1. 栈与队列到底在解决什么问题1.1 从“实验三”这个编号说起但凡计算机相关专业出身的人看到“实验三”这三个字脑子里大概都会浮现出一些共同的记忆碎片实验一通常是线性表实验二可能是链表到了实验三就该轮到栈和队列登场了。这个编排顺序不是随便定的它背后有一条很清晰的认知递进路线——线性表解决的是“数据怎么排成一排”的问题链表解决的是“数据怎么灵活地串起来”的问题而栈和队列解决的是“数据按照什么规则进出”的问题。换句话说前两个实验关注的是数据的静态结构实验三开始关注数据的动态行为。这个转变非常关键因为在实际工程中数据的访问顺序往往比数据本身的存储方式更能决定一个系统的行为特征。你想想浏览器的后退按钮、编辑器的撤销操作、函数调用的嵌套执行、操作系统的任务调度、消息队列的异步处理——这些东西表面上八竿子打不着但底层都依赖栈或队列这两种极其朴素却又极其强大的结构。我带过几届学生的实验课发现一个很普遍的现象很多人能把栈和队列的代码写出来数组实现和链表实现都能跑通但问他“为什么这里要用栈而不是队列”或者“什么场景下用循环队列比普通队列更合适”就答不上来了。这说明什么说明他学的是“代码怎么写”而不是“问题怎么解”。这篇内容就是想把后面这半截补上。1.2 栈和队列的本质差异一个“后进先出”一个“先进先出”用最直白的话说栈就是一摞盘子你只能从最上面拿也只能往最上面放。最后放上去的那个盘子一定是第一个被拿走的。这就是后进先出英文叫 LIFOLast In First Out。队列就是排队买奶茶先来的先服务后来的排在队尾。这就是先进先出英文叫 FIFOFirst In First Out。这两个规则听起来简单到近乎无聊但它们的应用场景差异巨大。栈适合处理“需要回退到最近状态”的问题比如括号匹配、表达式求值、深度优先搜索、函数调用栈。队列适合处理“需要按到达顺序公平处理”的问题比如广度优先搜索、任务调度、缓冲区管理、消息中间件。我经常跟人说你判断一个场景该用栈还是队列就问自己一个问题我需要先处理最近来的还是先处理最早来的如果是最近来的优先用栈如果是最早来的优先用队列。这个判断标准简单粗暴但命中率极高。1.3 这个实验到底要你掌握什么从教学设计的角度看“栈和队列的基本操作”这个实验通常要求你完成以下几件事用数组和链表两种方式分别实现栈和队列实现入栈、出栈、入队、出队、判空、取顶元素等基本操作理解并处理边界情况比如栈满、栈空、队列满、队列空掌握循环队列的取模运算原理最后通过几个经典应用案例如括号匹配、表达式求值、迷宫路径搜索来验证你的实现是否正确。但我想说的是这些要求只是“最低标准”。如果你只做到这些你拿到的是一个及格分。真正能让你从这个实验里获得长期收益的是理解每种实现方式的取舍逻辑是知道在什么场景下该选哪种结构是能把这些看似简单的工具组合起来解决更复杂的问题。接下来的内容我会按照这个思路展开既讲清楚基本操作怎么做也讲清楚背后的设计决策为什么这么定。2. 栈的核心操作与两种实现方式拆解2.1 顺序栈数组实现的细节与边界处理顺序栈就是用一段连续的内存通常是一个数组来存储栈元素同时用一个变量top来标记栈顶位置。这个top的设计有两种常见方案一种是top指向栈顶元素本身初始值为 -1另一种是top指向栈顶元素的下一个空位初始值为 0。两种方案都能用但混用会导致严重的逻辑错误所以选定一种之后就要贯彻到底。我个人的习惯是用top -1表示空栈top指向当前栈顶元素。这样入栈操作就是top然后赋值出栈操作就是取data[top]然后top--。逻辑非常直观不容易搞混。#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int top; } SeqStack; void initStack(SeqStack *s) { s-top -1; } int isEmpty(SeqStack *s) { return s-top -1; } int isFull(SeqStack *s) { return s-top MAX_SIZE - 1; } int push(SeqStack *s, int value) { if (isFull(s)) { return 0; // 栈满入栈失败 } s-data[(s-top)] value; return 1; } int pop(SeqStack *s, int *value) { if (isEmpty(s)) { return 0; // 栈空出栈失败 } *value s-data[(s-top)--]; return 1; } int getTop(SeqStack *s, int *value) { if (isEmpty(s)) { return 0; } *value s-data[s-top]; return 1; }这段代码看起来简单但有几个地方是初学者最容易翻车的。第一个坑是入栈时先判断满再自增顺序不能反。如果你先top再判断栈满的时候top已经越界了后面再回退就麻烦了。第二个坑是出栈时先取值再自减也不能反。第三个坑是取栈顶元素不改变top这个操作只是“看一眼”不是“拿走”。注意在实际工程中栈满时是返回错误码、抛异常还是动态扩容取决于你的使用场景。如果是嵌入式环境内存固定返回错误码更合适如果是上层应用动态扩容对调用方更友好。实验里通常要求返回错误码但你要知道这只是众多方案中的一种。2.2 链栈带头结点与不带头结点的选择链栈就是用链表来实现栈通常用单链表就够了。这里有一个经典的选择题带头结点还是不带头结点带头结点的好处是空栈和非空栈的操作逻辑统一入栈和出栈不需要特殊处理第一个结点的情况。不带头结点的好处是省一个结点的内存而且栈顶指针直接指向第一个有效元素逻辑更“纯粹”。在实验场景下我建议用带头结点的方式。原因很简单代码更简洁出错概率更低。你想想不带头结点的时候入栈要判断是不是空栈出栈也要判断是不是空栈每个操作都要多写一个分支。而带头结点的情况下入栈永远是“在头结点后面插入”出栈永远是“删除头结点后面的第一个结点”逻辑完全一致。typedef struct Node { int data; struct Node *next; } Node; typedef struct { Node *head; // 头结点 } LinkedStack; void initStack(LinkedStack *s) { s-head (Node *)malloc(sizeof(Node)); s-head-next NULL; } int isEmpty(LinkedStack *s) { return s-head-next NULL; } void push(LinkedStack *s, int value) { Node *newNode (Node *)malloc(sizeof(Node)); newNode-data value; newNode-next s-head-next; s-head-next newNode; } int pop(LinkedStack *s, int *value) { if (isEmpty(s)) { return 0; } Node *temp s-head-next; *value temp-data; s-head-next temp-next; free(temp); return 1; }链栈的入栈操作本质上就是头插法这个操作的时间复杂度是 O(1)不需要遍历链表。出栈也是 O(1)直接删除头结点后面的第一个结点即可。这就是为什么栈用链表实现时效率很高——所有的操作都集中在头部不需要随机访问。2.3 顺序栈 vs 链栈什么时候用哪个这个问题没有标准答案但有一些经验性的判断依据。对比维度顺序栈链栈内存分配预先分配固定大小动态分配按需增长空间开销可能有未使用的预留空间每个元素多一个指针开销入栈效率O(1)但可能触发扩容O(1)需要 malloc出栈效率O(1)O(1)需要 free缓存友好度高连续内存低结点分散适用场景栈大小可预估栈大小波动大如果你的栈大小可以预估而且对性能要求高比如嵌入式、游戏引擎顺序栈是更好的选择因为连续内存对 CPU 缓存更友好。如果你的栈大小完全不可预测或者你就是在做算法题链栈更省心不用担心扩容问题。实操心得在做实验的时候两种都实现一遍然后写一个测试用例分别往两个栈里压入十万个元素再全部弹出用clock()函数测一下时间。你会发现顺序栈通常快不少这个直观感受比看一百遍理论分析都管用。3. 队列的核心操作与循环队列的精髓3.1 普通队列的“假溢出”问题队列用数组实现时最朴素的做法是维护一个front和一个rearfront指向队头元素rear指向队尾元素的下一个位置。入队时rear出队时front。这个逻辑本身没问题但跑着跑着你就会发现一个尴尬的情况rear已经到达数组末尾了但front前面还有大量空闲空间因为出队操作只是把front往后移并没有真正释放前面的空间。这就是所谓的假溢出——队列明明没满但因为rear到头了没法再入队了。解决这个问题的方法就是循环队列把数组看成一个环rear到达末尾后绕回到开头。3.2 循环队列的取模运算与判满策略循环队列的核心就是取模运算rear (rear 1) % MAX_SIZEfront (front 1) % MAX_SIZE。这样rear和front就在数组里循环移动不会出现“到头了”的情况。但循环队列带来一个新的问题怎么判断队列是空还是满因为front rear既可能表示空队列也可能表示满队列。这个问题有三种常见的解决方案。第一种是牺牲一个存储单元规定rear的下一个位置是front时就算满这样队列最多存MAX_SIZE - 1个元素。判空条件是front rear判满条件是(rear 1) % MAX_SIZE front。这个方案最简单也是实验中最常用的。第二种是维护一个计数器size入队时size出队时size--。判空就是size 0判满就是size MAX_SIZE。这个方案不浪费空间但多维护一个变量。第三种是使用标志位tag当front rear时如果tag 0表示空tag 1表示满。每次入队设tag 1出队设tag 0。这个方案也不浪费空间但逻辑稍微绕一点。#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int front; int rear; } CircularQueue; void initQueue(CircularQueue *q) { q-front 0; q-rear 0; } int isEmpty(CircularQueue *q) { return q-front q-rear; } int isFull(CircularQueue *q) { return (q-rear 1) % MAX_SIZE q-front; } int enqueue(CircularQueue *q, int value) { if (isFull(q)) { return 0; } q-data[q-rear] value; q-rear (q-rear 1) % MAX_SIZE; return 1; } int dequeue(CircularQueue *q, int *value) { if (isEmpty(q)) { return 0; } *value q-data[q-front]; q-front (q-front 1) % MAX_SIZE; return 1; }我强烈建议在实验中选择第一种方案牺牲一个存储单元因为它的判空和判满条件非常清晰不容易写错。等你把第一种方案写熟了再去尝试另外两种作为思维训练。3.3 链队列带头结点让出队操作统一化链队列就是用链表实现队列通常需要两个指针front指向队头rear指向队尾。入队在rear后面插入新结点出队删除front后面的第一个结点。和链栈一样链队列也面临带头结点还是不带头结点的选择。这里我同样建议带头结点原因也是一样的让空队列和非空队列的操作逻辑统一。typedef struct QNode { int data; struct QNode *next; } QNode; typedef struct { QNode *front; // 头结点 QNode *rear; // 队尾指针 } LinkedQueue; void initQueue(LinkedQueue *q) { QNode *head (QNode *)malloc(sizeof(QNode)); head-next NULL; q-front head; q-rear head; } int isEmpty(LinkedQueue *q) { return q-front q-rear; } void enqueue(LinkedQueue *q, int value) { QNode *newNode (QNode *)malloc(sizeof(QNode)); newNode-data value; newNode-next NULL; q-rear-next newNode; q-rear newNode; } int dequeue(LinkedQueue *q, int *value) { if (isEmpty(q)) { return 0; } QNode *temp q-front-next; *value temp-data; q-front-next temp-next; if (q-rear temp) { q-rear q-front; // 队列变空时rear 要回退到头结点 } free(temp); return 1; }链队列里有一个非常容易忽略的细节当出队的是最后一个元素时rear必须回退到front的位置。如果你忘了这一步rear就会指向一个已经被free掉的结点后续入队操作就会访问非法内存。这个 bug 在实验里出现的频率极高而且因为不一定每次都崩溃所以特别难排查。注意链队列的rear指针在空队列时应该指向头结点而不是 NULL。这样入队操作就不需要判断队列是否为空统一用rear-next newNode即可。这是带头结点方案的又一个优势。4. 从基本操作到经典应用栈和队列的实战场景4.1 括号匹配栈的“回退”能力最直观的体现括号匹配是栈最经典的应用场景没有之一。给你一个字符串里面包含()、[]、{}三种括号判断这些括号是否合法嵌套。比如{[()]}是合法的{[(])}是不合法的。这个问题的核心逻辑是每遇到一个左括号就压栈每遇到一个右括号就检查栈顶是否是对应的左括号。如果是弹出栈顶如果不是直接判定不合法。最后如果栈为空说明所有括号都正确匹配了。int isMatching(char *str) { SeqStack s; initStack(s); for (int i 0; str[i] ! \0; i) { char c str[i]; if (c ( || c [ || c {) { push(s, c); } else if (c ) || c ] || c }) { if (isEmpty(s)) { return 0; // 右括号多余 } int top; pop(s, top); if ((c ) top ! () || (c ] top ! [) || (c } top ! {)) { return 0; // 括号类型不匹配 } } } return isEmpty(s); // 栈空说明全部匹配 }为什么用栈而不是队列因为括号匹配的本质是“最近打开的括号必须最先关闭”这正是后进先出的语义。如果你用队列最先打开的括号会最先被检查但它在嵌套结构里恰恰是最后才应该被关闭的逻辑就完全反了。4.2 表达式求值栈的“双栈”配合表达式求值是栈的另一个经典应用也是实验里经常出现的加分项。给定一个中缀表达式比如3 4 * 2 - (1 1)计算出结果。这个问题的标准解法是使用两个栈一个操作数栈一个运算符栈。核心规则是这样的从左到右扫描表达式遇到数字就压入操作数栈遇到运算符就和运算符栈顶比较优先级如果栈顶运算符优先级更高或相等就弹出栈顶运算符并从操作数栈弹出两个数进行计算把结果压回操作数栈然后继续比较如果当前运算符优先级更高就直接压入运算符栈。遇到左括号直接压入遇到右括号就不断弹出运算符直到遇到左括号。int getPriority(char op) { if (op || op -) return 1; if (op * || op /) return 2; return 0; } int calculate(int a, int b, char op) { switch (op) { case : return a b; case -: return a - b; case *: return a * b; case /: return a / b; } return 0; } int evaluate(char *expr) { SeqStack numStack, opStack; initStack(numStack); initStack(opStack); int i 0; while (expr[i] ! \0) { if (expr[i] 0 expr[i] 9) { int num 0; while (expr[i] 0 expr[i] 9) { num num * 10 (expr[i] - 0); i; } push(numStack, num); continue; } else if (expr[i] () { push(opStack, expr[i]); } else if (expr[i] )) { while (!isEmpty(opStack)) { int op; getTop(opStack, op); if (op () { pop(opStack, op); break; } pop(opStack, op); int b, a; pop(numStack, b); pop(numStack, a); push(numStack, calculate(a, b, op)); } } else if (expr[i] || expr[i] - || expr[i] * || expr[i] /) { while (!isEmpty(opStack)) { int topOp; getTop(opStack, topOp); if (topOp ( || getPriority(topOp) getPriority(expr[i])) { break; } pop(opStack, topOp); int b, a; pop(numStack, b); pop(numStack, a); push(numStack, calculate(a, b, topOp)); } push(opStack, expr[i]); } i; } while (!isEmpty(opStack)) { int op; pop(opStack, op); int b, a; pop(numStack, b); pop(numStack, a); push(numStack, calculate(a, b, op)); } int result; pop(numStack, result); return result; }这段代码看起来长但逻辑其实很清晰。关键点在于优先级比较的时机当前运算符优先级高于栈顶时才压栈否则先算栈顶的。这个规则保证了乘除法优先于加减法同时括号内的运算优先于括号外。4.3 迷宫路径搜索队列的广度优先搜索队列在搜索类问题中的典型应用是广度优先搜索BFS。以迷宫问题为例给定一个二维网格0 表示通路1 表示墙壁从起点出发找到终点的最短路径。BFS 的思路是从起点开始一层一层向外扩展每到一个新位置就把它加入队列然后从队列中取出位置继续扩展。typedef struct { int x, y; int step; } Point; int bfs(int maze[][100], int rows, int cols, int sx, int sy, int ex, int ey) { int visited[100][100] {0}; int dx[] {-1, 1, 0, 0}; int dy[] {0, 0, -1, 1}; Point queue[10000]; int front 0, rear 0; queue[rear] (Point){sx, sy, 0}; visited[sx][sy] 1; while (front rear) { Point cur queue[front]; if (cur.x ex cur.y ey) { return cur.step; } for (int d 0; d 4; d) { int nx cur.x dx[d]; int ny cur.y dy[d]; if (nx 0 nx rows ny 0 ny cols maze[nx][ny] 0 !visited[nx][ny]) { visited[nx][ny] 1; queue[rear] (Point){nx, ny, cur.step 1}; } } } return -1; // 无法到达 }BFS 用队列而不是栈的原因在于队列保证按层扩展先进入队列的结点先被处理这样第一次到达终点时的步数一定是最少的。如果你用栈来做就变成了深度优先搜索DFS虽然也能找到路径但不保证是最短路径。实操心得在迷宫问题中visited数组的标记时机非常关键。一定要在入队时就标记而不是在出队时标记。如果你在出队时才标记同一个位置可能被多次加入队列导致队列爆炸式增长严重时内存溢出。这个坑我在早期写代码时踩过不止一次。5. 实验中最容易踩的坑与排查技巧5.1 栈和队列的常见 Bug 速查表问题现象可能原因排查方法入栈后取栈顶元素不对top初始值设置错误检查top是 -1 还是 0与入栈逻辑是否一致出栈时程序崩溃空栈时未判空直接操作在pop开头加isEmpty检查循环队列入队失败但队列没满判满条件写错确认是牺牲一个单元还是用size计数链队列出队后入队崩溃rear未在队列变空时回退出队后检查rear是否指向被释放的结点链栈内存泄漏出栈时忘记free每次pop都要释放被删除的结点括号匹配结果错误右括号多余时未检查栈空遇到右括号先判空再弹栈比较5.2 调试栈和队列代码的三个有效手段第一个手段是打印中间状态。在每次入栈、出栈、入队、出队之后把top、front、rear的值和当前栈/队列的内容打印出来。这个方法看起来笨但对于理解指针变化非常有效。我见过很多学生代码写完了跑不通盯着代码看半天看不出问题一打印就发现top的变化和自己想的不一样。第二个手段是用小数据量手工模拟。不要一上来就用几百个元素测试先用三五个元素拿纸和笔把每一步的指针变化画出来然后和程序的输出对比。如果手工模拟的结果和程序不一致问题就定位到了具体哪一步。第三个手段是边界测试。空栈出栈、满栈入栈、空队列出队、满队列入队、循环队列绕回、链队列出到最后一个元素——这些边界情况是最容易出 bug 的地方。写一个测试函数专门测这些边界比随机测试有效得多。5.3 关于内存管理的经验教训栈和队列的实验里链式实现涉及大量的malloc和free。我见过太多人malloc写得很勤快free就忘得一干二净。短期跑没问题但如果你在循环里反复入队出队内存泄漏会迅速累积最终导致程序崩溃。一个实用的习惯是每写一个malloc立刻在旁边写一个注释标明这个内存在哪里释放。比如// 在 dequeue 中 free。这样你写dequeue的时候就会想起来要释放。另一个习惯是在程序退出前写一个destroyStack或destroyQueue函数把剩余的所有结点全部释放。虽然操作系统会在程序结束时回收内存但养成这个习惯对以后写大型程序非常有帮助。注意在链队列的dequeue操作中如果出队的是最后一个元素除了要回退rear指针还要注意不要释放头结点。头结点是队列结构的一部分只在destroyQueue时才释放。这个细节在实验里经常被忽略导致后续操作访问已释放的内存。6. 从实验代码到工程思维一些个人体会6.1 为什么“基本操作”值得反复写很多人觉得栈和队列的基本操作太简单了写一遍就够了没必要反复练。但我的经验恰恰相反越是基础的东西越值得反复写直到你能在不假思索的情况下写对。因为在实际工程中你很少会直接手写一个栈或队列但你会在各种场合用到它们的变体——单调栈、优先队列、双端队列、循环缓冲区、消息队列。这些高级结构的基础就是对基本操作的深刻理解。举个例子单调栈是栈的一种变体它在入栈时维护一个单调递增或递减的顺序。如果你对基本栈的入栈出栈逻辑不够熟练写单调栈的时候就会在“什么时候弹出栈顶”这个问题上卡住。但如果你对基本栈的操作已经形成了肌肉记忆单调栈的逻辑对你来说就是“在入栈前加一个 while 循环弹出不满足条件的元素”仅此而已。6.2 实验报告里应该写什么如果你正在做这个实验需要写实验报告我的建议是不要只贴代码和运行截图。那些东西网上一搜一大把体现不出你的思考。你应该重点写三样东西第一你在实现过程中遇到了什么问题你是怎么定位和解决的第二你对顺序实现和链式实现的性能做了哪些对比测试结果如何第三你对栈和队列的适用场景有什么自己的理解能不能举出实验要求之外的应用例子。这三样东西才是你真正从实验中获得的东西也是老师最想看到的东西。代码谁都能抄但思考过程抄不来。6.3 后续可以继续深入的方向如果你把这个实验做完了觉得还挺有意思想继续深入我推荐几个方向。第一个是用栈实现一个简单的计算器支持多位数、括号、四则运算这个在实验基础上稍微扩展就能做到。第二个是用队列实现一个任务调度模拟器模拟多个任务按优先级或时间片轮转调度的过程。第三个是实现一个双端队列支持从两端插入和删除然后用它来解决滑动窗口最大值问题。这些方向都不难但能让你从“会写基本操作”进阶到“能用这些结构解决实际问题”。这个跨越才是这个实验真正想让你完成的。我个人在实际操作中的体会是栈和队列这两个结构学一遍和学三遍的感受完全不同。第一遍你学的是语法第二遍你学的是逻辑第三遍你学的是直觉。当你看到一个问题脑子里能立刻浮现出“这个该用栈”或“这个该用队列”的时候你才算真正掌握了它们。而这个直觉只能靠反复写、反复错、反复改来培养。