用兩個(gè)棧實(shí)現(xiàn)隊(duì)列

題目描述：

用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列。隊(duì)列的聲明如下，請實(shí)現(xiàn)它的兩個(gè)函數(shù) appendTail 和 deleteHead ，分別完成在隊(duì)列尾部插入整數(shù)和在隊(duì)列頭部刪除整數(shù)的功能。(若隊(duì)列中沒有元素，deleteHead 操作返回 -1 )

解題思路

• 一個(gè)棧用于保存輸入元素，并一個(gè)元素用于保存輸出元素。隊(duì)列末尾添加元素時(shí)，即向 in 棧中添加元素，當(dāng)從隊(duì)頭刪除元素時(shí)，將 in 棧中的元素出棧，每次先出棧元素 push 到 out 棧中，這樣起到反轉(zhuǎn)元素順序的作用，此時(shí)對 out 棧進(jìn)行 pop ，就相當(dāng)于從對頭刪除元素

由于問題特殊，以下分析僅滿足添加 N 個(gè)元素并刪除 N 個(gè)元素，即棧初始和結(jié)束狀態(tài)下都為空的情況

• 時(shí)間復(fù)雜度：appendTail()函數(shù)為 O(1)；deleteHead() 函數(shù)在 N 次隊(duì)首元素刪除操作中總共需完成 N 個(gè)元素的倒序。
• 空間復(fù)雜度：O(N)

class CQueue {
    Deque<Integer> in;
    Deque<Integer> out;
    public CQueue() {
        in = new ArrayDeque<>();
        out = new ArrayDeque<>();
    }
    
    public void appendTail(int value) {
        in.push(value);
    }
    
    public int deleteHead() {
        if (in.isEmpty() && out.isEmpty())
            return -1 ;

        if (out.isEmpty()) {
            while(!in.isEmpty()) {
                out.push(in.pop());
            }
        }

        return out.pop();
    }
}