训练营进入第10天题目开始从“你有一个数据结构怎么用它”转向“你用A造一个B”。今天的主题是栈与队列两道经典题目——232题用栈实现队列、225题用队列实现栈——几乎是所有算法面试必刷的组合拳。说实话这两道题我第一次做的时候代码能跑通但心里是虚的只知道“两个栈倒来倒去”能变出队列不知道为什么这样设计、为什么时间复杂度是O(1)、边界条件为什么这么写。这次跟着代码随想录重新梳理了一轮把栈和队列的底层关系、接口设计、复杂度分析一次性搞清楚记录下来。1. 先别急着写代码栈和队列其实是套装容器不是底层容器1.1 为什么C的stack和queue默认拿deque当底裤很多人学数据结构时有这么一个误区以为栈和队列和vector、list是平级的容器。实际上在C STL里stack和queue压根不是容器它们是容器适配器——自己不存数据而是包装一个底层容器只暴露特定的接口。说得直白点栈和队列就是给vector、deque、list这些底层容器换了一层皮肤把你不该用的操作全部禁掉。为什么默认底层是deque而不是vector因为deque双端队列同时支持头部和尾部的快速插入删除。栈只需要尾插尾删queue需要尾插头删vector在头部操作为O(n)list虽然两头都快但缓存不友好deque两头都是O(1)且内存区块连续是两边都不得罪的万金油。你甚至可以显式指定底层容器std::stackint, std::vectorint st; // 用vector当栈的底层 std::queueint, std::listint q; // 用list当队列的底层指定成vector之后栈依然能用因为vector有push_back和pop_back。这个事实说明了一个非常关键的点也是今天所有题目的出发点栈和队列的区别不在底层存储而在操作限制。vector既能当作栈用也能当作队列用代价是头部操作O(n)stack和queue只是把这种自由收走了。232题用栈实现队列本质就是一个受限制的vector怎么叠加出另一个方向的限制。1.2 三种主流语言里的栈和队列选型避坑刷题和实际工程不一样语言自带的容器设计各有历史包袱这里必须单独说清楚Cstd::stack、std::queue完整体验STL的适配器设计接口是push、pop、top/front、empty没有size以外的随机访问能力。注意stack的pop是void你要先top再pop。Java老手基本不用Stack类它继承自Vector所有方法带synchronized锁性能拉胯官方注释自己都说建议用Deque替代。正确姿势是用ArrayDequeDequeInteger stack new ArrayDeque(); // 栈 DequeInteger queue new ArrayDeque(); // 队列也可以ArrayDeque两头都能操作addLast/removeFirst就是队列addFirst/removeFirst就是栈。它不允许null这点和LinkedList不同。Python没有专门的栈或队列类list天然是栈append/pop做队列用collections.dequepopleft是O(1)。注意千万别用list.pop(0)模拟队列那是O(n)的灾难。这几种语言的差异提醒我们一件事刷题的时候别死记API要理解你手上这个容器的两头操作成本。理解了这一点后面看单调队列、优先队列的底层实现思路会顺畅很多。2. 232题用两个栈造队列输入栈和输出栈的分工是精髓2.1 负负得正为什么两次后进先出等于先进先出232题的常规解法是维护两个栈一个inStack负责接收push一个outStack负责输出pop和peek。核心思想用一句话概括顺序翻转两次等于没有翻转。栈是后进先出元素按1、2、3的顺序压栈弹出顺序是3、2、1。如果你把弹出的3、2、1再压进第二个栈弹出顺序又变回1、2、3。这和负负得正是一个道理栈的逆序操作执行两次就抵消了。实际操作上所有push都进inStackinStack里栈顶是最后进入的元素。当需要pop时把inStack里的元素全部倒进outStackoutStack的栈顶变成了最早进入的元素pop它就是队首。等到outStack空了再从inStack倒一批货过来。这里有一个非常关键的细节也是很多人写错的地方倒元素的前提是outStack为空。如果outStack里还有存货就直接从outStack的栈顶pop绝对不能先把inStack倒过来再pop否则顺序就会乱。举个例子先后push(1)、push(2)然后pop一次——此时outStack里有[1, 2]2在栈顶pop得到2。如果你不判断outStack非空就直接倒inStack假设先push(3)outStack变成[1, 2, 3]pop得到3这就错了——正确队列的队首明明是1。所以必须先清空outStack的存货再倒新货。2.2 完整实现和摊还复杂度为什么均摊是O(1)C实现如下class MyQueue { private: stackint inStack, outStack; void transfer() { if (outStack.empty()) { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } } public: MyQueue() {} void push(int x) { inStack.push(x); } int pop() { transfer(); int val outStack.top(); outStack.pop(); return val; } int peek() { transfer(); return outStack.top(); } bool empty() { return inStack.empty() outStack.empty(); } };很多人在peek这里偷懒直接写return pop()但这样会弹出一个元素不符合peek的语义。要么像上面这样单独写要么可以复用逻辑但记住把弹出的值再push回去有点画蛇添足。我觉得单独维护一个transfer函数是最好的做法因为pop和peek的公共逻辑就是保证outStack不为空。时间复杂度这块网上很多讲解一笔带过我这次仔细想了一遍。单次pop最坏情况是O(n)——比如你连续push了n个元素之后第一次pop要把n个元素全部倒到outStack。但均摊复杂度是O(1)每个元素进inStack一次最多被倒到outStack一次再从outStack弹出一次每个元素在整个生命周期里贡献3次常数操作n次push加上n次pop一共O(3n)次操作均摊到每次操作就是O(1)。这就是摊还分析的标准案例和动态数组扩容时的均摊分析思路完全一致。2.3 empty的判断别踩坑两个栈都得查empty的判断是另一个高频踩坑点。有人只查inStack.empty()以为所有元素都在inStack里这显然忽略了outStack里的存货。有人只查outStack.empty()觉得队列的出口空就是空队列同样不对——inStack里可能还躺着好几个元素没来得及倒呢。正确的判断是关系两个栈都为空才说明队列为空。这个简单的逻辑暴露了一个本质数据永远不会同时存在于两个栈中它要么在inStack等着被倒要么在outStack等着被取。两个栈合在一起才是一个完整队列。3. 225题用队列造栈一个队列版本远比两个队列版本优雅3.1 两个队列的备份法先建立直觉再优化上一题是两个栈倒来倒去这一题很多人下意识想那我也用两个队列倒来倒去呗。确实能做但思路完全不同。栈的pop要拿的是队尾元素而普通队列只能从队首出所以你必须把队尾元素暴露到队首。两个队列的版本是这样的q1存放数据q2当临时中转。push时直接进q1pop时把q1的前n-1个元素依次挪到q2这时q1剩下的最后一个就是栈顶弹出它然后交换q1和q2——这样q2里full了但交换之后q1继续存剩下的元素。class MyStack { private: queueint q1, q2; public: MyStack() {} void push(int x) { q1.push(x); } int pop() { while (q1.size() 1) { q2.push(q1.front()); q1.pop(); } int val q1.front(); q1.pop(); swap(q1, q2); return val; } int top() { while (q1.size() 1) { q2.push(q1.front()); q1.pop(); } int val q1.front(); q2.push(val); // 和pop不同top不弹但要帮你把最后一个也搬过去 q1.pop(); swap(q1, q2); return val; } bool empty() { return q1.empty() q2.empty(); } };这个版本的问题在于top也要O(n)——把n-1个元素搬走才能看到栈顶。而且代码写起来很容易漏掉top里的关键一步你要把那个val重新放回q2否则交换后栈里就少了一个元素。3.2 单队列的转圈法push时直接把栈顶转到队首后来我发现这个题有个非常优雅的单队列做法。思路极其简单每次push新元素之后把队列里除了新元素以外的所有元素依次出队、再入队让新元素变成队首。这样队列的队首永远是最后一个push进来的元素pop直接出队首就是栈顶。from collections import deque class MyStack: def __init__(self): self.q deque() def push(self, x: int) - None: self.q.append(x) # 把前面的元素全部搬到后面新元素就变成队首了 for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def pop(self) - int: return self.q.popleft() def top(self) - int: return self.q[0] def empty(self) - bool: return not self.q四行核心逻辑干净利落。用生活的比喻你在一家排队的餐厅插了个队但规则不允许于是你让排在前面的人全部绕到你后面重新排队这样你就变成了队伍第一个人。3.3 两个版本怎么选复杂度对比很多人纠结这个题该用单队列还是双队列。直接看表操作双队列单队列push时转圈pushO(1)直接入队O(n)需要搬n-1个元素popO(n)搬n-1个O(1)直接出队首topO(n)搬n-1个再看O(1)直接看队首空间两个队列但总元素还是n一个队列省一个容器有意思的是双队列版本把O(n)的成本放在pop/top上而单队列版本把成本挪到了push上。如果应用场景是push很少、pop和top很多单队列版本有优势反过来则是双队列版本好。很多算法题就是这样总成本没变但你可以根据实际场景调配成本发生的位置。这种推挤成本的思路在后面设计LRU缓存、LFU缓存时还会反复遇到。4. 第10天真正要练的是设计思维接口、边界与复杂度4.1 为什么力扣爱考这种互相实现的题做完这两道题我发现它们的价值不只在于让你熟悉栈和队列的API。这类用一个数据结构实现另一个的题目考察的是三个层次的能力第一层是接口语义的理解。队列是FIFO栈是LIFO如果你连这两个规则都拎不清题目根本无从下手。很多人上来就背代码背完就忘就是因为第一层没过。第二层是操作约束的转换。给定一个数据结构你手头只有它的几个操作。要在这些限制下实现目标行为本质上是用已有的指令集完成一个新的任务和汇编编程的思路很像。第三层是复杂度与边界的管理。同样是实现一个栈双队列版本和单队列版本的成本分布完全不同同样是实现一个队列忘记判断outStack为空就会让顺序错乱。能把这些讲清楚才说明真的理解了不是只记住了答案。4.2 边界条件和测例设计怎么发现自己写错了我平时刷题有个习惯光靠力扣的测试用例不够自己会额外设计几组边界用例。这两道题我强烈建议你手动过一遍这几组先全部push再全部pop比如push(1,2,3,4,5)然后连续pop五次检查顺序是不是1,2,3,4,5。交错push和poppush(1), push(2), pop(), push(3), pop(), pop()。这种倒货到一半又来新货的场景最容易踩outStack非空判断的坑。pop到空之后继续push再pop验证transfer之后outStack的全部元素都消耗完了才会触发新的transfer。空结构的empty检查新建对象直接调empty必须返回truepush一个再pop再调empty必须返回true。这些用例基本覆盖了代码里所有分支。我记得有次面试面试官让我解释为什么pop之后还能保证顺序我直接拿交错push的用例在白板上走了一遍当场把transfer触发时机画了出来面试官很明显满意了。4.3 均摊分析与最坏复杂度什么时候说O什么时候说θ这正好回应了之前看到的一个讨论计算算法复杂度时什么时候用O什么时候用θO是上界表示最多不超过多少θ是紧界表示不多不少就是这个量级。严格意义上我们说冒泡排序时间复杂度O(n²)是安全的因为n²确实是上界但它同时是θ(n²)。而哈希表查找是O(n)这句话也没错——最坏情况所有key冲突时确实是O(n)——但它给的信息太弱了因为平均和均摊是O(1)。232题摊还O(1)是一个典型的均摊分析场景单次pop最坏O(n)但n次连续pop的总成本是O(n)所以每次pop均摊O(1)。这里你要是说单次pop是O(n)从最坏角度讲也没错但面试官期待你给出的回答是均摊O(1)因为它捕捉到了设计的本质每个元素在整体操作序列中只被搬动常数次。4.4 中文站点讨论度高的细节坑盘点翻一些讨论区典型问题就那几个一是C里stack的pop返回void很多人写了int val st.pop()直接编译不过二是Java里用Stack类被面试官当场批评后改用Deque三是Python里用list.pop(0)模拟队列被问时间复杂度。这些问题看着小但都是不变量没把握住的表现。刷题训练营真正起作用的地方就是把这类细节反复锤到你形成肌肉记忆。5. 从LeetCode回到现实栈和队列在系统里无处不在5.1 栈在计算机底层的老本行栈帧与调用回溯题目刷完了不妨抬起头看看栈和队列在真实系统里的影子这会让今天的知识变得立体。栈最经典的场景就是函数调用。每次函数被调用操作系统会在调用栈上分配一个栈帧里面放着局部变量、参数、返回地址。函数嵌套调用时栈帧像叠盘子一样一层层往上叠函数返回时栈帧从上往下依次弹出。这就是为什么递归太深会栈溢出——盘子叠太高了。backtrace栈回溯也叫栈回溯就是利用调用栈的特性程序崩溃时顺着栈帧的链表结构反向回溯每一层调用点打印出调用路径。调试器里的调用堆栈窗口就是干这个的搞嵌入式的还会看中断栈帧和任务栈ARM平台上还有专门的栈回溯工具。可以说递归在语言层面是递归在运行层面就是栈操作。5.2 队列在并发世界里的角色阻塞队列、消息队列与线程池队列的核心价值在于解耦生产者与消费者的速度差。生产者产出一个消息消费者一时处理不过来队列就先把消息存起来。这就是阻塞队列存在的意义——当队列满的时候生产者阻塞等待当队列空的时候消费者阻塞等待两边的节奏被队列平滑掉。工程上更能体现这点的是消息队列。Kafka、RabbitMQ、RocketMQ的选型对比本质上都是围绕这个队列要不要持久化、要不要保证顺序、能扛多大吞吐、怎么处理重复消费展开的。线程池里的任务队列也一样Java的ThreadPoolExecutor允许你选不同阻塞队列LinkedBlockingQueue是无界队列、ArrayBlockingQueue是有界队列、SynchronousQueue是直接交接——选哪种队列决定了任务的排队策略也决定了拒绝策略什么时候触发。今天学的队列FIFO规则在并发场景下只是起点后面还要叠加上阻塞、优先级、持久化这些需求。5.3 后面训练营会遇到的两个进阶形态单调队列和优先队列栈和队列的基础版本搞定了后面两道经典题会刷新你的认知。一道是滑动窗口最大值标准解法用单调队列——队列里的元素保持单调递减每次窗口移动时从队尾弹出比新元素小的值、从队首弹出过期的最大值虽然内部做了大量淘汰队首始终是当前最大值。另一道是前K个高频元素用优先队列——本质是堆但可以理解为队首永远是优先级最高的元素的队列。到时候你就发现今天这种在限制内做文章的思维方式会比API本身值钱得多。第10天的内容复盘到这基本完整了。我个人做这两道题最大的体会是栈和队列的代码都短但真正难的是想清楚数据在什么条件下存在于哪个容器、一次操作到底要被搬几次。一开始写232题的时候我总想省掉transfer的判断结果交错操作直接bug后来把outStack空了才倒货当成不变量死死记住代码就再没出过错。建议你也试着给自己总结一句不变量贴在这两道题旁边比如232就是outStack只要非空栈顶一定是队列头225单队列就是push之后队首一定是最后一个入队的元素。带着不变量去做题比背代码有用得多。