【剑指offer】用两个栈实现队列

用两个栈实现队列

题目描述

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

解题思路

使用栈A与栈B模拟队列，A为插入栈，B为弹出栈。假设A和B都为空，可以认为栈A提供入队列的功能，栈B提供出队列的功能。

• 入队列，入栈A即可。
• 出队列分两种情况：
  • 若栈B不为空，则直接弹出栈B的数据；
  • 若栈B为空，则依次弹出栈A的数据，放入栈B中，再弹出栈B的数据。

以上情况可以利用前面介绍的栈来实现，也可以采用Java类库提供的Stack来实现，下面的代码是采用Java内置的Stack来实现的。

AC代码

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