1. 为什么栈和队列值得单独开一个专题day10的内容在很多人看来是最不起眼的一天。数组、链表都学过了栈和队列不就是两个限定存取顺序的容器吗好像没什么可讲的。但如果你真的这么想后面刷题会吃不少亏——栈和队列不是简单的数据结构知识点它们是解决一大类问题的思维工具而且在笔试面试里出现频率极高。我先说一下实际情况。代码随想录训练营把栈和队列单独拉出来做好几天不是因为题目难而是因为这玩意儿太容易被低估。很多人一看到用栈实现队列用队列实现栈就开始笑——这不就是互相套壳吗结果自己动手一写各种边界处理不好、返回值搞错、判空顺序颠倒跑起来一堆bug。我见过不止一个刷了上百题的人在这两道入门题上卡了半小时。所以day10的第一天专题核心解决三件事搞清楚栈和队列的本质区别它们不是正着放和倒着放的区别而是适用场景的区别。掌握底层实现的思路数组和链表怎么模拟栈和队列标准库的栈和队列底层到底长什么样。彻底吃透LeetCode 232用栈实现队列和LeetCode 225用队列实现栈这两道题因为这两道题背后的双栈翻转和队列旋转思路是后续一堆进阶题的地基。这一篇适合两类人一类是刚入坑算法训练营、正在按计划刷题的初学者另一类是刷了一阵子题但老觉得栈和队列相关的应用场景很模糊、看到题目不知道用栈还是用队列的人。我尽量把底层逻辑讲透也把我自己踩过的坑放进去。2. 先进后出和先进先出只是表象关键是看场景2.1 栈的本质处理最近关联的状态很多人背栈的特性就一句话后进先出LIFO。背完就完了做题的时候还是不知道什么时候用。我的理解方式是换一个角度栈擅长处理最新的东西优先被处理的场景。举一个生活中最常见的例子——函数调用。你写代码的时候函数A调用函数BB调用函数C。C先执行完返回然后B执行完返回最后A才结束。这个后调用的函数先返回的过程靠的是什么就是系统维护的一个调用栈。每进入一个函数就把当前状态压栈每返回一个函数就弹栈。这也是为什么崩溃日志里经常有stack trace栈回溯/backtrace——因为系统只需要沿着栈一路往上弹就能还原出完整的调用链。从这个例子能看出栈的典型用途需要暂时保存现场、稍后再恢复。刷题里对应的场景就是括号匹配遇到左括号压栈遇到右括号弹栈天然匹配最近遇到的左括号。撤销操作编辑器里的undo永远是撤销最近一步而不是第一步。函数递归本质就是栈所以递归转迭代经常要自己显式开一个栈。2.2 队列的本质处理顺序调度的问题队列和栈正好相反它的核心是先进先出FIFO。它的核心场景是排队处理——先来的人先被服务这个直觉人人都懂。但刷题的时候队列比栈更容易被忽略因为它的应用场景在题目里藏得比较深。最常见的例子是树的层序遍历你要一层一层地输出二叉树每一层的节点先进队列处理完一层再处理下一层这时队列就是最自然的选择。还有BFS广度优先搜索——从起点出发逐层向外扩散每一层的候选节点依次入队先入队的先处理。这些东西本质上都是按照到达的顺序依次处理。所以我对栈和队列的总结就两句话栈处理最近状态遇到问题想最新信息优先用栈。队列处理先后顺序遇到问题想谁先来谁先干活用队列。2.3 底层实现的两个标准答案面试的时候有一道很常见的变形题用数组模拟一个栈、用数组模拟一个队列。很多人觉得这有什么好问的但真到写起来队列比栈麻烦不少因为数组的头部弹出是O(n)操作这是所有队列实现的痛点。先说栈。用数组模拟栈非常简单只需要维护一个top指针指向栈顶元素的位置class MyStackArray { private: vectorint data; public: void push(int x) { data.push_back(x); } int pop() { int res data.back(); data.pop_back(); return res; } int top() { return data.back(); } bool empty() { return data.empty(); } };因为栈的插入和删除都发生在同一端数组的尾部操作就是O(1)所以栈用数组实现是最顺的。队列就不一样了。如果你用数组普通实现队头在数组下标0的位置每次出队都要把所有元素往前挪变成O(n)。所以工程上要么用循环数组环形队列要么用链表来实现队列。环行队列的思路很有意思把数组看成首尾相接的环维护一个head队头和一个tail队尾tail指向下一个入队的位置。当tail走到数组末尾时如果数组头部有空位就绕回到下标0继续用。template typename T class CircularQueue { private: vectorT data; int head 0; int tail 0; int count 0; // 实际元素数量 int capacity; public: CircularQueue(int cap) : data(cap), capacity(cap) {} bool enqueue(T val) { if (count capacity) return false; // 队列已满 data[tail] val; tail (tail 1) % capacity; count; return true; } bool dequeue(T val) { if (count 0) return false; // 队列为空 val data[head]; head (head 1) % capacity; count--; return true; } };这里的关键是用count来区分空和满。如果不用count只用head和tail那么空队列和满队列的head tail就产生二义性了。所以实际工程里要么像上面这样用count计数要么牺牲一个数组位置来区分两种状态。这个环形队列的思路在操作系统里有大量应用比如CPU任务调度里的就绪队列、输入缓冲区等。面试时如果被问到怎么设计一个高性能的队列能讲出环形队列的思路会比只说一个链表要加分。3. LeetCode 232 用栈实现队列双栈翻转的核心思路3.1 为什么要用两个栈先想一个基础问题用一个栈能不能实现队列答案是不能。因为栈只能从顶部存取元素而队列要求从底部队头出队。举个直观的例子你把1、2、3依次压入栈栈顶是3。队列要求先出队的应该是1但栈里1在最低层取不出来。所以关键问题是**如何把栈里的底变成顶**答案就是再拿一个栈把第一个栈的元素全部倒出来。第一个栈的栈底到了第二个栈就变成了栈顶。这就是双栈翻转的核心思想。两个栈的分工很明确输入栈inStack专门负责入队操作push直接把元素放进来。输出栈outStack专门负责出队操作pop/peek时从输出栈取。只有一种情况需要做翻转输出栈为空的时候。这时把输入栈的所有元素一次性倒进输出栈所有元素的顺序就正好反过来了。这里我强烈建议自己动手画一下。你用笔在纸上画两个栈往inStack里依次压入1、2、3然后把inStack里的元素依次弹出并压入outStack——1、2、3会依次从inStack弹出压入outStack后outStack的栈顶就是1。此时对outStack执行pop得到的就是1完美符合队列的出队顺序。3.2 完整实现push、pop、peek、empty直接看我写好的实现这里我用了C演示逻辑和代码随想录里的版本一致class MyQueue { private: stackint inStack; // 输入栈 stackint outStack; // 输出栈 void inToOut() { // 只有当输出栈为空时才需要倒数据 if (outStack.empty()) { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } } public: void push(int x) { inStack.push(x); } int pop() { inToOut(); // 确保输出栈里有数据 int res outStack.top(); outStack.pop(); return res; } int peek() { inToOut(); return outStack.top(); } bool empty() { return inStack.empty() outStack.empty(); } };这里有一个非常关键的细节inToOut只在outStack为空时执行。为什么因为你不能每次都倒。假设先压入1、2、3然后执行一次pop这时候outStack里还剩2、3。如果下一次pop之前又把inStack的新元素倒了进来比如push了42和4的顺序就会在outStack里变成4在上、2在下弹出顺序变成了4、2——这就错了。所以每次出队优先消费outStack里已有的元素outStack彻底空了才去inStack进货。整个过程只有第一个元素需要经过一次完整的倒腾后面每个元素都只进栈一次、出栈一次均摊下来是O(1)时间复杂度。这个均摊O(1)的概念面试的时候很值得提一下。3.3 踩坑记录peek和pop别互相调用我第一次写这个题的时候图省事在peek里直接调用pop再把结果压回去int peek() { int res pop(); inStack.push(res); return res; }看起来没问题但这是个隐蔽的坑。pop内部执行了inToOut()如果你在一个outStack已经非空、且inStack里有新元素的情况下调用peek执行完pop后新元素已经被倒到outStack里了然后你又把弹出的值压回到了inStack。下一次pop时因为outStack不为空不会触发inToOut于是队列的弹出顺序就乱了。正确做法是让peek和pop共享inToOut但peek只取栈顶不弹栈。后来我写题总结了一个原则公共的逻辑抽出来但不要用调用另一个操作再回滚的方式去复用那样一定会引入状态副作用。4. LeetCode 225 用队列实现栈单队列旋转的巧妙解法4.1 两个队列的笨办法和单队列的聪明办法用队列实现栈比用栈实现队列要多想一层。直观上拿两个队列入栈时把元素放进非空的队列出栈时把队列前n-1个元素搬到另一个队列剩下的最后一个就是要弹出的栈顶元素。这个办法能解但要维护两个队列的状态代码里到处是哪个队列当前有数据的判断啰嗦。更优雅的办法是只用一个队列配合旋转操作。每次push的时候先把新元素入队然后把队列中前面所有元素依次出队再重新入队到队尾。这样新元素就被转到了队首。下次pop直接从队首弹即可。举个例子来理解队列一开始是[1]。push 2队列变成[1, 2]把前面的1挪到队尾变成[2, 1]。现在队首是2栈顶也是2。push 3队列变成[2, 1, 3]把前面的2和1依次挪到队尾变成[3, 2, 1]。队首是3栈顶也是3。完美对应了后进先出的顺序。4.2 实现代码push复杂、pop简单class MyStack { private: queueint q; public: void push(int x) { q.push(x); // 将前面的元素依次挪到队尾让新元素变成队首 int size q.size(); for (int i 0; i size - 1; i) { q.push(q.front()); q.pop(); } } int pop() { int res q.front(); q.pop(); return res; } int top() { return q.front(); } bool empty() { return q.empty(); } };注意一下时间复杂度push是O(n)因为每次都要做n-1次移动pop是O(1)直接从队首拿。这个设计非常典型——牺牲写操作的时间换取读/删操作的高效率。实际应用里如果读操作远多于写操作这个方案就很划算。这也是做题需要考虑的点数据结构的设计永远在操作开销之间做取舍。4.3 与双栈翻转的对比一题教会你两种思路这两道题放在一起做非常有意思。它们都用了同一个底层思想通过倒腾一遍来改变元素的可见顺序但具体手法完全不同题目方法时间复杂度核心操作用栈实现队列两个栈输出栈为空时批量翻转pop/peek均摊O(1)push O(1)批量倒数据用队列实现栈一个队列push时旋转队首到队尾push O(n)pop/top O(1)逐个旋转双栈方案的精髓是延迟翻转——不是每次push都马上翻而是等到需要出队时一次性翻完。这样每个元素进出各一次均摊成本低。单队列方案的精髓是即时旋转——新元素进来马上转到队首保证栈顶永远在队首。这两道题做完我建议你合上书自己从零写一遍不要看任何参考。第一遍能写对算你赢我第一遍两题都出了bug。这类题就是要自己亲手折腾一遍才会真正理解为什么两个栈为什么一个队列就够了这种问题。5. 跳出题目栈和队列在系统底层到底是怎么用的5.1 函数调用栈与栈回溯前面提到过函数调用栈但值得展开讲。每一层函数调用发生时系统会把局部变量、返回地址、调用者环境等打包成一个栈帧压入调用栈函数返回时这个栈帧被弹出恢复执行现场。这个机制是所有可执行程序的运行地基。所以你在看崩溃日志时看到的stack trace本质就是沿着调用栈逐帧回溯从崩溃点一路往回把每一层函数的调用关系打印出来。这也是热词里backtrace栈回溯的由来。这里有个学习上的建议刷题刷到递归的时候脑子里要有这张调用栈的图。任何递归函数在系统底层都对应一个不断压栈和弹栈的过程。当递归深度过大时栈空间被耗尽就会出现栈溢出stack overflow。理解了这一点你就能明白为什么有些递归要改成循环显式栈——因为系统栈是有限的但你自己在堆上开的栈容量大得多。5.2 阻塞队列和线程池再看队列在工程里的真实角色。线程池的任务队列是最典型的例子线程池里的工作线程数目是有限的当提交的任务数量超过线程数量多余的任务就要排队。这个排队用的就是队列——更准确地说是阻塞队列Blocking Queue。阻塞队列和普通队列最大的区别是当队列为空时消费者线程执行take操作会被挂起阻塞直到有新元素入队才被唤醒当队列满时生产者线程执行put操作也会被阻塞直到队列有空位。这个自动挂起和唤醒的机制避免了线程空转是并发编程里非常关键的组件。常见的阻塞队列实现有几个各自对应不同的场景ArrayBlockingQueue基于数组的有界队列容量固定适合任务不能无限制堆积的场景。LinkedBlockingQueue基于链表的队列可选有界或无界吞吐量通常更高。SynchronousQueue没有任何内部缓冲生产者直接把任务递交给消费者线程适合不排队、立即交接的场景比如JDK的Executors.newCachedThreadPool()默认用的就是它。热词里还有消息队列重复消费问题。这类问题发生在分布式系统里下游服务从消息队列拉取消息处理成功后还没来得及提交确认ack就崩溃了消息被重新投递于是同一笔业务被处理了两次。解决思路通常是消费幂等——让重复执行和单次执行的结果一样比如用唯一业务ID去重。这个场景下的队列本质上和LeetCode里用两个队列模拟栈不一样它更强调异步解耦和削峰填谷生产者把消息丢进队列就跑了消费者按自己的节奏慢慢处理哪怕瞬时请求量很大也不至于把下游服务打爆。5.3 操作系统里的环形队列和中断处理前面实现的环形队列在操作系统底层无处不在。键盘输入缓冲区就是一个典型的环形队列你打字很快CPU没时间立刻处理每一个按键中断按键的扫描码就先放进缓冲区排队CPU忙完再从缓冲区读。缓冲区满了怎么办有些老系统会直接丢新按键或者发出嘟声提示——这就是为什么有时候你快速连续按键会漏掉几个。中断处理场景里还有栈的身影当一个优先级更高的中断到达时CPU需要暂停当前任务这个暂停现场也要压栈保存。处理完中断后从栈里弹出保存的现场恢复执行。不同中断级别甚至使用不同的中断栈避免栈被深层嵌套的中断挤爆。这就是热词里中断栈针的背景。说这些其实就是想强调一个观点栈和队列不是面试里才出现的东西它们就是操作系统、编程语言、框架组件每天都在用的基础机制。你把LeetCode 232和225吃透了再回头去看线程池原理、函数调用栈会有一种原来如此的通透感。6. 专题学习的节奏安排和几个进阶方向6.1 今天这个阶段你要掌握到什么程度day10的目标不是让你知道栈和队列而是要做到以下几点两个特性倒背如流栈LIFO、队列FIFO以及各自适合什么场景。两道经典题不看答案秒写232和225的代码能做到一次性通过无编译错误。明确C/Java标准库底层C里的std::stack和std::queue默认底层是std::deque因为双端队列同时支持两端操作可以灵活适配两种容器的语义你也可以通过模板参数指定用vector或list实现。Java里Stack类是历史遗留类性能一般推荐用Deque接口和ArrayDeque实现类来当栈用LinkedList当队列用。理解容器适配器这个词栈和队列在C标准库里不是独立的数据结构而是封装其他容器的适配器——它们不提供迭代器不能随机访问只能按各自规则存取元素。这就是为什么你没法用std::for_each遍历一个std::queue。6.2 下一个阶段会遇到什么括号匹配、逆波兰表达式、单调栈day10之后栈和队列专题会接着上强度我提前给你做个预告让你有个心理准备。括号匹配那类题LeetCode 20是栈最经典的用法扫描字符串遇左括号就压栈遇右括号就检查栈顶是否匹配。这个题目背后是一个通用思想——需要记住最近的一个未闭合项时用栈。不只括号XML/HTML标签闭合校验、编辑器里的代码块折叠全都有栈的影子。逆波兰表达式后缀表达式求值LeetCode 150也是栈的经典应用遍历表达式遇到数字压栈遇到运算符就从栈顶弹出两个数计算结果再压回。其实双栈翻转那一套思想在这里也有体现——逆波兰表达式之所以好用就是因为它天然消除了优先级判断的复杂性。再往后会碰到单调栈。单调栈是一个更强悍的栈形态栈内元素保持单调递增或递减它专门解决下一个更大元素海拔积水这类问题。比如热词里那个找下一个身高更高的小朋友就是典型的单调栈题。它依然是栈只是你在入栈前多做一步把破坏单调性的元素先弹出去。这个维护单调性的手法是从栈这个基础容器上长出来的高级技巧也是栈专题的最终boss之一。6.3 刷这个专题我建议你坚持的一个习惯最后分享一个实实在在的学习方法。我从day1刷到day10最大的体会是栈和队列这章光看是看不明白的必须动手画状态图。我所谓画状态图就是每当遇到一个用栈或队列的题目先用笔在纸上把入栈、出栈、入队、出队的每一步画出来。232这道题你就画两个栈手动模拟push 1、push 2、pop、push 3、pop、pop这六个操作225这道题你就画一个队列手动模拟每一次push时元素是怎么旋转的。画完一遍你对为什么这样设计的理解会超过看十篇题解。另外刷完232和225一定要追问自己一个如果如果peek操作特别频繁双栈方案还最优吗如果push操作特别频繁单队列的旋转实现会不会成为瓶颈如果栈的元素特别大用deque当底层容器比vector好在哪这些问题现在不一定要答上来但带着问题去学到后面学单调栈、学线程池的时候很多概念会自动串起来。数据结构的训练营练的从来不是背代码而是建立一套看着场景选工具的本能。栈和队列是这个本能的起点希望今天这篇能帮你把这个地基打牢。