用兩個棧實現(xiàn)一個隊列。隊列的聲明如下，請實現(xiàn)它的兩個函數(shù) appendTail 和 deleteHead ，分別完成在隊列尾部插入整數(shù)和在隊列頭部刪除整數(shù)的功能。(若隊列中沒有元素，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 次調(diào)用

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

解題思路
挺有意思的一道題，說這個題有意思不是因為這個題的思路難，而是寫了半天，發(fā)現(xiàn)忽略了好多小細節(jié)。因為隊列是先進先出，而棧是先進后出，如果要用棧來實現(xiàn)隊列，很容易就想到了用兩個棧來回倒，入隊就是向棧里壓入元素，出隊就是將整個棧壓入另外一個棧，將棧底元素變成棧頂元素，再出棧。

實現(xiàn)如下：

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， 可以顯式給定數(shù)據(jù)類型，不需要后面再casting
3. 提交后發(fā)現(xiàn)執(zhí)行時間較慢，原因是使用的Stack是基于Vector的，有些人直接利用了LinkedList，時間效率一下子就提高了。
4. 最后理解了一下Stack.pop() 和 peek()的區(qū)別，一個是棧頂元素出棧，后者是保留。

改后的代碼為

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 可以繼續(xù)化簡為

b.push(a.pop());