题解 | #用两个栈实现队列#

题目主要信息:

• 队列：元素不可直接下标访问，先进先出
• 栈：元素不可直接访问，先进后出
• 使用两个栈模拟在队列中插入n个元素和弹出n个元素，顺序不定，但是保证操作都是合法的

举一反三：

学习完本题的思路你可以解决如下题目：

BM43. 包含min函数的栈

方法：双栈法（推荐使用）

知识点1：栈

栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

知识点2：队列

队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。·

思路：

元素进栈以后，只能优先弹出末尾元素，但是队列每次弹出的却是最先进去的元素，如果能够将栈中元素全部取出来，才能访问到最前面的元素，此时，可以用另一个栈来辅助取出。

具体做法：

• step 1：push操作就正常push到第一个栈末尾。
• step 2：pop操作时，优先将第一个栈的元素弹出，并依次进入第二个栈中。

//将第一个栈中内容弹出放入第二个栈中
while(!stack1.isEmpty()) 
    stack2.push(stack1.pop()); 

• step 3：第一个栈中最后取出的元素也就是最后进入第二个栈的元素就是队列首部元素，要弹出，此时在第二个栈中可以直接弹出。
• step 4：再将第二个中保存的内容，依次弹出，依次进入第一个栈中，这样第一个栈中虽然取出了最里面的元素，但是顺序并没有变。

//再将第二个栈的元素放回第一个栈
while(!stack2.isEmpty()) 
    stack1.push(stack2.pop());

图示：

Java实现代码：

import java.util.Stack;
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        //将第一个栈中内容弹出放入第二个栈中
        while(!stack1.isEmpty()) 
            stack2.push(stack1.pop()); 
        //第二个栈栈顶就是最先进来的元素，即队首
        int res = stack2.pop(); 
        //再将第二个栈的元素放回第一个栈
        while(!stack2.isEmpty()) 
            stack1.push(stack2.pop());
        return res;
    }
}

C++实现代码：

class Solution
{
public:
    //入队列就正常入栈
    void push(int node) { 
        stack1.push(node);
    }

    int pop() {
        //将第一个栈中内容弹出放入第二个栈中
        while(!stack1.empty()){ 
            stack2.push(stack1.top()); 
            stack1.pop();
        }
        //第二个栈栈顶就是最先进来的元素，即队首
        int res = stack2.top(); 
        stack2.pop(); 
        //再将第二个栈的元素放回第一个栈
        while(!stack2.empty()){ 
            stack1.push(stack2.top());
            stack2.pop();
        }
        return res;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

Python实现代码：

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        self.stack1.append(node)
    def pop(self):
        #将第一个栈中内容弹出放入第二个栈中
        while self.stack1: 
            self.stack2.append(self.stack1.pop()) 
        #第二个栈栈顶就是最先进来的元素，即队首
        res = self.stack2.pop() 
        #再将第二个栈的元素放回第一个栈
        while self.stack2: 
            self.stack1.append(self.stack2.pop())
        return res

复杂度分析：

• 时间复杂度：push的时间复杂度为$O(1)O(1)$，pop的时间复杂度为$O(n)O(n)$，push是直接加到栈尾，相当于遍历了两次栈
• 空间复杂度：$O(n)O(n)$，借助了另一个辅助栈空间