栈与队列从零实战：手写实现到单调栈、滑动窗口算法

如果说数据结构里最贴近生活直觉的我第一个想到的就是栈和队列。浏览器右上角的后退按钮点一下回到上一次访问的页面反反复复都是在最后一层进出——这叫后进先出食堂打饭排队、打印机接收多台电脑发来的任务谁先到谁先处理这叫先进先出。前者抽象成栈后者抽象成队列。这两个结构看起来都很简单“能往里放东西再取出来”但正因为存取顺序不同各自的底层实现方式、边界条件处理以及围绕它们衍生出来的单调栈、单调队列、滑动窗口最大值、括号匹配、表达式求值等高阶算法完全是一套独立逻辑。这篇文章我会从零开始把栈和队列各写一遍再把这几年做项目和刷算法题时攒下来的实现思路、选择依据和踩坑经验串在一起给正准备啃这块知识点的读者一条相对平滑的路径。1. 从后退按钮到打印队列栈和队列到底解决什么问题1.1 先建立直觉LIFO和FIFO分别适合什么场景很多教材一上来就甩定义栈是限定只在表尾插入和删除的线性表队列是限定在队尾插入、队头删除的线性表。这话没错但容易让人记住规则却忘了为什么需要这类规则。我更喜欢的理解方式是栈适合处理“嵌套”和“回溯”队列适合处理“等待”和“顺序”。举个实际的嵌套例子。你写一个函数函数里又调用另一个函数另一个函数再调用下一个。计算机在执行时最晚被调用的函数最先返回这就是天然的函数调用栈。如果你中途想去看看当前执行到哪一层也只能从最内层栈顶往回退。所以任何涉及递归、撤销操作、括号匹配、表达式求值的问题几乎都能看到栈的影子。队列这边更偏向时间顺序。操作系统里的进程调度、网络路由器里的数据包转发、秒杀系统里的请求排队都是先来的请求先处理。消息队列产品本质上也是这个思路只不过它把数据结构升级成了分布式系统里的异步通信机制。如果你想把某个过程“按时间顺序公平地处理”队列就是最直接的选择。1.2 从操作层面看栈和队列的差异点在哪栈只有两个核心操作push压栈和pop弹栈另外通常会有一个top/peek操作只查看栈顶元素。队列的核心操作是enqueue入队和dequeue出队加上front/peek查看队头。差异主要在三点存取位置栈只动栈顶队列是队尾进、队头出。遍历语义栈天然适合深度优先遍历队列天然适合广度优先遍历。空间回收栈的容量变化通常集中在尾部队列却常常因为头部出队而留下前端空洞。这三点差异直接决定了后面实现时的边界条件设计。比如用数组实现栈top指针从-1开始每push一个元素top加1代码简洁到几乎没有歧义但用数组实现队列如果只让front不断后移数组前段很快变成一片死区空间就不能复用了。所以队列实现经常要引入循环队列这算是数据结构里第一个需要点“绕弯思维”的地方。2. 顺序栈与链栈实战容量管理是新手最容易翻车的地方2.1 顺序栈的基础结构设计用数组实现栈核心就是三个字段底层数组、栈顶指针、当前容量。我习惯让top初始化为-1这样栈空时判断条件是top -1栈满时判断条件是top capacity - 1很直观。如果你把top初始化为0也不是不行但push和pop时要先处理指针还是先处理数据的关系容易记混尤其是初学者用-1作为空的标记会省很多事。#include stdio.h #include stdlib.h #include stdbool.h #define INIT_CAPACITY 4 typedef struct { int *data; int top; int capacity; } SeqStack; void initStack(SeqStack *s) { s-data (int *)malloc(sizeof(int) * INIT_CAPACITY); s-top -1; s-capacity INIT_CAPACITY; } bool isEmpty(SeqStack *s) { return s-top -1; } bool isFull(SeqStack *s) { return s-top s-capacity - 1; } void push(SeqStack *s, int value) { if (isFull(s)) { s-capacity * 2; s-data (int *)realloc(s-data, sizeof(int) * s-capacity); } s-data[s-top] value; } int pop(SeqStack *s) { if (isEmpty(s)) { printf(stack underflow\n); exit(1); } return s-data[s-top--]; } int peek(SeqStack *s) { return s-data[s-top]; }如果你用的是C语言记得在push里先判断满再扩容扩容用的是realloc它会把旧数据自动拷贝到新内存。如果你是C或Java选手直接用vector、ArrayList这类动态数组就行扩容细节被封装了但知道底层是倍增策略仍然有帮助。2.2 为什么扩容要乘2而不是一点一点加很多人第一次写动态栈时扩容幅度拍脑袋定成“容量加10”。在小规模测试下没区别一旦push次数上万每次扩容都触发一次realloc和数据拷贝时间开销会非常难看。乘2是空间和时间的折中空间上最多浪费一倍时间上让扩容操作分摊到每次push时均摊复杂度从O(n)降到O(1)。如果你在意内存碎片乘1.5也是一种常见选择Go的slice扩容策略里也有类似的考量。总之不要一次只加一个元素否则你在反复搬家。2.3 链栈实现与顺序栈的取舍链栈就是用单链表模拟栈每次push相当于在链表头部插入pop相当于删除头部节点。它没有容量上限也不会因为动态扩容发生整体拷贝代价是指针字段带来的额外内存开销。typedef struct StackNode { int data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; int size; } LinkedStack; void pushLinked(LinkedStack *s, int value) { StackNode *node (StackNode *)malloc(sizeof(StackNode)); node-data value; node-next s-top; s-top node; s-size; } int popLinked(LinkedStack *s) { if (s-top NULL) { printf(stack underflow\n); exit(1); } StackNode *tmp s-top; int value tmp-data; s-top tmp-next; free(tmp); s-size--; return value; }我的建议是如果栈的大小可以在工程启动时预估优先用顺序栈缓存友好实现简单如果栈元素属于自定义结构体且内存占用大、数量不确定链栈更合适。算法题里绝大多数情况下用顺序栈就够了。3. 循环队列与链式队列为什么队列实现更讲究空间效率3.1 直接用数组当队列会有什么问题假设你用数组模拟队列front指向队头rear指向队尾入队时rear出队时front。很快你就会发现出队操作让数组前段元素再也没有机会被访问但rear已经跑到数组末尾了此时你明明“物理上”还有很多空间却没法再入队。这就是“假溢出”。解决办法有两个一是出队时把所有元素整体前移让front回到0但每次出队都是O(n)很浪费二是把数组头尾拼接成环形用模运算实现下标循环。后者就是循环队列。3.2 循环队列的临界判断是重头戏循环队列需要区分空和满。有两种常见设计一种是留一个空位用(rear 1) % capacity front判满、front rear判空另一种是引入size字段记录当前元素个数。我推荐带size的版本理解起来最没有歧义调试时也直观代价只是多维护一个整型字段。typedef struct { int *data; int front; int rear; int size; int capacity; } CircularQueue; void initQueue(CircularQueue *q, int cap) { q-data (int *)malloc(sizeof(int) * cap); q-front 0; q-rear 0; q-size 0; q-capacity cap; } bool queueEmpty(CircularQueue *q) { return q-size 0; } bool queueFull(CircularQueue *q) { return q-size q-capacity; } void enqueue(CircularQueue *q, int value) { if (queueFull(q)) { printf(queue overflow\n); exit(1); } q-data[q-rear] value; q-rear (q-rear 1) % q-capacity; q-size; } int dequeue(CircularQueue *q) { if (queueEmpty(q)) { printf(queue underflow\n); exit(1); } int value q-data[q-front]; q-front (q-front 1) % q-capacity; q-size--; return value; }注意每次移动front或rear之后都要对capacity取模。这是循环队列区别于顺序栈最重要的地方。很多bug就出在忘了取模导致下标越界或者front变成负数。3.3 链式队列的天然优势与适用场合链式队列用head指针指向队头节点tail指针指向队尾节点。入队在tail之后接新节点出队从head删除节点。因为没有容量上限不会出现假溢出也不需要考虑取模。它的适用场景是队列入队出队频率差异大、无法预判缓存大小或者元素本身是大对象。但是链式队列的每个节点都多存一个指针缓存局部性差连续几十万次入队出队性能可能明显低于循环队列。所以工程实现里如果队列容量可预估我几乎总是先考虑环形数组只有容量完全不可控时才用链表。语言层面的队列类库也往往如此比如Java的ArrayDeque就是一个用环形数组实现的双端队列平时用它代替LinkedList的场景非常多。4. 单调栈与单调队列从基础结构到算法利器4.1 单调栈的思考方式为什么它能把O(n²)降成O(n)单调栈不是一种新的数据结构而是“栈 人为维护的单调性”。核心逻辑是当新元素要入栈时循环弹出所有破坏单调性的栈顶元素。这道维护单调性的操作让栈内元素始终保持从栈底到栈顶递增或递减。典型的题目是找数组中每一个元素右边第一个比它大的数。暴力做法是双重循环对每个元素向右扫时间复杂度O(n²)。用单调栈只需遍历一遍数组维护一个递减栈。场景还原一下从右往左遍历时如果当前元素比栈顶元素大说明栈顶这个“候选答案”已经不可能再是当前元素右边的更大值更靠右且有更合适的值在栈底弹出它。弹完以后栈顶元素就是当前元素右边第一个比它大的数。把当前元素下标压栈。def next_greater_element(nums): n len(nums) res [-1] * n stack [] for i in range(n - 1, -1, -1): while stack and nums[stack[-1]] nums[i]: stack.pop() if stack: res[i] nums[stack[-1]] stack.append(i) return res每个元素最多被弹出一次总操作次数是O(n)。真正值钱的不是代码本身而是“维护单调性、淘汰永远不会成为答案的候选者”这一思想。后面遇到底面积最大的直方图、接雨水这些题都是同一套栈内维护单调性的思路只是比较条件和答案计算方式不同。4.2 单调队列的滑动窗口应用滑动窗口最大值是另一个高频算法。需求很简单给定数组和一个固定长度k的窗口窗口每次右移一格求每个窗口里最大的元素。如果每次重新扫描窗口复杂度O(nk)窗口一大就完蛋。单调队列的做法是用双端队列deque维护候选最大值的下标并保证队头到队尾对应元素单调递减。关键步骤有三个窗口右移时先把队列中所有小于等于新元素的下标从队尾弹出。因为新元素更靠右、值更大旧的那些小值不可能再成为当前或后续窗口的最大值。再把队头已经滑出窗口的下标弹出。此时队头就是当前窗口最大值。from collections import deque def max_sliding_window(nums, k): dq deque() res [] for i, x in enumerate(nums): while dq and dq[0] i - k: dq.popleft() while dq and nums[dq[-1]] x: dq.pop() dq.append(i) if i k - 1: res.append(nums[dq[0]]) return res这里之所以选择队列而不是栈是因为窗口边界的推进是“旧元素从队头离开、新元素从队尾进来”时间顺序上符合先进先出。有人会问为什么不用大顶堆堆也能维护最大值但没法方便地删除滑出窗口的那个旧元素除非用懒删除否则实现复杂度更高。单调队列的价值就在这它利用元素进出顺序直接淘汰永远不会是答案的候选者连删除操作都变得极其自然。4.3 单调结构在真实工程里的延伸滑动窗口最大值不只是算法题它在很多场景中都有现实映照比如某个时间段内的最高水位、网络监控里最近五分钟的最大延迟、实时交易里的最大价格回撤。实现这些功能时不需要维护完整数组只要维护一个单调队列空间开销从O(n)降到O(k)。如果你日后要处理流式数据这种“只保留潜力候选者”的思路会一直有用。5. 括号匹配、表达式求值与广度优先在经典题目里辨认栈和队列的影子5.1 括号匹配栈的最直白应用括号匹配的题目描述很简单给一个只含()[]{}的字符串判断括号是否有效。解法就是用栈遇到左括号压栈遇到右括号时看栈顶是不是匹配的左括号匹配就弹出不匹配直接返回false最后栈必须为空。def is_valid(s): stack [] pairs {): (, ]: [, }: {} for ch in s: if ch in pairs: if not stack or stack[-1] ! pairs[ch]: return False stack.pop() else: stack.append(ch) return not stack为什么必须用栈因为括号的有效性天然是嵌套结构最后一层只与最内层未匹配的左括号有关。这正好对应栈的后进先出语义。如果你去尝试用一个队列或者一个列表加front指针来解就会发现自己一直在和一个“错误顺序”的抽象较劲。5.2 表达式求值与逆波兰式中缀表达式对人友好但对程序不友好因为要处理运算符优先级和括号。解决思路是把中缀转成后缀表达式逆波兰式然后用栈求值。转换时操作数直接输出运算符压栈遇到右括号就弹栈直到左括号。求值时遇到数字压栈遇到运算符弹出两个操作数计算后把结果压回栈。这个过程中栈承担了所有的临时状态保存。如果你对编译器前端感兴趣表达式求值几乎可以算是初识语法分析的最佳入门练习。5.3 队列与BFS的关系广度优先搜索BFS之所以用队列是因为它要求“先访问的节点其邻居也先被访问”。比如二叉树的层序遍历从根节点开始把每一层节点按从左到右的顺序放入队列弹出时再把它们的子节点入队就能保证按层输出。这个过程如果换成栈深度优先后序遍历可能是另一套结果往往就不是按层推进了。在求解无权图的最短路径时BFS也是主流选择因为第一次到达某个点时所走的步数就是最短步数。你需要一个队列来维持“下一步将要访问的节点集合”这个集合的顺序是由访问时刻决定的先进先出完美匹配。5.4 递归转迭代时显式栈怎么用递归函数依赖系统调用栈。当递归深度太大时容易爆栈或者语言对递归深度有限制比如Python默认大约1000层。这时可以用显式栈模拟系统的递归调用栈把递归转成迭代。以二叉树前序遍历为例维护一个栈先压右子节点再压左子节点弹出顺序就保证了先左后右。def preorder(root): if not root: return [] stack [root] res [] while stack: node stack.pop() res.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res这类写法的麻烦点在于状态还原。更复杂的递归比如递归里做了多步操作转迭代时往往要在栈节点里存一个“第几步”的标志模拟递归返回后的继续执行位置。这是比较进阶的玩法但在写解释器或做超深递归优化时迟早会遇到。6. 实现过程中最容易踩的坑与我的调试习惯6.1 边界条件表写之前最好先过一遍把常见边界条件列成表写代码前先默念一遍很多bug能直接预防。场景栈队列空状态top -1size 0循环队列满状态top capacity - 1size capacity单元素pop后回到空状态dequeue后回到空状态满时再push需要扩容或拒绝需要扩容或拒绝空时popunderflowunderflow下标循环不涉及每次移动后取模我最常看到的问题包括顺序栈忘记扩容直接越界写、循环队列的满判断写错导致覆盖旧数据、链栈忘记释放节点造成内存泄漏。这些坑几乎都会在第一次认真写的时候碰到所以我不建议大家直接拿IDE自动补全而是先手写一遍踩过一遍再谈优化。6.2 我调试栈和队列代码时的固定流程我自己调试这些基础结构时通常按三步走先写一个空结构的检查确认isEmpty和isFull逻辑与内存状态一致。再制造单元素场景验证push一次再pop一次结构能回到初始状态。最后做压力测试比如十万次push和pop交替用随机数校验每次弹出的数据是否符合预期。如果是循环队列我会特意在容量刚好为1和容量为2的时候测试因为取模运算在最小边界最容易出错。这些年我的体会是数据结构的问题大多不是算法复杂度太高而是边界处理不够严格。栈和队列已经是最简单的结构如果你能把它们的每个分支条件、每个下标变化都说到清清楚楚后面的树、图、堆这些复杂结构会顺畅得多。6.3 工程语言里的栈和队列别重复造轮子C语言由于缺少标准库容器自己写一遍很有必要。到了日常业务开发我一般不会手写。Java里用ArrayDeque代表栈或队列官方文档也推荐用它而不是StackPython里直接用list当栈队列可以用collections.dequeGo的container/list和切片也可以应付常见场景。自己实现的版本主要用于学习、面试手写和特殊性能优化比如需要精确控制内存或者做无锁并发队列时才需要回到更底层去折腾。最后再分享一个我在实际写代码时养成的习惯只要实现了栈或队列先给它写一组独立的测试用例固定输入、固定输出跑通过再继续下一个功能。基础容器是很多逻辑的地基它一旦有bug往上叠加的业务逻辑会全错而且错得莫名其妙排查成本极高。宁可在这上面多花十分钟也不要等到线上出问题再回头看指针和边界。