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

题目（Java题解）

用两个栈来实现一个队列，分别完成在队列尾部插入整数(push)和在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

示例

input:
    ["PUSH 1","PUSH 2","POP","POP"]
output:    
    1，2

解题思路

首先明确栈结构和队列结构的特点，栈为先进后出，队列为先进先出，如果需要用两个栈结构实现队列的话，需要注意的就是数字的进出顺序，这样我们先插入1，2，3，如果此时需要弹出数字12的话，弹出顺序必然为1，2，因此需要将栈1中的123弹出到另一个栈2中，插入顺序为321，此时通过栈2弹出数据可以得到12的顺序，这种最基本的东西是一目了然的。此时再次加入数据45，栈2中还有一个数据3，那么此时继续弹出数据，按照压入顺序显然需要先弹出3再将栈1中的45弹入栈2中，因此我们可以得出结论，压入数据时，统一压入到栈1中，弹出数据时，先判断栈2是否为空，为空的话将栈1中的所有数据都弹入栈2中，不为空的话则弹出栈2的数据。如果没有声明操作合法的话需要询问面试官是否需要对异常操作进行处理，比如空队列中删除元素，如果需要处理异常的话通过显示声明异常数据的方式还是通过抛出异常的方式等。

实例代码

Naive

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());
        }
        if(!satck2.isEmpty()){
            return stack2.pop();
        }else{
            return -1;
        }
    }
}

测试用例

1. 往空队列中添加元素，删除元素
2. 非空队列添加、删除元素
3. 连续删除元素直到队列为空