用队列实现栈：双队列与单队列旋转法详解

在数据结构的经典题目里“用队列Queue实现栈Stack”算是很能检验基本功的一道。第一次拿到这道题的人反应大多是一脸问号队列先进先出栈后进先出这俩顺序天生相反怎么能用队列把栈模拟出来但只要耐下心把问题拆开会发现它既不玄乎也不繁琐考察的是对两种结构操作性质的理解以及一个非常朴素的核心思路——想办法让最新入队的元素变成下一次出队时最先被取走的那个。这道题常出现在各类算法课程、竞赛题和公司面试的题库里用来热身非常合适。我会把双队列的两种写法、单队列的旋转法、复杂度计算、边界测试和不同语言的API坑全部过一遍适合刚学数据结构的人也适合面试前想要系统复习的朋友。1. 题目解析FIFO 与 LIFO 的冲突点在哪1.1 队列与栈的核心差异队列的本质是FIFOFirst In First Out先进入的元素先离开。生活里最简单的类比就是排队买奶茶第一个人先拿到后面的人只能等。栈的本质是LIFOLast In First Out最后进入的元素最先离开。可以想象一叠放在桌上的盘子你放盘子的时候总是放在最上面拿的时候也只能先拿走最上面的。如果只从这两个定义看队列和栈似乎没有任何可以互相替代的可能。但要注意我们说的“用队列实现栈”并不是要改变队列的底层行为而是在队列提供的操作基础上设计一套调用顺序让外部观察到的是一个后进先出的语义。换句话说队列依然严格按照FIFO规则运行只是我们通过调度让“最新元素”在关键时候恰好出现在队首。1.2 这个题的难点不是“实现”而是“抽象”为什么非要限定用队列直接用数组或链表写一个栈不是更简单这个题目最初更多是数据结构与抽象数据类型教学里的训练假设你手里只有一份队列实现不允许访问它的内部存储只能调用enqueue、dequeue、peek等标准接口却要让所有调用者以为自己在用栈。这个过程训练的是接口隔离和抽象思维也正是现代工程里接口与实现分离的核心思想。再看一个现实原因很多公司面试拿这道题出来主要是想观察候选人在动手写代码之前能不能先分析出关键矛盾。如果你一上来就写数组模拟栈当然也能写对但没有理解到题目的核心考点如果你能先点出“队首是最老元素栈顶是最新元素所以必须让最新元素在出队时出现在队首”面试官会很明显感觉到你对数据结构是有认识的。2. 双队列实现两种方案两种取舍2.1 方案A让 push 付出代价pop/top 变成 O(1)用两个队列来做最常见的两个方案方向正好相反一个方案让push承担所有搬运成本另一个让pop承担所有搬运成本。先说方案A它的核心目标是让队列q1的队首始终对应栈顶这样pop和top操作就无比轻松代价是每次push都需要做一次全量搬运。具体步骤维护两个队列q1、q2。真实数据总是放在q1中q2只作为临时周转区。push(x)时先把x放入q2。再把q1中的所有元素依次出队并入队到q2。交换q1、q2。此时q1队首是x旧的元素全部排在x后面顺序和原来一致。pop()时直接从q1队首取出top同理empty判断q1是否为空。代码实现如下from collections import deque class MyStackA: def __init__(self): self.q1 deque() self.q2 deque() def push(self, x: int) - None: self.q2.append(x) while self.q1: self.q2.append(self.q1.popleft()) self.q1, self.q2 self.q2, self.q1 def pop(self) - int: return self.q1.popleft() def top(self) - int: return self.q1[0] def empty(self) - bool: return not self.q1这段代码里最让人容易忽略的是最后一步交换引用。很多初学者会忘记swap导致后一次push又把元素搬回旧队列顺序彻底乱掉。交换之后q2一定是空的因为旧元素和新元素全部被搬到了q1q2只是记录了之前的q1引用而之前的q1已经被搬空。复杂度上push里第一步O(1)第二步需要处理当前q1中所有n个元素每个元素出队并入队是O(1)所以单次push是O(n)。pop、top、empty都是O(1)。连续n次push后的总操作次数接近n(n-1)/2均摊到每次push仍然是O(n)这个方案在push频繁的场景下并不理想。2.2 方案Bpush 保持 O(1)pop/top 承担搬运成本方案B换一个思路push直接进队列让数据保持自然队列顺序队首是最早进入的队尾是最新进入的。既然栈顶对应队尾那pop时就需要找到队尾。但因为队列只能从队首弹出队尾不能在O(1)时间内弹出只能把队首的一批旧元素先挪走让队尾暴露出来。具体步骤push(x)直接入队到q1。pop时把q1中除了最后一个元素之外的所有元素搬到q2。此时q1只剩下最新元素也就是栈顶出队返回。交换q1、q2让剩余元素回到q1。top操作不能真的把元素弹出所以要么把最后元素取出来再重新放回去要么在支持查看队尾的语言里直接读取队尾。代码实现如下from collections import deque class MyStackB: def __init__(self): self.q1 deque() self.q2 deque() def push(self, x: int) - None: self.q1.append(x) def pop(self) - int: while len(self.q1) 1: self.q2.append(self.q1.popleft()) top self.q1.popleft() self.q1, self.q2 self.q2, self.q1 return top def top(self) - int: while len(self.q1) 1: self.q2.append(self.q1.popleft()) top self.q1.popleft() self.q2.append(top) self.q1, self.q2 self.q2, self.q1 return top def empty(self) - bool: return not self.q1这个版本的top写得稍微绕一点但核心思路清楚先把前n-1个旧元素搬到q2让队尾元素暴露出来取出它之后原样放回q2的队尾再交换回来。这样栈数据顺序不会被破坏。复杂度上push是O(1)pop和top是O(n)。如果队列容量很大且pop频繁这个方案会明显比方案A慢。但它也有自己的价值当插入操作是主流、弹出操作很少时push的常数级开销非常诱人。2.3 这两个双队列方案怎么选方案pushpoptopempty空间方案AO(n)O(1)O(1)O(1)O(n)方案BO(1)O(n)O(n)O(1)O(n)从表格可以看得很清楚两个方案没有绝对优劣只是把“昂贵操作”放到了不同位置。如果业务场景里几乎只push、偶尔pop方案B明显更划算如果pop/top频繁方案A更合理。但在纯算法题的评测环境下两者均摊复杂度差不多都能通过关键是你要能讲清楚为什么做这个取舍。还有一种常见面试追问是“能不能只用一个队列实现”这其实就是下面要说的旋转法。3. 单队列实现旋转大法一步到位3.1 核心技巧把新元素“转”到队首用两个队列确实能解决问题但细心的人会问第二个队列是不是必须的答案是否定的。我们完全可以只用一个队列配合一个“旋转”操作达到同样的效果。具体做法每次push时先把x正常入队到队尾然后把队列中除了x之外的旧元素一个一个出队再重新入队。每进行一次这样的操作队首元素就被换到了队尾新元素x则向队首方向移动一格。反复执行n-1次后x就从队尾移动到了队首而其他旧元素的相对顺序保持不变。这就等价于把整个队列绕了一圈新来的元素被转到最前面。可以类比转盘餐厅里那桌旋转小菜新出的菜刚放上去时离你最远但只要餐桌转一圈它就会转到你面前。我们这里的“旋转”操作就是主动把队列从头到尾转一圈让新元素停在队首。3.2 代码实现from collections import deque class MyStackSingle: def __init__(self): self.q deque() def push(self, x: int) - None: self.q.append(x) n len(self.q) - 1 for _ in range(n): 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代码非常短核心就三行先入队记录需要旋转的次数然后循环把队首搬到队尾。这里把len(self.q) - 1先存到变量n里是为了避免有人在循环里额外改动队列长度后产生误解其实在Python里range参数在循环开始时只求值一次直接写也安全但先存起来更清晰。3.3 为什么循环次数必须是 len(q)-1以队列初始为[1,2,3]为例模拟一次push(4)的过程操作队列内容队首在左初始[1, 2, 3]push(4)之后[1, 2, 3, 4]第1次旋转[2, 3, 4, 1]第2次旋转[3, 4, 1, 2]第3次旋转[4, 1, 2, 3]从表里可以清楚看到第3次旋转后新元素4已经到了队首此时立刻停止整个队列的弹出顺序就是4、1、2、3对应一个“栈顶为4”的栈。如果旋转次数写成len(q)也就是转4次队列会回到[1,2,3,4]新元素又跑回队尾等于白做了。更危险的是有些实现会写成while temp 0但每次旋转后队列长度不变temp不会自动减少容易造成死循环或者顺序错乱。所以请一定记住旋转次数是当前队列长度减1也就是旧元素的数量。3.4 单队列与双队列的本质关系单队列版本本质上是方案A的精简版方案A先把旧元素搬到q2再通过交换引用的方式让它们集中在q1单队列版本直接通过旋转完成同样的排列。两者的时间复杂度一样空间上单队列省一个队列对象代码也更短。不过双队列方案更容易向别人证明操作的正确性因为它的搬运动作一目了然单队列的旋转看起来更“机灵”也更容易在边界条件上翻车。面试的时候如果时间宽裕可以先讲双队列方案再主动补一句“其实还可以只用一个队列用旋转的方式实现”会加分不少。4. 复杂度推导与正确性验证4.1 时间复杂度的严谨推导单队列版本push的最坏情况是O(n)pop、top、empty是O(1)。空间复杂度O(n)只算存储n个元素的队列本身不算辅助空间。很多人以为“均摊后能达到O(1)”这是不成立的。每个新元素入栈时都要把现有元素全部转一遍如果是连续n次push总旋转次数是012...(n-1)n(n-1)/2均摊到每次push仍是O(n)。所以这个数据结构和语言内置栈相比没有任何性能优势它的价值在于抽象转换而不是替代原生栈。同理双队列方案A和单队列都是push为O(n)双队列方案B是pop为O(n)。不管怎么设计至少有一个操作要付出O(n)的代价。原因也很直白FIFO和LIFO之间的“反转”需要把一部分元素重新排列而这个重排动作本身就是线性的。想两头都是O(1)在只允许队列操作的前提下做不到。4.2 用随机测试验证栈行为光看代码容易自我感觉良好真正能发现隐藏bug的是随机对比测试。用上面任意一个类作为栈实现再配合一个Python列表模拟原生栈随机执行push、pop、top然后对比结果。import random from collections import deque def random_test(times10000): s MyStackSingle() ref [] for _ in range(times): op random.choice([push, pop, top]) if op push: x random.randint(-100, 100) s.push(x) ref.append(x) elif op pop: if ref: assert s.pop() ref.pop() else: if ref: assert s.top() ref[-1] print(random test passed) random_test()这段测试能覆盖很多手写用例想不到的交替操作场景。只要出现顺序问题assert基本立刻就会报错。运行结果如果正常输出“random test passed”说明栈的语义在绝大多数随机操作下都符合预期。4.3 常见边界场景除了随机测试固定边界场景也要单独验证。空栈调用pop/top应当抛出异常或者按设计返回一个特殊值但最怕的是不检查空栈直接访问队首导致错误时机不明确。只push一个元素后top/pop必须能正常返回这个唯一元素。push多个后连续pop预期完全逆序输出。比如push(1)、push(2)、push(3)然后连续pop三次得到3、2、1。交替操作比如push(1)、push(2)、pop()返回2、push(3)、top()返回3、pop()返回3、pop()返回1。大量元素操作可以用循环push几千个元素再全部pop防止旋转次数写错导致元素重复或顺序错误。这些场景加起来基本能覆盖实现里所有的分支和边界条件。5. 实操中容易踩的坑语言 API 与逻辑细节5.1 Python 别把 list 当队列如果你用Python实现最自然的想法可能是直接list.appendlist.pop(0)。功能上能跑但list的pop(0)会把后面的所有元素向前挪代价是O(n)整个实现会变成O(n^2)甚至更糟。正确姿势是用collections.deque它是双端队列队首出队是O(1)。另一个容易混淆的是queue.Queue。这个类适合多线程场景内部有锁算法题里用它会引入不必要的开销。所以标准写法永远是from collections import deque无论算法竞赛还是面试手写都非常稳。5.2 Java 中 ArrayDeque 与 LinkedList 的选择Java的Stack类官方已经不建议使用更推荐Deque接口。如果用队列实现栈可以选LinkedList或ArrayDeque。ArrayDeque底层是循环数组操作效率高但它不允许null元素LinkedList虽然稍慢但允许null。如果题目允许向栈里放null就选LinkedList否则ArrayDeque更合适。接口层面建议用offer/poll/peek而不是add/remove/push因为前者在失败时返回null或false后者会抛异常。尤其在做空栈判断时用peek检查队首元素是否为null再用poll弹出代码更安全。另外不要为了图方便在Deque上直接同时用栈方法和队列方法那样虽然也能实现功能却没达到题目“只用队列操作”的约束会被面试官扣分。5.3 C 中 std::queue 的坑C的std::queue包装了底层容器提供push、pop、front、back、empty这些方法。最大的坑是pop()不返回元素你需要先int top q.front(); q.pop();。很多从Python或Java转过来的朋友容易直接写q.pop()取值直接编译不过。另一点是std::queue本身是容器适配器默认底层是deque。queue的back()允许O(1)查看队尾这对方案B的top实现很有帮助可以直接返回队尾元素而不需要把整个队列搬一遍。但需要注意如果底层被换成不支持back的容器就不能这么用了。5.4 常见的逻辑错误速查表现象可能原因处理方式push后序列没有反转忘记交换队列引用或者旋转次数写错检查方案A的swap检查单队列的len-1pop返回最早进入的元素数据顺序没有维护成栈序回到“队首等于栈顶”的不变量重新推导空栈时行为不符合预期没有检查empty就开始pop/top在pop/top前加空栈判断并统一抛错单队列版本死循环旋转条件用while size 0且size不变改用固定次数for _ in range(len(q)-1)测试超时用list.popleft()或list.pop(0)模拟队列换成collections.dequetop之后元素消失top里直接调用了pop而没有放回top操作后必须把取出的元素重新入队6. 这个算法题背后的工程思维6.1 适配器模式队列包栈很常见用队列实现栈本质上就是适配器模式的一次微型演练外部只暴露push/pop/top/empty四个方法内部却用另一个结构的操作去满足这个接口的语义。工程里这种“包一层”的场景非常多比如老系统只提供FIFO消息队列新业务流程却要求最新任务优先处理最省事的就是写一个薄薄的适配层拦截插入逻辑把元素调整到队首。这个方案当然没有优先队列高效但在数据量不大、不想引入额外依赖的时候非常实用。栈和队列联合使用也很常见深度优先搜索用栈广度优先搜索用队列很多框架把待处理任务放在队列里处理过程中又用栈记录回溯路径。理解结构之间的转换可以帮你在遇到类似需求时多一个思路而不是只会盯着特定容器的文档。6.2 “维护不变量”才是算法学习的真正收获这个题最大的收获不是会背代码而是学会用不变量来约束实现。比如双队列方案A的不变量是“q1队首永远等于栈顶”方案B的不变量是“q1的队尾永远等于栈顶”单队列版本的不变量是“队列队首永远等于栈顶”。代码维护的是这条不变量而不是某个临时状态。写任何结构转换题先问自己每一步操作之后我要保证哪一条性质成立思路会清晰很多。类似的ADT转换题还有很多比如用两个栈实现队列、用数组实现循环队列、用栈实现表达式求值等。把队列实现栈这个例子琢磨透了再见到其他容器转换题时你就有了一套可复用的分析框架。我自己在给别人讲这道题时最常说的一句话是别急着写代码先搞清楚你希望“最新来的元素”最终站在哪个位置。队列实现栈看似只是个练习题但它逼着你去思考操作顺序和排列这种习惯放到系统设计里同样重要。如果你能自己把双队列两种方案和单队列旋转法都写一遍再把边界情况全部跑通以后再碰到类似的结构转换题心里就不会发慌了。