LeetCode 232. 用栈实现队列

LeetCode 232. 用栈实现队列

难度：$easy$

---

题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（$push$、$pop$、$peek$、$empty$）：

实现 $MyQueue$ 类：

• $voidpush(intx)$ 将元素 x 推到队列的末尾
• $intpop()$ 从队列的开头移除并返回元素
• $intpeek()$ 返回队列开头的元素
• $booleanempty()$ 如果队列为空，返回 $true$ ；否则，返回 $false$

说明：

• 你 只能 使用标准的栈操作 —— 也就是只有 $pushtotop$, $peek/popfromtop$, $size$, 和 $isempty$ 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

• $1<=x<=9$
• 最多调用 $100$ 次 $push$、$pop$、$peek$ 和 $empty$
• 假设所有操作都是有效的 （例如，一个空的队列不会调用 $pop$ 或者 $peek$ 操作）

进阶：

• 你能否实现每个操作均摊时间复杂度为 $O(1)$ 的队列？换句话说，执行 $n$ 个操作的总时间复杂度为 $O(n)$ ，即使其中一个操作可能花费较长时间。

---

算法

(栈,队列)

我们用一个栈来存储队列中的元素，另外还需要一个辅助栈，用来辅助实现 pop() 和 peek() 操作。

四种操作的实现方式如下：

• push(x) – 直接将x插入栈顶；
• pop() – 即需要弹出栈底元素，我们先将栈底以上的所有元素插入辅助栈中，然后弹出栈底元素，最后再将辅助栈中的元素重新压入当前栈中；
• peek() – 返回栈顶元素，同理，我们先将栈底以上的所有元素插入辅助栈中，然后输出栈底元素，最后再将辅助栈中的元素重新压入当前栈中，恢复当前栈原状；
• empty() – 返回当前栈是否为空；

复杂度分析

• 时间复杂度：push(x) 和 emtpy() 均只有一次操作，时间复杂度是 $O(1)$，pop() 和 peek() 涉及到 $n$ 次操作，所以时间复杂度是 $O(n)$

• 空间复杂度 : $O(n)$

C++ 代码

class MyQueue {
public:stack<int> stk1;stack<int> stk2;MyQueue() {}void push(int x) {stk1.push(x);}int pop() {while (stk1.size() > 1) {int t = stk1.top();stk1.pop();stk2.push(t);}int ans = stk1.top();stk1.pop();while (stk2.size()) {stk1.push(stk2.top());stk2.pop();}return ans;}int peek() {while (stk1.size() > 1) {int t = stk1.top();stk1.pop();stk2.push(t);}int ans = stk1.top();while (stk2.size()) {stk1.push(stk2.top());stk2.pop();}return ans;}bool empty() {if (stk1.empty()) return true;return false;}
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj = new MyQueue();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->peek();* bool param_4 = obj->empty();*/

---