所有的LeetCode題解索引，可以看這篇文章——【算法和數(shù)據(jù)結(jié)構(gòu)】LeetCode題解。

一、題目

二、解法

??思路分析：這道題要求我們用棧模擬隊(duì)列（工作上一定沒人這么搞）。程序當(dāng)中，push函數(shù)很好解決，直接將元素push進(jìn)輸入棧當(dāng)中。pop函數(shù)需要實(shí)現(xiàn)隊(duì)列先進(jìn)先出的操作，而棧是先進(jìn)后出。只用一個(gè)棧是無法實(shí)現(xiàn)，需要兩個(gè)棧，一個(gè)輸入棧，一個(gè)輸出棧。輸入棧當(dāng)中，先進(jìn)棧的元素在棧底所以后出，此時(shí)我們將輸入棧的元素push進(jìn)輸出棧，先進(jìn)的元素就在棧頂，會(huì)先輸出，這樣就實(shí)現(xiàn)了先進(jìn)先出的隊(duì)列。peek函數(shù)復(fù)用了pop函數(shù)，實(shí)現(xiàn)代碼縮減。最后empty函數(shù)，只要輸入棧和輸出棧同時(shí)為空那么隊(duì)列就是空的。
??程序如下：

class MyQueue {
public:
    stack<int> stIn;
    stack<int> stOut;
    MyQueue() { // 構(gòu)造函數(shù)

    }

    void push(int x) {
        stIn.push(x);
    }

    int pop() {
        if (stOut.empty()) {   // 只有當(dāng)Out棧為空的時(shí)候，才將In棧的元素全部導(dǎo)入Out棧
            while (!stIn.empty()) { 
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }

    int peek() {
        int res = this->pop();  // 直接使用已經(jīng)寫好的pop函數(shù)
        stOut.push(res);        // 已經(jīng)彈出，再添加回去
        return res;
    }

    bool empty() {
        return stIn.empty() && stOut.empty();
    }
};

復(fù)雜度分析：

• 時(shí)間復(fù)雜度： push和empty為$O(1)$, pop和peek為$O(n)$。
• 空間復(fù)雜度：$O(n)$。

三、完整代碼

# include <iostream>
# include <stack>
using namespace std;

class MyQueue {
public:
    stack<int> stIn;
    stack<int> stOut;
    MyQueue() { // 構(gòu)造函數(shù)

    }

    void push(int x) {
        stIn.push(x);
    }

    int pop() {
        if (stOut.empty()) {   // 只有當(dāng)Out棧為空的時(shí)候，才將In棧的元素全部導(dǎo)入Out棧
            while (!stIn.empty()) { 
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }

    int peek() {
        int res = this->pop();  // 直接使用已經(jīng)寫好的pop函數(shù)
        stOut.push(res);        // 已經(jīng)彈出，再添加回去
        return res;
    }

    bool empty() {
        return stIn.empty() && stOut.empty();
    }
};

int main()
{
    int x = 10;
    MyQueue* obj = new MyQueue();
    obj->push(x);
    obj->push(x);
    int param_2 = obj->pop();
    int param_3 = obj->peek();
    bool param_4 = obj->empty();
	system("pause");
	return 0;
}

end文章來源地址http://www.zghlxwxcb.cn/news/detail-531235.html

到了這里，關(guān)于【算法與數(shù)據(jù)結(jié)構(gòu)】232、LeetCode用棧實(shí)現(xiàn)隊(duì)列的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！