使用栈实现队列

题目介绍

力扣232题：https://leetcode-cn.com/problems/implement-queue-using-stacks/

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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（双端队列）来模拟一个栈，只要是标准的栈操作即可。

进阶：你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
在这里插入图片描述

分析

我们要用栈来实现队列。一个队列是 FIFO 的，但一个栈是 LIFO 的。为了满足队列的 FIFO 的特性，我们需要将入栈的元素次序进行反转，这样在出队时就可以按照入队顺序依次弹出了。

想要反转，简单的想法是只要把所有元素依次弹出，并压入另一个栈，自然就变成本来栈底元素到了栈顶了。所以我们的实现，需要用到两个栈。

方法一：入队时反转

一种直观的思路是，最终的栈里，按照“自顶向下”的顺序保持队列。也就是说，栈顶元素是最先入队的元素，而最新入队的元素要压入栈底。我们可以用一个栈来存储元素的最终顺序（队列顺序），记作stack1；用另一个进行辅助反转，记作stack2。

最简单的实现，就是直接用stack2，来缓存原始压栈的元素。每次调push，就把stack1中的元素先全部弹出并压入stack2，然后把新的元素也压入stack2；这样stack2就是完全按照原始顺序入栈的。最后再把stack2中的元素全部弹出并压入stack1，进行反转。
在这里插入图片描述

代码演示如下：

// 用两个栈实现队列：入队时翻转
public class MyQueue {
    // 定义两个栈
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    // 入队方法
    public void push(int x){
        // 1. 首先将stack1中所有元素弹出，压入stack2
        while (!stack1.isEmpty())
            stack2.push( stack1.pop() );

        // 2. 将新元素压入stack1
        stack1.push(x);

        // 3. 再将stack2中所有元素弹出，压入stack
        while (!stack2.isEmpty())
            stack1.push( stack2.pop() );
    }

    // 出队方法
    public int pop(){
        return stack1.pop();
    }

    // 获取队首元素
    public int peek(){
        return stack1.peek();
    }

    // 判空
    public boolean empty(){
        return stack1.isEmpty();
    }

    public static void main(String[] args) {
        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
    }
}

复杂度分析
入队
时间复杂度：O(n)
除新元素之外，所有元素都会被压入两次，弹出两次。新元素被压入两次，弹出一次。（当然，我们可以稍作改进，在stack1清空之后把新元素直接压入，就只压入一次了）
这个过程产生了4n+3 次操作，其中 n 是队列的大小。由于入栈操作和弹出操作的时间复杂度为 O(1)，所以时间复杂度为 O(n)。

空间复杂度：O(n)
需要额外的内存来存储队列中的元素。

其它操作（pop、peek、isEmpty）
时间复杂度：O(1)
空间复杂度：O(1)

方法二：出队时反转

可以不要在入队时反转，而是在出队时再做处理。
在这里插入图片描述
执行出队操作时，我们想要弹出的是stack1的栈底元素。所以需要将stack1中所有元素弹出，并压入stack2，然后弹出stack2的栈顶元素。

我们观察可以发现，stack2中的元素，其实就是保持着队列顺序的，所以完全没必要将它们再压回stack1，下次出队时，我们只要直接弹出stack2中的栈顶元素就可以了。

代码实现如下：

public class MyQueue2 {
    // 定义两个栈
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public MyQueue2() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

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

    public int pop(){
        // 1. 判断stack2是否为空，如果为空，就要将stack1中所有元素弹出，然后压入
        if (stack2.isEmpty()){
            while (!stack1.isEmpty())
                stack2.push( stack1.pop() );
        }

        // 2. 弹出stack2栈顶元素
        return stack2.pop();
    }

    public int peek(){
        // 1. 判断stack2是否为空，如果为空，就要将stack1中所有元素弹出，然后压入
        if (stack2.isEmpty()){
            while (!stack1.isEmpty())
                stack2.push( stack1.pop() );
        }

        // 2. 返回stack2栈顶元素
        return stack2.peek();
    }

    public boolean empty(){
        return stack1.isEmpty() && stack2.isEmpty();
    }

    public static void main(String[] args) {
        MyQueue2 myQueue = new MyQueue2();
        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
    }
}

复杂度分析
入队（push）

时间复杂度：O(1)。向栈压入元素的时间复杂度为O(1)
空间复杂度：O(n)。需要额外的内存（stack1和stack2共同存储）来存储队列元素。

出队（pop）

时间复杂度：摊还复杂度 O(1)，最坏情况下的时间复杂度 O(n)在最坏情况下，stack2为空，算法需要执行while循环进行反转。具体过程是从 stack1 中弹出 n 个元素，然后再把这 n 个元素压入stack2，在这里n代表队列的大小。这个过程产生了 2n 步操作，时间复杂度为 O(n)。但当 stack2非空时，只需要直接弹栈，算法就只有 O(1) 的时间复杂度。均摊下来，摊还复杂度为O(1)。
空间复杂度：O(1)

取队首元素（peek）和判断是否为空（empty）

时间复杂度：O(1)
空间复杂度：O(1)

摊还复杂度分析

摊还分析（Amortized Analysis，均摊法），用来评价某个数据结构的一系列操作的平均代价。

对于一连串操作而言，可能某种情况下某个操作的代价特别高，但总体上来看，也并非那么糟糕，可以形象的理解为把高代价的操作“分摊”到其他操作上去了，要求的就是均摊后的平均代价。

摊还分析的核心在于，最坏情况下的操作一旦发生了一次，那么在未来很长一段时间都不会再次发生，这样就会均摊每次操作的代价。

摊还分析与平均复杂度分析的区别在于，平均情况分析是平均所有的输入。而摊还分析是平均操作。在摊还分析中，不涉及概率，并且保证在最坏情况下每一个操作的平均性能。

所以摊还分析，往往会用在某一数据结构的操作分析上。