栈和队列在数据结构中有什么区别和特点？

本文共计1363个文字，预计阅读时间需要6分钟。

栈和队列的基本概念、在数组中，我们可以通过索引（下标）访问任意元素。但在某些情况下，我们可能需要限制处理顺序，这时就产生了栈和队列这两种功能受限的线性结构。

栈和队列 一、栈和队列的基本概念

在数组中，我们可以通过索引(下标)访问随机元素。但是，在某些情况下，我们可能需要限制处理顺序，这就产生了栈和队列这两种功能受限的线性结构。

栈和队列是两种不同的处理顺序：先进后出和先进先出，以及两个相应的线性数据结构。

二、数据结构中的栈和队列 1、栈(stack)

数据后进先出，先进后出 LIFO (last in first out)

栈只有一个开口，先进去的就到下面，后进来的就在上面(top)，要是拿出去的话，肯定是从开口端拿出去，所以说先进后出，后进先出。

入栈 push 出栈 pop 获取栈顶元素 top

判断栈是否已经是空

判断栈是否已经满了 is_full（如果是数组实现的)

2、队列(queue)

先进先出，后进后出 FIFO (first in first out)

队列有队首(front) 和队尾(back), 数据从对尾进去队列，从队首出列，队头(front)指向队列的第一个数据，对尾(back)指向队列中最后一个数据。

入队 push 出队 pop 队头 front 队尾 back 三、栈和队列的基本结构

四、栈和队列的实现 1、使用链表或顺序表实现栈 1.1 声明

#define STACK_SIZE_MAX 10 //栈的最大大小 typedef struct Stack //栈的结构声明 { Type data[STACK_SIZE_MAX]; //数据域 int top; //栈顶元素下标 }Stack; //1 栈的初始化函数 Stack* stack_init(); //2 数据入栈函数 void stack_push(Stack* stack,Type val); //3 数据出栈函数 Type stack_pop(Stack* stack); //4 获取栈顶元素 Type stack_top(Stack* stack); //5 判断栈是否为空 bool stack_empty(Stack* stack); //6 判断栈是否满了 bool stack_full(Stack* stack); 1.2 功能实现

//1 栈的初始化函数 Stack* stack_init() { Stack* temp = (Stack*)malloc(sizeof(Stack)); assert(temp); temp->top = -1; //初始化栈顶元素下标为-1，表示栈中没有数据 return temp; } //2 数据入栈函数 void stack_push(Stack* stack, Type val) { assert(stack); //判断栈是否存在 assert(!stack_full(stack)); //判断栈是否满了 stack->data[++stack->top] = val; //栈顶插入元素 } //3 数据出栈函数 Type stack_pop(Stack* stack) { assert(stack); assert(!stack_empty(stack)); //判断栈是否为空 Type val = stack->data[stack->top]; //记录当前栈顶元素 stack->top--; //栈顶下标-1 return val; } //4 获取栈顶元素 Type stack_top(Stack* stack) { assert(stack); assert(!stack_empty(stack)); //判断栈是否为空 return stack->data[stack->top]; } //5 判断栈是否为空 bool stack_empty(Stack* stack) { return stack->top == -1; //栈空了 } //6 判断栈是否满了 bool stack_full(Stack* stack) { return stack->top >= STACK_SIZE_MAX - 1; //栈满了 } 2、使用链表或顺序表实现队列

对于队列来说，入队和出队比较频繁，所以如果用顺序表实现入队虽然简单，但是每次出队都要移动整个顺序表，效率不高，所以使用链表实现。

2.1 队列声明

//队列节点的声明 typedef struct Node { Type data; Node* next; }Node; typedef struct Queue { Node* front; //队首 Node* back; //队尾 }Queue; //队列单例表的初始化 Queue* queue_init(); //队列单链表节点的初始化 Node* node_create(Type val); //1 数据入队 void queue_push(Queue* q, Type val); //2 数据出队 Type queue_pop(Queue* q); //3 获取队首元素 Type queue_front(Queue* q); //4 获取队尾元素 Type queue_back(Queue* q); //5 判断队列是否为空 bool queue_isNull(Queue* q); 2.2 功能实现

//1 队列单例表的初始化 Queue* queue_init() { Queue* queue = (Queue*)malloc(sizeof(Queue));//开辟空间 assert(queue); //断言:如果queue为空或者0，则会弹出报错窗口 queue->front = queue->back = nullptr; return queue; } //2 队列单链表节点的初始化 Node* node_create(Type val) { Node* temp = (Node*)malloc(sizeof(Node)); assert(temp); temp->data = val; temp->next = nullptr; return temp; } //3 数据入队 void queue_push(Queue* q, Type val) //尾插 { assert(q); if (q->front == nullptr) //队首为空 { q->front = node_create(val); q->back = q->front; } else { q->back->next = node_create(val); q->back = q->back->next; } } //4 数据出队 Type queue_pop(Queue* q) //头删 { assert(q); //整个链表不存在 assert(q->front); //链表为空 Node* temp = q->front; Type val = temp->data; q->front = q->front->next; //当前队首的下一个节点成为新的队首 free(temp); //之前的队首出队，空间释放 temp = NULL; //避免temp是野指针 return val; } //5 获取队首元素 Type queue_front(Queue* q) { assert(q); //整个链表不存在 assert(q->front); //链表为空 return q->front->data; } //6 获取队尾元素 Type queue_back(Queue* q) { assert(q); //整个链表不存在 assert(q->front); //链表为空 return q->back->data; } //7 判断队列是否为空 bool queue_isNull(Queue* q) { assert(q); //整个链表不存在 if (q->front == NULL) { return true; } else { return false; } //或者直接 return q->front == NULL; } 3、检查代码的健壮性，是否能够正常使用