0232. Implement Queue using Stacks
=================================
题目信息
--------
:题号: 0232
:难度: Easy
:主题: 设计、队列、栈、对象状态
:原题: `LeetCode 0232 `_
:重点: 用 LIFO 操作实现 FIFO、方法语义、跨调用状态、合法队首操作
题目重述
--------
设计 ``MyQueue`` 类,只使用一个或两个栈实现先进先出的队列,并支持以下方法:``push(x)`` 把元素加入队尾;``pop()`` 删除并返回队首元素;``peek()`` 返回但不删除队首元素;``empty()`` 判断队列是否为空。
实现只能使用栈的标准操作,包括压入栈顶、读取或弹出栈顶、查询长度以及判空。``x`` 位于 ``[1, 9]``,四种方法的调用总数最多为 ``100``;题目保证调用 ``pop`` 和 ``peek`` 时队列非空。同一个对象必须在连续调用之间保存队列内容和先进先出顺序。
自建示例
--------
先加入的元素先离开:
.. code-block:: text
输入:依次调用 push(5), push(2), push(9), peek(), pop(), peek(), empty()
输出:5, 5, 2, false
解释:5 最早进入队列,所以 peek 和第一次 pop 都得到 5;删除后新的队首是 2,队列仍包含元素。
双栈的摊还转移
--------------
使用 ``in_stack`` 接收新元素,使用 ``out_stack`` 提供队首。若输出栈为空,
把输入栈全部弹出并压入输出栈;原来较早加入的元素会在转换后位于输出栈顶。
输出栈非空时不能再次转移,否则会破坏尚未离开的元素顺序。
.. code-block:: text
push(5), push(2), push(9)
in_stack: 5 2 9(栈顶为 9)
第一次 peek 前转移后:out_stack 栈顶为 5,下面是 2、9
之后 ``pop``/``peek`` 直接操作 ``out_stack``。当它再次为空,才把期间积累在 ``in_stack`` 中的新元素反转到输出栈。
正确性说明
----------
当 ``out_stack`` 非空时,它的栈顶是所有尚未出队元素中最早加入的元素,因为上一次转移按入队时间逆序压入。
新的元素只进入 ``in_stack``,不会越过当前输出栈中的旧元素;旧元素全部出队后再转移,新的最早元素又会到达栈顶。
因此每次 ``peek`` 读取和 ``pop`` 删除的都是 FIFO 队首,两个栈为空当且仅当队列为空。
C++ 实现
--------
.. code-block:: cpp
class MyQueue {
std::stack in_stack;
std::stack out_stack;
void moveIfNeeded() {
if (!out_stack.empty()) return;
while (!in_stack.empty()) {
out_stack.push(in_stack.top());
in_stack.pop();
}
}
public:
MyQueue() = default;
void push(int x) {
in_stack.push(x);
}
int pop() {
moveIfNeeded();
const int value = out_stack.top();
out_stack.pop();
return value;
}
int peek() {
moveIfNeeded();
return out_stack.top();
}
bool empty() const {
return in_stack.empty() && out_stack.empty();
}
};
代码分析
--------
单次转移可能搬运多个元素,但每个元素从输入栈到输出栈最多一次、从输出栈弹出一次,
所以一串操作的总时间为线性,``push`` 为 ``O(1)``,``pop``/``peek`` 摊还为 ``O(1)``,
最坏单次转移为 ``O(n)``。两个栈合计保存队列元素,额外空间为 ``O(n)``。