? 劍指 Offer 09. 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列

難度：簡(jiǎn)單

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

示例 1：

輸入：
[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”,“deleteHead”]
[[],[3],[],[],[]]
輸出：[null,null,3,-1,-1]

示例 2：

輸入：
[“CQueue”,“deleteHead”,“appendTail”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[],[5],[2],[],[]]
輸出：[null,-1,null,null,5,2]

提示：

• $1<=values<=10000$
• 最多會(huì)對(duì) appendTail、deleteHead 進(jìn)行 10000 次調(diào)用

??思路：

用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列，完成隊(duì)列的 appendTail 和 deleteHead 操作。

• in 棧用來(lái)處理入棧（push）操作，out 棧用來(lái)處理出棧（pop）操作;
• 一個(gè)元素進(jìn)入 in 棧之后，出棧的順序被反轉(zhuǎn)。當(dāng)元素要出棧時(shí)，需要先進(jìn)入 out 棧，此時(shí)元素出棧順序再一次被反轉(zhuǎn)，因此出棧順序就和最開(kāi)始入棧順序是相同的，先進(jìn)入的元素先退出，這就是隊(duì)列的順序。
  

??代碼：(C++、Java)

C++

class CQueue {
private:
    stack<int> in, out;

    void in2out(){
        while(!in.empty()){
            out.push(in.top());
            in.pop();
        }
    }

public:
    CQueue() { }
    
    void appendTail(int value) {
        in.push(value);
    }
    
    int deleteHead() {
        if(out.empty()){
            if(in.empty()) return -1;
            in2out();
        }
        int ans = out.top();
        out.pop();
        return ans;
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */

Java

class CQueue {
    private Stack<Integer> in = new Stack<Integer>();
    private Stack<Integer> out = new Stack<Integer>();

    private void in2out(){
        while(!in.isEmpty()){
            out.push(in.pop());
        }
    }

    public CQueue() { }
    
    public void appendTail(int value) {
        in.push(value);
    }
    
    public int deleteHead() {
        if(out.isEmpty()){
            if(in.isEmpty()) return -1;
            in2out();
        }
        return out.pop();
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

?? 運(yùn)行結(jié)果：

?? 復(fù)雜度分析：

• 時(shí)間復(fù)雜度：appendTail 為 $O(1)$，deleteHead 為均攤 $O(1)$。對(duì)于每個(gè)元素，至多入棧和出棧各兩次，故均攤復(fù)雜度為 $O(1)$。

• 空間復(fù)雜度：$O(n)$，其中 n 是操作總數(shù)。對(duì)于有 n 次appendTail 操作的情況，隊(duì)列中會(huì)有 nnn 個(gè)元素，故空間復(fù)雜度為 $O(n)$。

題目來(lái)源：力扣。

放棄一件事很容易，每天能堅(jiān)持一件事一定很酷，一起每日一題吧！
關(guān)注我LeetCode主頁(yè) / CSDN—力扣專(zhuān)欄，每日更新！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-583863.html

注： 如有不足，歡迎指正！

到了這里，關(guān)于(棧隊(duì)列堆) 劍指 Offer 09. 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列 ——【Leetcode每日一題】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！