剑指offer_【5】两个栈实现队列

1. 题目描述

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

2. 解题思路

• 栈的规则是先进后出，队列的规则是先进先出

1. stack1一直维持着栈底–栈顶是队列的入队顺序

2. stack2一直维持着栈顶–栈尾为队列的入队顺序

3. 当执行队列的入队（push）时，如果stack2为空，则直接插入到stack1,stack1从栈底到栈顶的顺序为入队顺序，如果stack2不为空，则将stack2的元素倒入（栈顶—栈尾）stack1,然后再插入数据

4- 当执行队列的出队(pop)操作时，应该出的是stack1的栈底元素，故将stack1依次倒入stack2,这时stack2的栈顶就是要出队的数值，此时stack1为空，stack2从（栈顶–栈尾）为入队顺序

3. 代码

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    //队列的入队

    public void push(int node) {
        //将stack2倒入stack1

        while (!stack2.empty()) {
            stack1.push(stack2.pop());
        }
        //将元素插入stack1

        stack1.push(node);
    }
    //队列的出队

    public int pop() {
        //将stack1倒入stack2

        while (!stack1.empty()) {
            stack2.push(stack1.pop());
        }
        //stack2的栈顶就是出队数值

        return stack2.pop();
    }
}