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

什么是队列？

想象一下你在学校排队领午餐。你来到队伍的末尾加入队伍，当你前面的人都领完午餐后，你就能够领取自己的午餐。这就是队列的工作原理——先进先出（First In First Out, FIFO）。

用两把椅子来实现队列

现在，我们有两把椅子（栈），我们把它们叫做 A 和 B。我们的目标是用这两把椅子来模仿排队的行为。

插入元素（Push）

• 当有人加入队伍时（插入元素），我们让他坐在椅子 A 上。

删除元素（Pop）

• 当我们需要让一个人离开队伍（删除元素）时，我们需要确保最先加入队伍的人最先离开。
• 如果椅子 B 上有人，那么这个人就是最先加入队伍的人，他可以直接离开（删除）。
• 如果椅子 B 是空的，我们就把椅子 A 上的人一个个移到椅子 B 上。这样一来，最先加入队伍的人就会坐在椅子 B 的最上面，他就可以离开了（删除）。

具体步骤

加入队伍（Push）

1. 新来的朋友直接坐到椅子 A 上。

离开队伍（Pop）

1. 如果椅子 B 上有朋友，让椅子 B 上面的朋友离开。
2. 如果椅子 B 是空的，把椅子 A 上所有的朋友都搬到椅子 B 上，然后让椅子 B 上面的朋友离开。

示例

假设有如下操作：

1. 朋友 1 加入队伍。
2. 朋友 2 加入队伍。
3. 朋友 1 离开队伍。
4. 朋友 2 离开队伍。

我们会这样做：

1. 朋友 1 坐到椅子 A 上。
2. 朋友 2 坐到椅子 A 上。
3. 椅子 B 是空的，所以先把椅子 A 上的朋友移动到椅子 B 上，然后让椅子 B 上面的（也就是朋友 1）离开。
4. 再次检查，发现椅子 B 还有一个朋友（朋友 2），让他离开。

下面是简单的代码实现：

import java.util.Stack;

class QueueWithTwoStacks {
    private Stack<Integer> stack1 = new Stack<>();
    private Stack<Integer> stack2 = new Stack<>();

    // 向队列尾部插入整数
    public void push(int value) {
        stack1.push(value);
    }

    // 从队列头部删除整数
    public int pop() {
        // 如果stack2为空，则将stack1中的所有元素转移至stack2
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        // 从stack2中弹出元素，此时stack2的顶部元素是最先进入stack1的元素
        return stack2.pop();
    }
}

如果这篇文章对你有帮助，请点个免费的攒👍，让能够帮助更多的人。