一、stack的介紹和使用

1.1 stack的介紹

• stack 是一種容器適配器，專門用在具有后進(jìn)先出的上下文環(huán)境中。只能從容器的一端進(jìn)行元素的插入與提取操作。

• stack 是作為容器適配器被實(shí)現(xiàn)的，容器適配器即是對(duì)特定類封裝作為其底層的容器，并提供一組特定的成員函數(shù)來(lái)訪問(wèn)其元素，使得元素在特定容器的尾部（棧頂）被壓入和彈出。

• stack 的底層容器可以使任何標(biāo)準(zhǔn)的容器類模板或者一些其它特定的容器類，這些容器類應(yīng)該支持以下操作：

  • empty：判空操作

  • back：獲取尾部元素操作

  • push_back：尾部插入元素操作

  • pop_back：尾部刪除元素操作

• 標(biāo)準(zhǔn)容器 vector、deque、list 均符合這些需求，默認(rèn)情況下，如果沒(méi)有為 stack 指定特定的底層容器，默認(rèn)情況下使用 deque。

1.2 stack的使用

函數(shù)說(shuō)明	接口說(shuō)明
stack()	構(gòu)造空的棧
empty()	檢測(cè)棧 stack 是否為空
size()	返回 stack 中元素的個(gè)數(shù)
top()	返回棧頂元素的引用
push()	將元素 val 壓入 stack 中
pop()	將 stack 中尾部的元素彈出

1.2.1 最小棧

本題的思路是用兩個(gè)棧來(lái)實(shí)現(xiàn)，其中一個(gè)棧 _st 用來(lái)正常存儲(chǔ)數(shù)據(jù)，另一個(gè)棧 _minst 用來(lái)存儲(chǔ)最小的數(shù)據(jù)。具體實(shí)現(xiàn)就是在往 _st 中插入數(shù)據(jù)的時(shí)候進(jìn)行判斷，如果當(dāng)前插入的數(shù)據(jù) val 小于等于 _minst 棧頂?shù)臄?shù)據(jù)，那就將 val 也插入到 _minst 這個(gè)棧中。否則直將數(shù)據(jù)插入 _st 中。在 pop 數(shù)據(jù)的時(shí)候，先取 _st 的棧頂元素和 _minst 的棧頂元素進(jìn)行比較，如果二者相等，那就同時(shí) pop _st 和 _minst 的棧頂元素，否則就值 pop _st 的棧頂元素。要獲取堆棧中的最小元素直接返回 _minst 的棧頂元素即可。

class MinStack 
{
public:MinStack() {}void push(int val) {_st.push(val);if(_minst.empty() || val <= _minst.top()){_minst.push(val);}}void pop() {if(_st.top() == _minst.top()){_minst.pop();}_st.pop();}int top() {return _st.top();}int getMin() {return _minst.top();}
private:stack<int> _st;stack<int> _minst;
};

1.2.2 棧的壓入、彈出序列

本題的解題思路是用一個(gè)棧來(lái)模擬。即先定義一個(gè)棧 st 然后給棧中入一個(gè)數(shù)據(jù)，接著取棧頂?shù)臄?shù)據(jù)和出棧序列 popV 當(dāng)前位置元素進(jìn)行比較進(jìn)行比較，如果不相等則繼續(xù)從入棧序列 pushV 中拿數(shù)據(jù)往棧 st 中入，如果相等就出棧。這里需要注意，有可能需要連續(xù)多次出棧。直到最終將入棧序列 pushV 中的數(shù)據(jù)全入棧，最后判斷棧 st 是否為空，如果為空，就說(shuō)明該出棧序列正確。如果不空就說(shuō)明該出棧序列有問(wèn)題。

class Solution {
public:/*** 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可** * @param pushV int整型vector * @param popV int整型vector * @return bool布爾型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code herestack<int> st;size_t push_pos = 0, pop_pos = 0;while(push_pos < pushV.size()){//先入一個(gè)元素st.push(pushV[push_pos++]);if(st.top() != popV[pop_pos]){//不匹配繼續(xù)入數(shù)據(jù)continue;}while(!st.empty() && st.top() == popV[pop_pos]){//匹配，出數(shù)據(jù)st.pop();pop_pos++;}}return st.empty();}
};

代碼優(yōu)化：我們可以發(fā)現(xiàn)上面代碼中不匹配邏輯里面其實(shí)啥也沒(méi)干，因此我們可以把這段代碼給刪掉，上面加上是為了使邏輯更加清晰。

class Solution {
public:/*** 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可** * @param pushV int整型vector * @param popV int整型vector * @return bool布爾型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code herestack<int> st;size_t push_pos = 0, pop_pos = 0;while(push_pos < pushV.size()){//先入一個(gè)元素st.push(pushV[push_pos++]);while(!st.empty() && st.top() == popV[pop_pos]){//匹配，出數(shù)據(jù)st.pop();pop_pos++;}}return st.empty();}
};

1.2.3 逆波蘭表達(dá)式求值

逆波蘭表達(dá)式也被叫做后綴表達(dá)式。什么是后綴表達(dá)式呢？先來(lái)了解一下中綴表達(dá)式，中綴表達(dá)式就是我們平時(shí)最常見(jiàn)的，例如：$2+3?1$，就是一個(gè)典型的中綴表達(dá)式。將前面的中綴表達(dá)式變成后綴表達(dá)式得到：2 1 3 * +，這就是一個(gè)后綴表達(dá)式，后綴表達(dá)式相較于中中綴表達(dá)式，操作數(shù)順序不變，操作符按優(yōu)先級(jí)重排。這道題目就是要求我們對(duì)后綴表達(dá)式進(jìn)行求解。求解后綴表達(dá)式，我們可以借助一個(gè)棧，遇到操作數(shù)入棧，遇到操作符從棧中出兩個(gè)元素進(jìn)行運(yùn)算，將運(yùn)算結(jié)果繼續(xù)入棧。最終棧頂?shù)脑鼐褪钦麄€(gè)逆波蘭表達(dá)式的結(jié)果。

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> st;size_t pos = 0;while(pos < tokens.size()){if(tokens[pos] != "+" && tokens[pos] != "-" && tokens[pos] != "*" && tokens[pos] != "/"){//如果是數(shù)字就入棧int num = stoi(tokens[pos]);st.push(num);}else{//不是數(shù)字就從棧中取兩個(gè)元素出來(lái)int val1 = st.top();st.pop();int val2 = st.top();st.pop();int ret = 0;if(tokens[pos] == "+"){ret = val2 + val1;}else if(tokens[pos] == "-"){ret = val2 - val1;}else if(tokens[pos] == "*"){ret = val2 * val1;}else if(tokens[pos] == "/"){ret = val2 / val1;}//將計(jì)算結(jié)果繼續(xù)入棧st.push(ret);}pos++;}return st.top();}
};

注意：在寫(xiě)上面這段代碼的時(shí)候有下面幾點(diǎn)需要特別注意，首先這是一個(gè) string 數(shù)組，會(huì)涉及到 string 轉(zhuǎn) int 。其次需要注意在從棧中取數(shù)的時(shí)候，第一次取出的是右操作數(shù)，第二次取出的是左操作數(shù)，因此 val2 應(yīng)該做左操作數(shù)，val1 應(yīng)該做右操作數(shù)，尤其是減法運(yùn)算和除法運(yùn)算，這兩個(gè)操作數(shù)的順序必須得到保證。

補(bǔ)充：這里補(bǔ)充一個(gè)小知識(shí)點(diǎn)：如何將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。主要過(guò)程分為以下幾步：

1. 遇到操作數(shù)就輸出（這里的輸出是將其存儲(chǔ)到某種容器里）。

2. 遇到操作符，根據(jù)優(yōu)先級(jí)的順序分為以下兩種情況：

   • 棧為空或當(dāng)前操作符比棧頂?shù)膬?yōu)先級(jí)高，繼續(xù)入棧。

   • 棧不為空且當(dāng)前操作符比棧頂?shù)膬?yōu)先級(jí)低或者相等，則輸出棧頂操作符，繼續(xù)執(zhí)行第二步。

3. 中綴表達(dá)式結(jié)束后，依次出棧里面的操作符。

小Tips：當(dāng)前操作符能否計(jì)算取決于后一個(gè)操作符的優(yōu)先級(jí)是否高于自己，所以每當(dāng)我們遇到一個(gè)操作符的時(shí)候，先不著急將它入棧，先和棧頂?shù)牟僮鞣M(jìn)行優(yōu)先級(jí)比較，如果當(dāng)前操作符的優(yōu)先級(jí)比棧頂操作符的優(yōu)先級(jí)低或者相等，我們就可以取出棧頂這個(gè)操作符進(jìn)行運(yùn)算。如果遇到括號(hào)可以走一個(gè)遞歸。其次就是需要想辦法確定符號(hào)的優(yōu)先級(jí)。

1.2.4 用棧實(shí)現(xiàn)隊(duì)列

將一個(gè)棧當(dāng)做輸入棧，用于壓入 push 傳入的數(shù)據(jù)，另一個(gè)棧當(dāng)做輸出棧，用于 pop 和 peek 操作。每次 pop 或 peek 時(shí)，若輸出棧為空則將輸入棧的全部數(shù)據(jù)依次彈并壓入輸出棧，這樣輸出棧從棧頂往棧底的順序就是隊(duì)列從隊(duì)首往隊(duì)尾的順序。

class MyQueue {
public:MyQueue() {}void push(int x) {input_st.push(x);}int pop() {if(output_st.empty()){while(!input_st.empty()){output_st.push(input_st.top());input_st.pop();} }int ret = output_st.top();output_st.pop();return ret;}int peek() {if(output_st.empty()){while(!input_st.empty()){output_st.push(input_st.top());input_st.pop();}}return output_st.top();}bool empty() {return input_st.empty() && output_st.empty();}
private:stack<int> input_st;stack<int> output_st;
};

二、queue的介紹和使用

2.1 queue的介紹

• 隊(duì)列是一種容器適配器，專門用于在FIFO上下文中執(zhí)行先進(jìn)先出操作，其中從容器的一端插入元素，另一端提取元素。

• 隊(duì)列作為容器適配器實(shí)現(xiàn)，容器適配器即將特定的容器類封裝最為其底層容器，queue 提供一組特定的成員函數(shù)來(lái)訪問(wèn)其元素。元素從隊(duì)尾入隊(duì)列，從對(duì)頭出隊(duì)列。

• 底層容器可以是標(biāo)準(zhǔn)容器模板之一，也可以是其他專門設(shè)計(jì)的容器類。該底層容器應(yīng)至少支持以下操作：

  • empty：檢查隊(duì)列是否為空

  • size：返回隊(duì)列中有效元素的個(gè)數(shù)

  • front：返回對(duì)頭元素的引用

  • back：返回隊(duì)尾元素的引用

  • push_back：在隊(duì)列尾部入隊(duì)列

  • pop_front：在隊(duì)列頭部出隊(duì)列

• 標(biāo)準(zhǔn)容器類 deque 和 list 滿足了這些要求。默認(rèn)情況下，如果沒(méi)有為 queue 實(shí)例化指定容器類，則使用標(biāo)準(zhǔn)容器 deque。

2.2 queue的使用

函數(shù)聲明	接口說(shuō)明
queue()	構(gòu)造空隊(duì)列
empty()	檢測(cè)隊(duì)列是否為空，是返回 true，否則返回 false
size()	返回隊(duì)列中有效元素個(gè)數(shù)
front()	返回隊(duì)頭元素的引用
back()	返回隊(duì)尾元素的引用
push()	在隊(duì)尾將元素 val 入隊(duì)列
pop()	將隊(duì)頭元素出隊(duì)列

2.2.1 二叉樹(shù)的層序遍歷

二叉樹(shù)的層序遍歷可以借助隊(duì)列來(lái)實(shí)現(xiàn)，從根節(jié)點(diǎn)開(kāi)始，先讓父節(jié)點(diǎn)入隊(duì)列，在出隊(duì)尾節(jié)點(diǎn)的同時(shí)，將該節(jié)點(diǎn)的左孩子和右孩子依次入隊(duì)列。直到隊(duì)列為空，從隊(duì)列中出出來(lái)的結(jié)果就是層序遍歷的結(jié)果。這道題目需要將同一層的所有節(jié)點(diǎn)都存入一個(gè)一維數(shù)組，再將這些一維數(shù)組組合成一個(gè)二維數(shù)組返回。我們前面的這種做法會(huì)導(dǎo)致隊(duì)列中出現(xiàn)兩層節(jié)點(diǎn)混在意的情況，因此我們可以定義一個(gè)變量 levelSize 來(lái)記錄每一層的節(jié)點(diǎn)數(shù)。具體代碼如下：

class Solution 
{
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> retV;queue<TreeNode*> qu;int levelSize = 0;qu.push(root);while(!qu.empty()){vector<int> tmp;levelSize = qu.size();while(levelSize != 0){TreeNode* top = qu.front();if(top != nullptr){tmp.push_back(top->val);qu.push(top->left);qu.push(top->right);} qu.pop();levelSize--;}if(!tmp.empty()){retV.push_back(tmp);}}return retV;}
};

三、模擬實(shí)現(xiàn)

3.1 stack模擬實(shí)現(xiàn)

template<class T, class Continer = vector<T>>class stack{public:stack(){}void push(const T& val){_con.push_back(val);}void pop(){_con.pop_back();}T& top(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Continer _con;};

小Tips：stack 可以使用 vector 或者 list 來(lái)實(shí)現(xiàn)，效率相當(dāng)。插入數(shù)據(jù)就相當(dāng)于尾插，刪除棧頂元素就相當(dāng)于尾刪。

3.2 queue模擬實(shí)現(xiàn)

template<class T, class Continer = std::list<T>>
class queue
{
public:queue(){}void push(const T& val){_con.push_back(val);}void pop(){_con.pop_front();//這里不再支持vector}T& front(){return _con.front();}T& back(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}
private:Continer _con;
};

小Tips：棧不能借助 vector 來(lái)實(shí)現(xiàn)，因?yàn)槌鲫?duì)列，相當(dāng)于刪除 vector 中的第一個(gè)元素，而對(duì) vector 頭刪會(huì)涉及挪動(dòng)數(shù)據(jù)，效率相較于 list 會(huì)有所下降。

四、容器適配器

4.1 什么是適配器？

適配器是一種設(shè)計(jì)模式（設(shè)計(jì)模式是一套被反復(fù)使用的、多數(shù)人知曉的、經(jīng)過(guò)分類編目的、代碼設(shè)計(jì)經(jīng)驗(yàn)的總結(jié)），該種模式是將一個(gè)類的接口轉(zhuǎn)換成客戶希望的另外一個(gè)接口。

4.2 STL標(biāo)準(zhǔn)庫(kù)中stack和queue的底層結(jié)構(gòu)

雖然 stack 和 queue 中也可以存放元素，但在 STL 中并沒(méi)有將其劃分在容器行列，而是將其稱為容器適配器，這是因?yàn)?stack 和 queue 只是對(duì)其他容器的接口進(jìn)行了包裝，STL 中 stack 和 queue 默認(rèn)使用 deque。

4.3 deque的簡(jiǎn)單介紹

4.3.1 deque的原理介紹

deque（雙端隊(duì)列）：是一種雙開(kāi)口的“連續(xù)”空間的數(shù)據(jù)結(jié)構(gòu)，雙開(kāi)口的含義是：可以在頭尾兩端進(jìn)行插入和刪除操作，且時(shí)間復(fù)雜度為O(1)，與 vector 比較，頭插效率高，不需要搬移元素；與 list 比較，空間利用率比較高。

deque并不是真正連續(xù)的空間，而是由一段段連續(xù)的小空間拼接而成的，實(shí)際 deque 類似于一個(gè)動(dòng)態(tài)的二維數(shù)組，其底層結(jié)構(gòu)如下圖所示：

雙端隊(duì)列底層是一段假象的連續(xù)空間，實(shí)際是分段連續(xù)的，為了維護(hù)其“整體連續(xù)”以及隨機(jī)訪問(wèn)的假象，落在了 deque 的迭代器身上，因此 deque 的迭代器設(shè)計(jì)的就比較復(fù)雜，如下圖所示：

4.3.2 deque的缺陷

• 與 vector 比較，deque 的優(yōu)勢(shì)是：頭部插入和刪除時(shí)，不需要搬移元素，效率特別高，而且在擴(kuò)容時(shí)，也不需要搬移大量的元素，因此其效率是比 vector 高的。

• 與 list 比較，其底層空間是連續(xù)的，空間利用率比較高，不需要存儲(chǔ)額外字段。

• 但是，deque 有一個(gè)致命缺陷：不適合遍歷，因?yàn)樵诒闅v時(shí)，deque 的迭代器要頻繁的去檢測(cè)其是否移動(dòng)到某段小空間的邊界，導(dǎo)致效率低下，而序列式場(chǎng)景中，可能需要經(jīng)常遍歷，因此在實(shí)際中，需要線性結(jié)構(gòu)式，大多數(shù)情況下優(yōu)先考慮 vector 和 list，deque 的應(yīng)用并不多，而目前能看到的一個(gè)應(yīng)用場(chǎng)景就是，STL 用其作為 stack 和 queue 的底層數(shù)據(jù)結(jié)構(gòu)。

4.4 為什么選擇deque作為stack和queue的底層默認(rèn)容器？

stack 是一種后進(jìn)先出的特殊線性數(shù)據(jù)結(jié)構(gòu)，因此只要是具有 push_back() 和 pop_back() 操作的線性結(jié)構(gòu)，都可以作為 stack 的底層容器，比如 vector 和 list 都可以；queue 是先進(jìn)先出的特殊線性數(shù)據(jù)結(jié)構(gòu)，只要具有 push_back() 和 pop_front() 操作的線性結(jié)構(gòu)，都可以作為 queue de 底層容器，比如 list。但是 STL 中對(duì) stack 和 queue 默認(rèn)選擇 deque 作為其底層容器，主要是因?yàn)?#xff1a;

• stack 和 queue 不需要遍歷（因此 stack 和 queue 沒(méi)有迭代器），只需要在固定的一端或者兩端進(jìn)行操作。

• 在 stack 中元素增長(zhǎng)時(shí)，deque 比 vector 的效率高（擴(kuò)容時(shí)不需要搬移大量數(shù)據(jù)）；queue 中的元素增長(zhǎng)時(shí)，deque 不僅效率高，而且內(nèi)存利用率高。

五、結(jié)語(yǔ)

今天的分享到這里就結(jié)束啦！如果覺(jué)得文章還不錯(cuò)的話，可以三連支持一下，春人的主頁(yè)還有很多有趣的文章，歡迎小伙伴們前去點(diǎn)評(píng)，您的支持就是春人前進(jìn)的動(dòng)力！