用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列廓握。隊(duì)列的聲明如下询枚，請實(shí)現(xiàn)它的兩個(gè)函數(shù) appendTail 和 deleteHead 台舱，分別完成在隊(duì)列尾部插入整數(shù)和在隊(duì)列頭部刪除整數(shù)的功能涧偷。(若隊(duì)列中沒有元素尚骄，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 進(jìn)行 10000 次調(diào)用

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

解題思路
挺有意思的一道題，說這個(gè)題有意思不是因?yàn)檫@個(gè)題的思路難倔丈，而是寫了半天憨闰，發(fā)現(xiàn)忽略了好多小細(xì)節(jié)。因?yàn)殛?duì)列是先進(jìn)先出需五，而棧是先進(jìn)后出鹉动，如果要用棧來實(shí)現(xiàn)隊(duì)列，很容易就想到了用兩個(gè)棧來回倒宏邮，入隊(duì)就是向棧里壓入元素泽示，出隊(duì)就是將整個(gè)棧壓入另外一個(gè)棧，將棧底元素變成棧頂元素蜜氨，再出棧械筛。

實(shí)現(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);
            }
        }
        
    }
}

提交沒問題，但是感覺寫的很繁瑣飒炎，是因?yàn)闆]有想清楚幾個(gè)問題就動(dòng)手了埋哟。

1. Stack A 和Stack B 可以為固定的棧，即A永遠(yuǎn)用于進(jìn)隊(duì)郎汪，B用于出隊(duì)而不是兩個(gè)棧來回顛倒赤赊，所以appendTail 和 deleteHead 完全用不上。
2. Stack 直接使用了java 類包 java.util.Stack煞赢， 可以顯式給定數(shù)據(jù)類型抛计，不需要后面再casting
3. 提交后發(fā)現(xiàn)執(zhí)行時(shí)間較慢，原因是使用的Stack是基于Vector的照筑，有些人直接利用了LinkedList爷辱，時(shí)間效率一下子就提高了录豺。
4. 最后理解了一下Stack.pop() 和 peek()的區(qū)別，一個(gè)是棧頂元素出棧饭弓，后者是保留双饥。

改后的代碼為

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());