剑指offer----用两个栈实现队列

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

代码

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(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

思路：
由于队列是先进先出的，而栈是先进后出的，也就是说，同样的数据进入两种结构之后

• 队列弹出数据的顺序和压入的顺序是一致的。
• 栈弹出数据的顺序和压入数据的顺序是相反的。

而本题中说可以用两个栈，那么

• 首先将数据压入一个栈中，再弹出到另外一个栈，
• 将这个栈的数据弹出。
• 结果就等于最开始压入的顺序了，差不多就是负负得正的意思。

（将数据压入stack1，然后弹出数据，依次压入stack2，弹出的时候从stack2弹出。即将stack1中的数据倒如stack2中。）

几个需要注意的点:

• 在stack1的数据倒入stack2中的时候一定要保证stack1是空的。否则数据的顺序会被打乱。