用两个栈实现队列

题目：

用两个栈实现一个队列。队列的声明如下，请实现两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入节点和队列头部删除节点的功能。

public class TwoStackQueue {    
    Stack stack1;    
    Stack stack2;    
    void appendTail(T node);   
    T deleteHead();
}

分析：

当向 stack1 中依次插入3个元素 {a,b,c}后，它们的出栈顺序是 {c,b,a}，如果想要 a 最先出栈，可以将 stack1 中的元素依次压入 stack2 中，这样 stack2 的入栈顺序就变成了 {c,b,a}，出栈顺序则刚好相反，变成 {a,b,c}。

代码：

public class TwoStackQueue<T> {
    // 插入栈，只用于插入的数据
    Stack<T> stack1 = new Stack<>();
    // 弹出栈，只用于弹出数据
    Stack<T> stack2 = new Stack<>();

    // 添加操作，在队列尾部插入结点
    void appendTail(T node) {
        stack1.add(node);
    }

    T deleteHead() {
        // 先判断弹出栈是否为空，如果为空就将插入栈的所有数据弹出栈，
        // 并且将弹出的数据压入弹出栈中
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.add(stack1.pop());
            }
        }

        // 如果弹出栈中还没有数据就抛出异常
        if (stack2.isEmpty()) {
            throw new RuntimeException("栈数据异常");
        }

        // 返回弹出栈的栈顶元素，对应的就是队首元素
        return stack2.pop();
    }
}

测试：

    @Test
    public void test1() {
        TwoStackQueue<Integer> stackQueue = new TwoStackQueue<>();
        stackQueue.appendTail(1);
        stackQueue.appendTail(2);
        stackQueue.appendTail(3);
        System.out.println(stackQueue.deleteHead());
        System.out.println(stackQueue.deleteHead());
        System.out.println(stackQueue.deleteHead());
    }

tips：“用两个队列实现一个栈” 原理类似

先往队列 queue1 添加元素，取出数据时，先把 queue1 中数据遍历出来，放到 queue2 中，然后从 queue2 中取元素。就变成了先进后出的栈结构。