题解 | #用两个栈实现队列#

题目链接

用两个栈实现队列

题目描述

请你用两个栈来实现一个队列，支持 push（在队列尾部插入元素）和 pop（在队列头部删除元素）两种操作。

你需要在一个类中实现这两个方法，并处理一系列的操作。

输入描述: 一个字符串数组，每个字符串代表一个操作。例如 "PSH1" 表示将整数 1 push 进队列，"POP" 表示从队列中 pop 一个元素。

输出描述: 对于每个 "POP" 操作，将弹出的元素依次用逗号隔开，形成一个字符串输出。

示例输入: ["PSH1","PSH2","POP","POP"] 输出: 1,2

解题思路

这个问题的核心在于理解栈（LIFO, Last-In-First-Out）和队列（FIFO, First-In-First-Out）的特性差异，并用两个栈来模拟出队列的行为。

我们可以指定一个栈 stack1 专门用于入队（push），另一个栈 stack2 专门用于出队（pop）。

push 操作:
- 当需要将一个元素 node 入队时，我们始终将其压入 stack1。这个操作非常简单，直接利用栈的 push 方法即可。
pop 操作:
- 当需要从队列头部弹出一个元素时，我们期望得到的是最早进入的元素。这个元素应该位于 stack1 的底部。直接从 stack1 弹出是不行的，因为那会得到最后进入的元素。
- 这时，stack2 就派上用场了。
- 首先，检查 stack2 是否为空。
  - 如果 stack2 不为空，那么 stack2 的栈顶元素就是我们想要的队列头部元素（因为它是在之前某次 "倒腾" 时最早进入 stack1 的）。我们直接从 stack2 弹出并返回即可。
  - 如果 stack2 为空，我们就需要从 stack1 "补充" 元素。我们将 stack1 中的所有元素逐个弹出，并压入 stack2。当 stack1 被清空后，原本在 stack1 底部的元素现在就成了 stack2 的栈顶元素。这个过程巧妙地逆转了元素的顺序，实现了从 LIFO 到 FIFO 的转换。
- 完成上述 "倒腾" 后（如果需要），stack2 的栈顶就是队列的头部，我们弹出并返回它。

通过这种方式，我们利用 stack1 作为入口缓冲，利用 stack2 作为出口缓冲，实现了队列的先进先出特性。每个元素最多被 push 进 stack1 一次，pop出 stack1 一次，push 进 stack2 一次，pop 出 stack2 一次。因此，虽然 pop 操作单次可能耗时较长（在需要 "倒腾" 时），但其摊还时间复杂度是 $\mathcal{O}(1)$ 。

代码

cpp
java
python

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int val = stack2.top();
        stack2.pop();
        return val;
    }

private:
    std::stack<int> stack1;
    std::stack<int> stack2;
};

import java.util.*;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
        
    def push(self, node):
        self.stack1.append(node)
        
    def pop(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

算法及复杂度

算法：双栈模拟
时间复杂度：对于包含 M 个操作的输入，总时间复杂度为 $\mathcal{O}(M)$ 。
- push 操作的单次时间复杂度为 $\mathcal{O}(1)$ 。
- pop 操作的摊还时间复杂度为 $\mathcal{O}(1)$ 。这是因为虽然在 stack2 为空时，单次 pop 需要转移 stack1 中的所有元素，看起来是 $\mathcal{O}(M)$ ，但每个元素一生中最多只会被从 stack1 转移到 stack2 一次。因此，M 次操作的总成本是线性的，平摊到每一次操作上就是常数时间。
空间复杂度： $\mathcal{O}(M)$ ，在最坏的情况下（例如，连续 M 次 push），两个栈需要存储所有 M 个元素。