单个栈无法模拟队列,因lifo与fifo本质冲突;必须用两个栈:instack存新元素,outstack提供翻转后的fifo访问,仅当outstack为空时才将instack全部转移过去。

为什么不能直接用一个栈模拟队列
栈是后进先出(LIFO),队列是先进先出(FIFO),单个栈无法反转元素顺序。必须借助第二个栈做“翻转缓冲”——把入队元素暂存,等出队时再整体倒出来,让最早入栈的变成最先弹出的。
push() 只往 inStack 压,别动 outStack
所有新元素统一压入 inStack,保持插入顺序。此时 outStack 仍为空或含已翻转好的待出队元素。不要在 push() 里触发转移逻辑,否则会破坏顺序、增加冗余操作。
-
inStack.push(x)即可,无需检查outStack状态 - 即使
outStack非空,也绝不把新元素塞进去——那会打乱 FIFO 时序 - 性能上:
push()保持 O(1) 均摊时间复杂度
pop() 和 front() 必须先检查 outStack 是否为空
这是最容易出错的地方:不判空就直接从 outStack 取,会导致空栈访问(std::stack::top() 或 pop() 行为未定义)。
- 若
outStack为空,需把inStack全部弹出并压入outStack—— 这次翻转让最老元素落到outStack栈顶 - 若
outStack非空,直接操作它,inStack不参与 - 注意:翻转只在
outStack空时批量做一次,不是每次pop()都全量搬运
示例关键逻辑:
if (outStack.empty()) {
while (!inStack.empty()) {
outStack.push(inStack.top());
inStack.pop();
}
}
// 此时 outStack 一定非空(除非整个队列为空)
return outStack.top(); // 或 pop()
空队列判断要同时检查两个栈
队列为空当且仅当 inStack 和 outStack 都为空。只看其中一个会误判:比如 inStack 有数据但还没触发翻转,outStack 是空的,此时队列显然非空。
- 实现
empty()时必须写成inStack.empty() && outStack.empty() - 如果省略这个联合判断,
pop()前的空栈检查可能漏掉inStack里的待翻转数据,导致逻辑崩溃 - 某些边界场景(如连续
push后立刻empty())会暴露这个问题
真正麻烦的不是代码量,而是翻转时机和空栈状态的耦合——多线程下还要加锁,但单线程里最容易栽在“忘了判 outStack 空就去取”。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











