实现队列所需的最小栈数量是多少？能否用单个栈实现？

核心结论 #

• 若要求均摊O(1)时间复杂度的队列实现，最少需要2个栈；
• 若允许牺牲时间复杂度（出队操作O(n)），仅用1个栈也能实现队列，你提到的递归反转栈的方案完全可行。

一、2个栈实现队列（最优性能方案） #

这是工业界常用的标准实现，用两个栈拆分入队和出队逻辑：

• 入队（enqueue）：直接将元素压入「入栈」，对应栈的push操作，时间复杂度O(1)；
• 出队（dequeue）：如果「出栈」为空，就把入栈的所有元素依次弹出并压入出栈（相当于反转元素顺序，把队首元素移到出栈栈顶），然后弹出出栈栈顶；如果出栈不为空，直接弹出栈顶。
  每个元素最多被压入和弹出两次，因此均摊时间复杂度为O(1)，空间复杂度O(n)。

二、单栈实现队列（递归反转方案） #

仅用1个栈实现队列的核心思路，是利用递归的调用栈来模拟第二个栈的暂存功能，具体操作如下：

入队操作 #

完全等价于栈的push操作，直接把元素压入栈即可，时间复杂度O(1)。

出队操作 #

通过递归遍历栈，先弹出所有元素到调用栈暂存，直到拿到栈底元素（队列的队首），再把暂存的元素重新压回原栈：

1. 若栈为空，抛出空队列异常；
2. 弹出栈顶元素并暂存；
3. 如果此时栈已空，直接返回该暂存元素（这就是队首）；
4. 否则递归调用出队操作，获取真正的队首元素；
5. 将暂存的元素重新压回原栈；
6. 返回递归得到的队首元素。

这种方式每次出队需要遍历整个栈两次（弹出+压回），时间复杂度为O(n)，但确实能仅用1个栈实现队列的所有功能。

伪代码示例 #

class QueueWithSingleStack:
    def __init__(self):
        self.stack = []
    
    def enqueue(self, item):
        self.stack.append(item)
    
    def dequeue(self):
        if not self.stack:
            raise IndexError("Queue is empty")
        top = self.stack.pop()
        # 栈为空时，当前top就是队首
        if not self.stack:
            return top
        # 递归获取队首
        front = self.dequeue()
        # 把暂存的元素放回栈
        self.stack.append(top)
        return front

内容的提问来源于stack exchange，提问作者Tharun Vemula