?? 作者簡介：一名在后端領域?qū)W習，并渴望能夠?qū)W有所成的追夢人。
?? 個人主頁：不 良
?? 系列專欄：??劍指 Offer ???Linux
?? 學習格言：博觀而約取，厚積而薄發(fā)
?? 歡迎進來的小伙伴，如果小伙伴們在學習的過程中，發(fā)現(xiàn)有需要糾正的地方，煩請指正，希望能夠與諸君一同成長！ ??

劍指 Offer 09. 用兩個棧實現(xiàn)隊列

題目：

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

思路一：

雙棧。棧是先進后出的機構，隊列是先進先出的結構。

CQueue()作為一個構造函數(shù)，在本題中不用管。

1.定義兩個棧pushst和popst，將pushst棧作為輸入棧用于appendTail操作，popst棧作為輸出棧用于deleteHead操作；

2.進行appendTail操作時，直接將數(shù)據(jù)壓入pushst棧中；

3.進行deleteHead操作時：

• 先檢查popst和pushst是否為空，如果為空直接返回-1；

• 如果popst為空且pushst不為空，將pushst中的數(shù)據(jù)從棧頂開始放入popst中，然后再進行刪除返回操作。

• 如果popst不為空，直接刪除并返回棧頂元素。

代碼如下：

class CQueue {
public:
    CQueue() {
        
    }
    
    void appendTail(int value) {
        pushst.push(value);
    }
    
    int deleteHead() {
        if(pushst.empty() && popst.empty())
            return -1;
        //如果popst中為空，則將pushst中的數(shù)據(jù)都倒入popst中
        if(popst.empty() && !pushst.empty())
        {
            while(!pushst.empty())
            {
                int tmp = pushst.top();
                popst.push(tmp);
                pushst.pop();
            }
        }
        //如果popst中不為空，直接刪除并返回
        int tmp = popst.top();
        popst.pop();
        return tmp;
    }
private:
    stack<int> pushst;//實例化一個pushst棧，用于壓入數(shù)據(jù)
    stack<int> popst;//實例化一個popst棧，用于刪除數(shù)據(jù)
};

插入：

時間復雜度：O(1)

空間復雜度：O(1)

刪除：

時間復雜度：O(N)，要將pushst中的數(shù)據(jù)全部壓入popst中。

空間復雜度：O(N)，使用了輔助棧的空間。文章來源地址http://www.zghlxwxcb.cn/news/detail-475780.html

到了這里，關于劍指 Offer 09. 用兩個棧實現(xiàn)隊列的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！