栈和队列都是特殊的线性表。它们不改变“数据按顺序组织”的本质只是对插入和删除的位置施加了严格限制。一个遵循“后进先出”一个遵循“先进先出”却广泛存在于函数调用、浏览器历史记录、任务调度、消息系统和操作系统中。一、栈和队列对线性表操作的限制顺序表、链表都属于线性表理论上可以在任意位置插入或删除数据。而栈和队列是两种受限线性表数据结构插入位置删除位置核心原则栈栈顶栈顶后进先出 LIFO队列队尾队头先进先出 FIFO它们限制了操作位置因此在很多场景中逻辑更清晰也更容易保证数据处理顺序正确。二、栈后进先出1. 栈的基本概念栈Stack是一种只允许在固定一端插入和删除元素的线性表。允许操作的一端叫作栈顶另一端叫作栈底。栈遵循后进先出 LIFOLast In First Out可以把栈理解为一摞盘子┌─────┐ 栈顶 │ C │ - 最后放进去最先取出来 ├─────┤ │ B │ ├─────┤ 栈底 │ A │ - 最早放进去最后取出来 └─────┘如果依次把A、B、C压入栈中那么出栈顺序一定是C - B - A2. 栈的基本操作栈主要有以下操作操作含义初始化创建一个空栈入栈 Push在栈顶插入元素出栈 Pop删除栈顶元素取栈顶 Top获取栈顶元素但不删除判空 Empty判断栈中是否没有元素获取大小 Size获取有效元素个数销毁 Destroy释放动态申请的内存注意栈不允许从中间删除元素也不允许跳过栈顶直接访问栈底。三、为什么栈通常用数组实现栈可以用数组实现也可以用链表实现。但在大多数情况下使用动态数组实现栈更合适。原因是栈的操作只发生在栈顶而数组尾部插入和删除元素的效率很高。数组尾部入栈O(1) 数组尾部出栈O(1)例如数组 下标 0 1 2 数据 [10] [20] [30] ↑ 栈顶如果要压入40[10] [20] [30] [40] ↑ 栈顶不需要移动原有元素。四、动态栈的 C 语言实现1. 栈的结构typedef int STDataType; typedef struct Stack { STDataType* data; int top; int capacity; } Stack;其中data动态数组首地址top栈顶元素的下一个位置capacity当前数组容量。这里采用一种常见设计top 表示有效元素个数因此空栈时top 0 栈顶元素下标top - 1例如data [10, 20, 30] top 3 栈顶元素是 data[top - 1]即 302. 初始化栈#include assert.h #include stdlib.h void StackInit(Stack* ps) { assert(ps); ps-data NULL; ps-top 0; ps-capacity 0; }初始化后栈中没有数据也没有申请动态空间。3. 入栈操作当栈满时需要先扩容。#include stdio.h void StackPush(Stack* ps, STDataType x) { assert(ps); if (ps-top ps-capacity) { int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2; STDataType* tmp (STDataType*)realloc( ps-data, newCapacity * sizeof(STDataType) ); if (tmp NULL) { perror(realloc failed); exit(EXIT_FAILURE); } ps-data tmp; ps-capacity newCapacity; } ps-data[ps-top] x; ps-top; }例如依次执行StackPush(st, 10); StackPush(st, 20); StackPush(st, 30);栈内逻辑结构为栈底 [10] [20] [30] 栈顶4. 出栈操作出栈本质上不需要真的“删除数组元素”只需要让top向前移动一格。void StackPop(Stack* ps) { assert(ps); assert(ps-top 0); ps-top--; }例如出栈前 [10] [20] [30] ↑ top 出栈后 [10] [20] ↑ top原本的30还可能留在内存中但逻辑上已经不属于栈了。5. 获取栈顶元素STDataType StackTop(Stack* ps) { assert(ps); assert(ps-top 0); return ps-data[ps-top - 1]; }注意获取栈顶元素不等于出栈。StackTop(st); // 只查看 StackPop(st); // 真正删除6. 判断栈是否为空int StackEmpty(Stack* ps) { assert(ps); return ps-top 0; }如果返回非零值说明栈为空。7. 销毁栈void StackDestroy(Stack* ps) { assert(ps); free(ps-data); ps-data NULL; ps-top 0; ps-capacity 0; }动态申请的内存必须释放否则会产生内存泄漏。五、栈的典型应用1. 函数调用程序调用函数时会保存当前函数的局部变量、返回地址等信息。函数调用遵循后进先出main 调用 A A 调用 B B 调用 C调用关系main - A - B - C返回顺序C - B - A - main这正是典型的栈结构。2. 浏览器前进和后退浏览器访问页面首页 - 搜索页 - 商品页 - 订单页点击“后退”时最后访问的页面最先被返回。这可以用两个栈实现后退栈前进栈。3. 括号匹配问题例如下面的表达式(a b) * [c - d]括号是正确匹配的。而下面的表达式(a b]括号类型不匹配。再例如(a b左括号没有关闭也是不合法的。4. 括号匹配的核心思路遍历字符串遇到左括号(、[、{压入栈遇到右括号)、]、}检查栈顶是否是对应左括号如果不匹配表达式非法最后栈必须为空。示例输入{[()]} 遍历过程 遇到 { 入栈 遇到 [ 入栈 遇到 ( 入栈 遇到 ) 与栈顶 ( 匹配出栈 遇到 ] 与栈顶 [ 匹配出栈 遇到 } 与栈顶 { 匹配出栈 最终栈为空匹配成功代码示意int IsValid(char* s) { Stack st; StackInit(st); while (*s) { if (*s ( || *s [ || *s {) { StackPush(st, *s); } else { if (StackEmpty(st)) { StackDestroy(st); return 0; } char top StackTop(st); if ((*s ) top () || (*s ] top [) || (*s } top {)) { StackPop(st); } else { StackDestroy(st); return 0; } } s; } int result StackEmpty(st); StackDestroy(st); return result; }时间复杂度O(N)空间复杂度O(N)六、队列先进先出1. 队列的基本概念队列Queue是一种只允许在一端插入元素、在另一端删除元素的线性表。队列遵循先进先出 FIFOFirst In First Out可以把队列理解为排队买票队头 队尾 A - B - C - D ↑ ↑ 最先离开 新人从这里加入如果A、B、C、D依次进入队列那么离开队列的顺序一定是A - B - C - D2. 队列的基本操作操作含义入队 QueuePush在队尾插入元素出队 QueuePop删除队头元素取队头 QueueFront获取队头元素取队尾 QueueBack获取队尾元素判空 QueueEmpty判断队列是否为空销毁 QueueDestroy释放所有结点七、为什么队列通常用链表实现队列也可以用数组实现。但普通数组如果从头部出队就需要移动后面的所有元素。例如出队前 [A] [B] [C] [D] A 出队后 [B] [C] [D]为了让数组保持连续B、C、D都需要向前移动。因此普通数组从头部删除的时间复杂度是O(N)而链表只需调整指针A - B - C - D 出队后 B - C - D只需要修改队头指针复杂度为O(1)所以队列通常使用链表实现。八、链式队列的 C 语言实现1. 队列结点typedef int QDataType; typedef struct QueueNode { QDataType data; struct QueueNode* next; } QNode;2. 队列结构为了保证入队和出队都是 O(1)队列需要同时保存队头和队尾指针。typedef struct Queue { QNode* front; QNode* rear; int size; } Queue;其中front指向队头rear指向队尾size记录有效元素个数。3. 初始化队列void QueueInit(Queue* q) { assert(q); q-front NULL; q-rear NULL; q-size 0; }空队列满足front NULL rear NULL4. 入队操作void QueuePush(Queue* q, QDataType x) { assert(q); QNode* newNode (QNode*)malloc(sizeof(QNode)); if (newNode NULL) { perror(malloc failed); exit(EXIT_FAILURE); } newNode-data x; newNode-next NULL; if (q-rear NULL) { q-front q-rear newNode; } else { q-rear-next newNode; q-rear newNode; } q-size; }重点是空队列的特殊情况if (q-rear NULL) { q-front q-rear newNode; }第一次插入元素时队头和队尾都应该指向新结点。5. 出队操作void QueuePop(Queue* q) { assert(q); assert(q-front ! NULL); QNode* del q-front; q-front q-front-next; free(del); q-size--; if (q-front NULL) { q-rear NULL; } }最后一个元素出队后必须让front NULL rear NULL否则rear会变成悬空指针后续操作可能出现严重错误。6. 获取队头和队尾元素QDataType QueueFront(Queue* q) { assert(q); assert(q-front); return q-front-data; } QDataType QueueBack(Queue* q) { assert(q); assert(q-rear); return q-rear-data; }7. 判断队列是否为空int QueueEmpty(Queue* q) { assert(q); return q-front NULL; }8. 销毁队列void QueueDestroy(Queue* q) { assert(q); QNode* cur q-front; while (cur) { QNode* next cur-next; free(cur); cur next; } q-front NULL; q-rear NULL; q-size 0; }链式队列中的每个结点都由malloc申请因此销毁时必须逐个释放。九、循环队列解决数组队列的空间浪费普通数组队列存在一个问题。假设数组容量为 5初始状态 [ ][ ][ ][ ][ ]入队A、B、C、D、E[A][B][C][D][E]然后A、B出队[ ][ ][C][D][E]数组前面明明有空位但如果rear已经到末尾普通数组无法继续从尾部插入元素。这就是“假溢出”。循环队列的解决方法是让数组首尾相连。数组最后一个位置的下一个位置是数组第一个位置常见位置计算next (index 1) % capacity;1. 循环队列判空循环队列为空时front rear2. 循环队列判满如果规定front指向队头前一个位置并且空出一个位置来区分“空”和“满”那么队满条件是(rear 1) % capacity front此时队列有效元素个数为(rear - front capacity) % capacity需要注意如果数组长度为 N并且采用“空出一个位置”的方案最多只能存 N - 1 个元素。例如数组容量为 5实际最多存放 4 个元素。十、栈和队列的复杂度对比操作栈链式队列插入栈顶入栈 O(1)队尾入队 O(1)删除栈顶出栈 O(1)队头出队 O(1)获取元素获取栈顶 O(1)获取队头、队尾 O(1)随机访问不支持不支持它们的设计目标不是随机访问而是严格维护特定的数据处理顺序。十一、经典面试题思路1. 用两个队列实现栈栈需要“后进先出”队列是“先进先出”。可以让一个队列保存数据另一个队列用于辅助。出栈时将非空队列中前size - 1个元素搬到辅助队列剩下的最后一个元素就是栈顶删除该元素交换两个队列的角色。特点入栈O(1) 出栈O(N)2. 用两个栈实现队列队列需要“先进先出”可以利用两个栈反转两次顺序。准备pushStack负责入队popStack负责出队。入队时直接压入pushStack。出队时如果popStack不为空直接弹出如果popStack为空将pushStack的全部元素转移到popStack再从popStack弹出。例如pushStack 1 2 3 ↑ 栈顶 全部转移后 popStack 3 2 1 ↑ 栈顶此时弹出1正好符合队列先进先出。虽然某次转移可能是 O(N)但每个元素最多经历一次“入 pushStack”和一次“转移到 popStack”因此整体摊销复杂度为O(1)十二、总结栈和队列都是受限线性表栈遵循后进先出适合函数调用、括号匹配、撤销操作等场景队列遵循先进先出适合任务调度、消息处理、广度优先搜索等场景栈通常使用动态数组实现队列通常使用链表实现循环队列可以用数组高效解决普通数组队列的假溢出问题。理解栈和队列时不要只背定义更应该从数据流动方向理解栈最后进入的数据最先处理 队列最早进入的数据最先处理当你能在脑中画出“数据从哪里进入、从哪里离开”栈和队列的代码实现就会清晰很多。