[剑指Offer]09.用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
提示：

1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof

解题思路
挺有意思的一道题，说这个题有意思不是因为这个题的思路难，而是写了半天，发现忽略了好多小细节。因为队列是先进先出，而栈是先进后出，如果要用栈来实现队列，很容易就想到了用两个栈来回倒，入队就是向栈里压入元素，出队就是将整个栈压入另外一个栈，将栈底元素变成栈顶元素，再出栈。

实现如下：

class CQueue {
    Stack stackA;
    Stack stackB;

    boolean deleteHead;
    boolean appendTail;

    public CQueue() {
        stackA = new Stack();
        stackB = new Stack();

        appendTail = false;
        deleteHead = false;
    }
    
    public void appendTail(int value) {
        if(deleteHead){
            switchStack(stackA,stackB);        
        }

        if(!stackB.empty())
            stackB.push(value);
        else
            stackA.push(value); 

        appendTail = true;
        deleteHead = false;     
    }
    
    public int deleteHead() {
        if(appendTail){
            switchStack(stackA,stackB);
        }   

        appendTail = false;
        deleteHead = true;     

        if(stackA.empty() && !stackB.empty())
            return (Integer)stackB.pop();

        if(stackB.empty() && !stackA.empty())
            return (Integer)stackA.pop();

        return -1;
    }

    private void switchStack(Stack a, Stack b){
        if(!a.empty()){
            while(!a.empty()){
                Integer value = (Integer) a.pop();
                b.push(value);
            }
        } else if(!b.empty()){
            while(!b.empty()){
                Integer value = (Integer) b.pop();
                a.push(value);
            }
        }
        
    }
}

提交没问题，但是感觉写的很繁琐，是因为没有想清楚几个问题就动手了。

1. Stack A 和Stack B 可以为固定的栈，即A永远用于进队，B用于出队而不是两个栈来回颠倒，所以appendTail 和 deleteHead 完全用不上。
2. Stack 直接使用了java 类包 java.util.Stack， 可以显式给定数据类型，不需要后面再casting
3. 提交后发现执行时间较慢，原因是使用的Stack是基于Vector的，有些人直接利用了LinkedList，时间效率一下子就提高了。
4. 最后理解了一下Stack.pop() 和 peek()的区别，一个是栈顶元素出栈，后者是保留。

改后的代码为

class CQueue {
    Stack<Integer> in;
    Stack<Integer> out;

    public CQueue() {
        in = new Stack<>();
        out = new Stack<>();
    }

    public void appendTail(int value) {
        if(!out.empty())
           switchStack(out,in);
        in.push(value);
    }

    public int deleteHead() {
        if(!in.empty())
            switchStack(in,out);

        if(!out.empty())
            return out.pop();

        return -1;
    }

    private void switchStack(Stack a, Stack b){
        while(!a.empty()){
            Integer value = (Integer) a.pop();
            b.push(value);
        }
    }
}

其中switchStack 可以继续化简为

b.push(a.pop());