232.用栈实现队列

难度：容易

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

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top，peek/pop from top， size 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 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) ，即使其中一个操作可能花费较长时间。

解题思路

这是一道模拟题，不涉及到具体算法，考察的就是对栈和队列的掌握程度。

队列的特性是 FIFO（先入先出），而栈的特性是 FILO（先入后出）。

知道两者特性之后，我们需要用两个栈来模拟队列的特性，一个栈为 输入栈，一个栈为 输出栈。

我们只需要保证，输入的元素总是跟在前面的输入元素的后面，而输出元素总是最早输入的那个元素即可。

push 数据的时候，只要将数据放进输入栈就好
pop 数据的时候，操作就复杂一些：
1. 如果 输出栈 为空，就把 输入栈 的数据全部导入进来（注意是全部导入），再从 输出栈 栈顶弹出数据
2. 如果 输出栈 不为空，则直接从 输出栈 栈顶弹出数据，因为此栈顶元素是最先进入 push 进队列的
peek 和 pop 函数功能类似：
1. 如果 输出栈 为空，就把 输入栈 的数据全部导入进来（注意是全部导入），再返回 输出栈 栈顶的数据
2. 如果 输出栈 不为空，则直接返回 输出栈 栈顶的数据
最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空。

其实就是两个栈来回倒腾，但只有在 输出栈为空 的时候，才发生倒腾。

注意：根据栈的的特性，我们仅能使用 push 和 pop 操作。

Deque 的常用方法

作用	方法
栈顶添加	`void push(E e)`、`boolean offerFirst(E e)`
栈底添加	`boolean add(E e)`、`boolean offer(E e)`、`boolean offerLast(E e)`
栈顶删除	`E remove()`、`E pop()`、`E poll()`、`pollFirst()`
栈底删除	`E pollLast()`
栈顶查看	`E peek()`、`E peekFirst()`
栈底查看	`E peekLast()`
栈的大小	`int size()`
栈是否为空	`boolean isEmpty()`

代码展示

java

class MyQueue {
    Deque<Integer> inStack;
    Deque<Integer> outStack;

    public MyQueue() {
        inStack = new LinkedList<Integer>();
        outStack = new LinkedList<Integer>();
    }

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();

    }

    public int peek() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
}

时间复杂度：pop() 和 peek() 操作都是均摊 O(1)

空间复杂度：O(n)

关于均摊复杂度的说明

我们先用另外一个例子来理解「均摊复杂度」，我们都知道「哈希表」底层是通过数组实现的。

正常情况下，计算元素在哈希桶的位置，然后放入哈希桶，复杂度为 O(1)，假定是通过简单的“拉链法”搭配「头插法」方式来解决哈希冲突。

但当某次元素插入后，「哈希表」达到扩容阈值，则需要对底层所使用的数组进行扩容，这个复杂度是 O(n)

显然「扩容」操作不会发生在每一次的元素插入中，因此扩容的 O(n) 都会伴随着 n 次的 O(1)，也就是 O(n) 的复杂度会被均摊到每一次插入当中，因此哈希表插入仍然是 O(1) 的。

我们的倒腾不是发生在每一次 pop() 和 push() 中，而是集中发生在一次 输出栈为空 的时候，因此 pop() 和 peek() 都是均摊复杂度为 O(1) 的操作。

总结

在工业级别代码开发中，最忌讳的就是实现一个类似的函数，直接把代码粘过来改一改就完事了。

这样的项目代码会越来越乱，一定要懂得复用，功能相近的函数要抽象出来，不要大量的复制粘贴，很容易出问题！（踩过坑的人自然懂）

工作中如果发现某一个功能自己要经常用，同事们可能也会用到，自己就花点时间把这个功能抽象成一个好用的函数或者工具类，不仅自己方便，也方便了同事们。

同事们就会逐渐认可你的工作态度和工作能力，自己的口碑都是这么一点一点积累起来的！在同事圈里口碑起来了之后，你就发现自己走上了一个正循环，以后的升职加薪才少不了你！

232.用栈实现队列 ​

解题思路 ​

Deque 的常用方法 ​

代码展示 ​

关于均摊复杂度的说明 ​

总结 ​

232.用栈实现队列

解题思路

Deque 的常用方法

代码展示

关于均摊复杂度的说明

总结