https://leetcode-cn.com/problems/implement-queue-using-stacks/
使用栈实现队列的下列操作：
push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
说明:
你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-queue-using-stacks
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
由于队列是 FIFI (先进先出)，而栈是 FILO (先进后出)。如果要用栈来模拟队列，则每次往模拟队列增加元素的时候，这个元素需要放在栈底，因为它是最后才会出列。
方法之一是，每次需要往模拟队列尾端 push 一个新元素时：
- 先把栈中的全部元素暂时取出
- 将新元素入栈到栈底
- 再将刚刚取出来元素重新入栈
因此我们还需要一个辅助栈来存暂时取出来的元素。
- 时间复杂度：入列操作是
$O(n)$ ，每次入列时，除新增元素外，每个元素都需要分别出栈入栈 2 次 (从模拟队列的栈中弹出，压入辅助栈，再从辅助栈弹出，压入队列模拟栈)。压入、弹出操作的时间复杂度都是$O(1)$ ，所以总的时间复杂度差不多是$O(4n)$ ，忽略掉常数，最后得到$O(n)$ 。出列操作是$O(1)$ 。 - 空间复杂度：$O(n)$，n 是队列的大小，需要一个大小为 n 的栈来模拟队列，还需要一个大小为 n 的辅助空间，但总的空间复杂度还是
$O(n)$ 。
JavaScript Code
class MyQueue {
constructor() {
this.stack = [];
}
push(x) {
const helper = [];
while (!this.empty()) {
helper.push(this.stack.pop());
}
this.stack.push(x);
while (helper.length) {
this.stack.push(helper.pop());
}
}
peek() {
return this.stack[this.stack.length - 1];
}
pop() {
return this.stack.pop();
}
empty() {
return this.stack.length === 0;
}
}方法 1 是在元素入列的时候，就考虑好了它出列的顺序，但我们还可以转换一下思路，在元素需要出列的时候再来考虑这个问题，这样的话：
- 入列时，直接
push到栈中； - 出列时，由于先入列的元素在栈底，需要先把其他元素弹出，依次压入辅助栈；
- 栈底元素弹出，出列；
- 刚才出栈的其他元素依次从辅助栈弹出，重新压入模拟栈。
再仔细想想的话：
- 第 2 步中，辅助栈中的元素出栈顺序刚好就是队列的出列顺序；
- 所以到第 4 步的时候，我们根本没必要把元素再从辅助栈转移到模拟栈；
- 下一次
pop操作时，直接从辅助栈弹出元素就可以了； - 如果辅助栈中没有元素了，我们再重复第 2 步。
这样的话，我们的队列元素其实是用了两个栈来储存，所以在判断队列是否为空的时候，两个栈都要考虑进去。
- 时间复杂度：入列是
$O(1)$ ，出列最差的情况就是每个元素都要从模拟栈中弹出，压入辅助栈，再从辅助栈中弹出，所以是$O(n)$ 。 - 空间复杂度：$O(n)$，n 为队列大小。
JavaScript Code
class MyQueue {
constructor() {
this.stack = new MyStack();
this.helper = new MyStack();
}
push(x) {
this.stack.push(x);
}
peek() {
if (this.helper.empty()) {
while (!this.stack.empty()) {
this.helper.push(this.stack.pop());
}
}
return this.helper.peek();
}
pop() {
if (this.helper.empty()) {
while (!this.stack.empty()) {
this.helper.push(this.stack.pop());
}
}
return this.helper.pop();
}
empty() {
return this.stack.empty() && this.helper.empty();
}
}
class MyStack {
constructor() {
this.stack = [];
}
push(x) {
this.stack.push(x);
}
pop() {
return this.stack.pop();
}
peek() {
return this.stack[this.stack.length - 1];
}
empty() {
return this.stack.length === 0;
}
}C++ Code
#include <stack>
using namespace std;
class MyQueue {
private:
stack<int> stack_in_;
stack<int> stack_out_;
void pour_to_stack_out_() {
while (!stack_in_.empty()) {
int top = stack_in_.top();
stack_in_.pop();
stack_out_.push(top);
}
};
public:
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
stack_in_.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
if (stack_out_.empty()) {
pour_to_stack_out_();
}
int top = stack_out_.top();
stack_out_.pop();
return top;
}
/** Get the front element. */
int peek() {
if (stack_out_.empty()) {
pour_to_stack_out_();
}
return stack_out_.top();
}
/** Returns whether the queue is empty. */
bool empty() {
return stack_in_.empty() && stack_out_.empty();
}
};
/**
* 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();
*/更多题解可以访问：https://github.com/suukii/91-days-algorithm