队列栈与一般线性表区别
线性表抽象是存储具有先后顺序元素数据的结构,支持任意位置的插入,删除操作。队列和栈限制插入删除操作,队列只能从尾部插入,首部取出(删除),既先入先出;栈限制插入和取出操作只能在尾部进行,既先入后出。
实现方式
队列和栈同一般线性表相同,可用数组和链式结构体实现。由于限制了插入和取出的位置,没有频繁的中间元素操作,数组实现比链式实现效率更高。对应缺点为初始化时要定义数组大小,无法动态分配大小。
代码实现
栈
struct stack;typedef struct stack sStack;typedef sStack *pStack;#define EmptyTOS -1;struct stack { int capacity; int topOfStack; long long int *data;};pStack elrInitStackInt(int capaticy) { pStack s; s = malloc(sizeof(sStack)); if (s == NULL) { printf("out of space!"); } s->data = malloc(sizeof(long long int) * capaticy); if (s->data == NULL) { printf("out of space!"); } s->capacity = capaticy; elrMakeStackEmpty(s); return s;}void elrFreeStackInt(pStack stack) { if (stack != NULL) { free(stack->data); free(stack); }}int elrIsStackEmpty(pStack stack) { return stack->topOfStack == EmptyTOS;}int elrIsStackFull(pStack stack) { return stack->topOfStack == (stack->capacity - 1);}void elrMakeStackEmpty(pStack stack) { stack->topOfStack = EmptyTOS;}void elrPushStackInt(pStack stack, long long int data) { if (elrIsStackFull(stack)) { printf("full stack"); } else { stack->data[++stack->topOfStack] = data; }}long long int elrPopStackInt(pStack stack) { if (elrIsStackEmpty(stack)) { printf("empty stack"); } else { return stack->data[--stack->topOfStack]; }}
队列
struct queue;typedef struct queue sQueue;typedef sQueue *pQueue;struct queue { int capacity; int front; int rear; int size; long long int *data;};pQueue elrInitQueueInt(int capaticy) { pQueue s; s = malloc(sizeof(sQueue)); if (s == NULL) { printf("out of space!"); } s->data = malloc(sizeof(long long int) * capaticy); if (s->data == NULL) { printf("out of space!"); } s->capacity = capaticy; elrMakeQueueEmpty(s); return s;}void elrFreeQueueInt(pQueue queue) { if (queue != NULL) { free(queue->data); free(queue); }}int elrIsQueueEmpty(pQueue queue) { return queue->size == 0;}int elrIsQueueFull(pQueue queue) { return queue->size == queue->capacity;}void elrMakeQueueEmpty(pQueue queue) { queue->size = 0; queue->front = 1; queue->rear = 0;}int succ(pQueue queue, int value) { if (++value == queue->capacity) { value = 0; } return value;}void elrEnqueuekInt(pQueue queue, long long int data) { if (elrIsQueueFull(queue)) { printf("full queue"); } else { queue->size++; queue->rear = succ(queue, queue->rear); queue->data[queue->rear] = data; }}long long int elrDequeueInt(pQueue queue) { if (elrIsQueueEmpty(queue)) { printf("empty queue"); } else { queue->size--; int data = queue->data[queue->front]; queue->front = succ(queue, queue->front); }}