文章目錄

? ? ? ? 棧和隊列是倆種特殊的容器，C++在實現棧和隊列時，復用了vector和list容器。本章內容我們將介紹和模擬實現stack(棧)和queue(隊列)。以及做幾道關于stack和queue的題。加深對stack和queue的理解。

---

一、stack、queue介紹

? ? ? ?1.stack

????????stack的文檔介紹https://legacy.cplusplus.com/reference/stack/stack/?kw=stack

翻譯：
????????1. stack是一種容器適配器，專門用在具有后進先出操作的上下文環境中，其刪除只能從容器的一端進行元素的插入與提取操作。
????????2. stack是作為容器適配器被實現的，容器適配器即是對特定類封裝作為其底層的容器，并提供一組特定的成員函數來訪問其元素，將特定類作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出。
????????3. stack的底層容器可以是任何標準的容器類模板或者一些其他特定的容器類，這些容器類應該支持以下操作：

????????empty：判空操作
????????back：獲取尾部元素操作
????????push_back：尾部插入元素操作
????????pop_back：尾部刪除元素操作

????????4. 標準容器vector、deque、list均符合這些需求，默認情況下，如果沒有為stack指定特定的底層容器，默認情況下使用deque。

stack的接口：

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

????????2.queue

????????queue - C++ Reference (cplusplus.com)https://legacy.cplusplus.com/reference/queue/queue/翻譯：
????????1. 隊列是一種容器適配器，專門用于在FIFO上下文(先進先出)中操作，其中從容器一端插入元素，另一端提取元素。
????????2. 隊列作為容器適配器實現，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數來訪問其元素。元素從隊尾入隊列，從隊頭出隊列。
????????3. 底層容器可以是標準容器類模板之一，也可以是其他專門設計的容器類。該底層容器應至少支持以下操作:

empty：檢測隊列是否為空
size：返回隊列中有效元素的個數
front：返回隊頭元素的引用
back：返回隊尾元素的引用
push_back：在隊列尾部入隊列
pop_front：在隊列頭部出隊列

????????4. 標準容器類deque和list滿足了這些要求。默認情況下，如果沒有為queue實例化指定容器類，則使用標準容器deque。

queue的接口：

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

二、stack、queue的習題

? ? ? ? 1. 最小棧

155. 最小棧 - 力扣（LeetCode）https://leetcode.cn/problems/min-stack/

? ? ? ?思路：使用倆個棧，一個棧用于存儲所有數據，另一個棧用于記錄動態記錄最小數據(棧頂為最小數據).

????????

? ? ? ? 1.如果st為空，第一次Push時，minst也應該push。

? ? ? ? 2.在之后的每一次push，都要與minst的棧頂元素進行比較，如果<=minst棧頂元素，minst就也需要push該數據。否則只需要push到st。如圖，push了1、2、0.最小的就是minst棧頂元素。

? ? ? ? （等于的時候minst也要push的原因，是因為pop時，如果有倆個相同的最小元素，最終最小元素不會記錄）：

? ? ? ? 如圖再次push0，但未記錄，pop 0 時minst棧頂結果不對。

? ? ? ? 3.在每次pop的時候和minst棧頂元素進行比較，如果等于棧頂元素則minst也需要pop掉。（因為在2步驟我們保證了minst的棧頂是最小值）

代碼：

class MinStack {
public:MinStack() {//構造可以不寫，因為stack是自定義類型會自動調用它的構造。}void push(int val) {//minst為空minst push。不為空進行比較st.push(val);if(minst.empty() || st.top() <= minst.top()){minst.push(val);}}void pop() {//和minst棧頂元素相同minst popif(st.top() == minst.top()){minst.pop();}st.pop();}int top() {return st.top();}int getMin() {return minst.top();}stack<int> st;stack<int> minst;
};

2. 棧的壓入、彈出序列

棧的壓入、彈出序列_牛客題霸_牛客網 (nowcoder.com)https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

? ? ? ? 已知入棧和出棧序列：vector<int>

首先我們需要有一個棧，按照入棧序列的順序進行入棧。

思路：

? ? ? ? 1.先入一個棧。

? ? ? ? 2.s的棧頂元素和popV的棧頂元素（順序就是出棧順序）比較：
? ? ? ? ? ? ? ? a.如果相同，出棧序列往后走，棧頂元素pop掉。（說明以及匹配了出棧的順序）

相同了，pop掉4，popi往后走。

? ? ? ? ? ? ? ? b.如果不相同，回到第1步，繼續入棧，然后比較。知道pushV入完。下面是不相同：

結束條件：
? ? ? ? 遍歷pushV有倆種結果：
1.遍歷完pushV，popV結束,st為空

2.遍歷往pushV，st不為空，popV沒走完。

代碼：

class Solution {
public:bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code heresize_t popi = 0, pushi = 0;stack<int> s;for(; pushi < pushV.size(); pushi++){//先入一個s.push(pushV[pushi]);//進行比較while(!s.empty() && s.top() == popV[popi]){//如果出棧和popV匹配，則s出棧，比較下一個出棧的。popi++;s.pop();}//如果不匹配//接著入棧}//結束條件,倆種結果都要遍歷完pushV。//最后可以判斷st是否為空。或者popi是否等于出棧序列的大小return s.empty();//return popi == popV.size();}
};

3.二叉樹的層序遍歷

102. 二叉樹的層序遍歷 - 力扣（LeetCode）https://leetcode.cn/problems/binary-tree-level-order-traversal/description/二叉樹的層序遍歷要使用到隊列。

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> q;q.push(root);//插入頭節點while(!q.empty()){//頭節點出TreeNode* front = q.front();q.pop();//孩子節點入.不為空再入if(front->left)q.push(front->left);if(front->right)q.push(front->right);}}
};

思路：使用一個levesize變量控制一層一層出。

第一層：1個數據。

levesize = 1；

第一層出完之后：

下一層的個數是q.size();

重置levesize = q.size();

第二層是：第一層孩子的個數。
所以控制levesize--。就可以將每一層的儲存到二維數組里。

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> vv;if(root == nullptr){return vv;}queue<TreeNode*> q;q.push(root);//插入頭節點int levelsize = 1;while(!q.empty()){vector<int> v;while(levelsize--){ //頭節點出TreeNode* front = q.front();q.pop();//將這一層的值存儲到一維數組里v.push_back(front->val);//孩子節點入.不為空再入if(front->left)q.push(front->left);if(front->right)q.push(front->right);}vv.push_back(v);//下一層的個數是q.size()levelsize = q.size();   }return vv;}
};

三、stack和queue的模擬實現

? ? ? ? 1.stack的模擬實現

從棧的接口中可以看出，棧實際是一種特殊的vector，因此使用vector完全可以模擬實現stack。

#include<vector>
namespace mystack
{template<class T>class stack{public:stack() {};void push(const T& x) {_c.push_back(x);}void pop() {_c.pop_back();}T& top() {return _c.back();}const T& top()const {return _c.back();}size_t size()const {return _c.size();}bool empty()const {return _c.empty();}private:std::vector<T> _c;};
}

? ? ? ? 像上面這樣修改起來不方便，可以增加模板參數：

#include <iostream>
using namespace std;
#include <vector>
#include <list>
#include <deque>
namespace mystack
{template<class T, class Container = vector<T>>class stack{public:stack(){};//入棧void push(const T& data){_con.push_back(data);}//出棧void pop(){_con.pop_back();}//棧頂數T top(){return _con.back();}//判空bool empty(){return _con.empty();}//數據size_t size(){return _con.size();}private:Container _con;};
}

2.queue的模擬實現

????????因為queue的接口中存在頭刪和尾插，因此使用vector來封裝效率太低，故可以借助list來模擬實現queue，具體如下：

#include <iostream>
using namespace std;
#include <vector>
#include <list>
#include <deque>namespace myqueue {template<class T, class Container = list<T> > class queue{public:queue() {};//插入void push(const T& data){_con.push_back(data);}//popvoid pop(){_con.pop_front();}T& front(){return _con.front();}T& back(){return _con.back();}const T& front(){return _con.front();}	const T& back(){return _con.front();}//emptybool empty(){return _con.empty();}//sizesize_t size(){return _con.size();}private:Container _con;};
}

---

如果你有所收獲，可以留下你的點贊和關注。謝謝你的觀看！！！