队列栈与一般线性表区别

线性表抽象是存储具有先后顺序元素数据的结构,支持任意位置的插入,删除操作。队列和栈限制插入删除操作,队列只能从尾部插入,首部取出(删除),既先入先出;栈限制插入和取出操作只能在尾部进行,既先入后出。

实现方式

队列和栈同一般线性表相同,可用数组和链式结构体实现。由于限制了插入和取出的位置,没有频繁的中间元素操作,数组实现比链式实现效率更高。对应缺点为初始化时要定义数组大小,无法动态分配大小。

代码实现

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);    }}