剑指 offer 笔记 05 | 用两个栈实现队列

题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

分析：

题目要求是，利用两个栈来模拟，一个队列，栈的特点类似手枪弹夹，先压入的“子弹”，最后才弹出来。就是所谓的「先进后出」或者「后进先出」的特点。

而队列，就像生活中的排队一样，比如你去窗口买车票，肯定要排队，排最前的可以先买票，窗口服务员就是这样以此处理乘客。也就是「先进先出」。

这道题，要利用两个栈来模拟一个队列效果，结合特点，我们可以这样处理。

第一个栈（StackPush），先一次性把数据倒进去，然后从栈顶依次弹出，把弹出的数据存放到第二个栈（StackPop）里。最后一步就把第二个栈里的数据依次倒出来，这就模拟了队列。

这里有两个地方要注意的，左神（左程云）说的。
1）第一个栈要把里面的数据，一次性全部倒完；

2）若 StackPop 里面有数据（不为空），则不能往里倒数据；

代码实现：
这是左程云的《程序员代码面试指南》的答案：

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() {
       
        if(stack1.empty()&&stack2.empty()){ //若两个栈都为空，则提示该“队列”为空
            throw new RuntimeException("Queue is empty!");
        }
     
        if(stack2.empty()){  //若栈2为空，可以往里面倒数据；
            while(!stack1.empty()){ //  若 栈1 有数据，继续则倒入
                stack2.push(stack1.pop());  //将 栈1 弹出的元素放入栈2中 
            }
        }
        return stack2.pop(); //然后弹 栈2
    }
}

总结：其实得用一个全局的视角来看， 让我们实现这个“队列”的 push 和 pop 方法，里面就用两个栈的方法来封装。

参考文献:牛客网大佬们的评论区