C++棧、隊列

文章目錄

目錄

文章目錄

前言

一、stack、queue介紹

? ? ? ?1.stack

????????2.queue

二、stack、queue的習題

? ? ? ? 1. 最小棧

2. 棧的壓入、彈出序列

3.二叉樹的層序遍歷

三、stack和queue的模擬實現

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

2.queue的模擬實現


前言

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


一、stack、queue介紹

? ? ? ?1.stack

????????stack的文檔介紹icon-default.png?t=N7T8https://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)icon-default.png?t=N7T8https://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)icon-default.png?t=N7T8https://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)icon-default.png?t=N7T8https://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)icon-default.png?t=N7T8https://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;};
}

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

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/bicheng/21542.shtml
繁體地址,請注明出處:http://hk.pswp.cn/bicheng/21542.shtml
英文地址,請注明出處:http://en.pswp.cn/bicheng/21542.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Go Go-Simple-Mail包進行批量SMTP郵件發送

go-simple-mail 包提供了一種簡便的方式來處理和發送郵件。這個包支持保持活動連接、TLS和SSL加密協議,非常適合批量SMTP郵件發送需求。 1、安裝Go-Simple-Mail包 go get -u github.com/xhit/go-simple-mail/v2 2、配置SMTP服務器連接 go-simple-mail包支持多種SMTP服務器…

強達電路營收下滑凈利潤急劇放緩:周轉率驟降,2次因環保被罰

《港灣商業觀察》施子夫 自2022年6月向深交所創業板遞交招股書起&#xff0c;深圳市強達電路股份有限公司&#xff08;以下簡稱&#xff0c;強達電路&#xff09;已收到深交所下發的兩輪審核問詢函&#xff0c;并且公司已于2023年3月31日順利過會。但由于遲遲未提交注冊申請&a…

無實驗數據指導蛋白質定向進化,上海交大洪亮課題組發表微環境感知圖神經網絡 ProtLGN

在現代生物技術和醫藥研究中&#xff0c;蛋白質工程扮演著至關重要的角色。通過修改蛋白質的氨基酸序列&#xff0c;蛋白質工程可以改善或賦予蛋白質新的生物化學性質&#xff0c;如增強酶的催化效率、提高藥物的親和力或改善其熱穩定性。這些改進對于開發新藥、治療疾病以及提…

lua vm 一: attempt to yield across a C-call boundary 的原因分析

使用 lua 的時候有時候會遇到這樣的報錯&#xff1a;“attempt to yield across a C-call boundary”。 1. 網絡上的解釋 可以在網上找到一些關于這個問題的解釋。 1.1 解釋一 這個 issue&#xff1a;一個關于 yield across a C-call boundary 的問題&#xff0c;云風的解釋是…

【最新鴻蒙應用開發】——實用廣告思路,可動態修改(方便運營)

鴻蒙項目加入廣告展示頁業務 廣告頁的思路——華為有廣告業務&#xff0c;但是我們不用- ad模塊&#xff1b; 想自定義廣告——場景&#xff1a; app啟動-有廣告需求&#xff0c;就打開廣告頁&#xff0c;沒有的話就去登錄或者主頁&#xff1b; 騰訊體育的廣告- 啟動有廣告頁…

適合小白學習的項目1894java開發ssm框架校園跑腿管理系統myeclipse開發mysql數據庫springMVC模式java編程計算機網頁設計

一、源碼特點 java ssm 校園跑腿管理系統是一套完善的web設計系統&#xff08;系統采用SSM框架進行設計開發&#xff0c;springspringMVCmybatis&#xff09;&#xff0c;對理解JSP java編程開發語言有幫助&#xff0c;系統具有完整的源代碼和數據庫&#xff0c;系統主要采…

Java項目:96 springboot精品在線試題庫系統

作者主頁&#xff1a;舒克日記 簡介&#xff1a;Java領域優質創作者、Java項目、學習資料、技術互助 文中獲取源碼 項目介紹 這次開發的精品在線試題庫系統有管理員&#xff0c;教師&#xff0c;學生三個角色。 管理員功能有個人中心&#xff0c;專業管理&#xff0c;學生管理…

比較(二)利用python繪制雷達圖

比較&#xff08;二&#xff09;利用python繪制雷達圖 雷達圖&#xff08;Radar Chart&#xff09;簡介 雷達圖可以用來比較多個定量變量&#xff0c;也可以用于查看數據集中變量的得分高低&#xff0c;是顯示性能表現的理想之選。缺點是變量過多容易造成閱讀困難。 快速繪制…

Go語言 一些問題了解

一、讀取文件數據&#xff0c;是阻塞還是非阻塞的&#xff1f; 分兩種情況&#xff1a;常規讀取文件數據&#xff0c;和網絡IO讀取數據 1. 常規讀取文件數據&#xff1a; io.Reader 和 bufio.Reader 是同步進行的。 bufio.Reader 提供緩沖的讀取操作&#xff0c;意味著數據是…

網站入門:Flask用法講解

Flask是一個使用Python編寫的輕量級Web服務框架&#xff0c;旨在幫助開發人員快速構建和部署Web應用程序。下面將對Flask進行更為詳細的解釋說明&#xff0c;并展示其使用示例與注意事項&#xff1a; 1.解釋說明 定義及特點: Flask以其簡潔和靈活著稱&#xff0c;允許開發者以…

C++:list模擬實現

hello&#xff0c;各位小伙伴&#xff0c;本篇文章跟大家一起學習《C&#xff1a;list模擬實現》&#xff0c;感謝大家對我上一篇的支持&#xff0c;如有什么問題&#xff0c;還請多多指教 &#xff01; 如果本篇文章對你有幫助&#xff0c;還請各位點點贊&#xff01;&#xf…

LeetCode題練習與總結:二叉樹展開為鏈表--114

一、題目描述 給你二叉樹的根結點 root &#xff0c;請你將它展開為一個單鏈表&#xff1a; 展開后的單鏈表應該同樣使用 TreeNode &#xff0c;其中 right 子指針指向鏈表中下一個結點&#xff0c;而左子指針始終為 null 。展開后的單鏈表應該與二叉樹 先序遍歷 順序相同。 …

深入探討Java字符串拼接的藝術

引言 在Java編程中&#xff0c;字符串是最基本的數據類型之一。字符串拼接是開發過程中一個非常常見的操作&#xff0c;無論是構建用戶界面的文本&#xff0c;還是生成日志信息&#xff0c;都離不開字符串的拼接。然而&#xff0c;字符串拼接的效率和正確性常常被開發者忽視&a…

格式化數據恢復指南:從備份到實戰,3個技巧一網打盡

朋友們&#xff01;你們有沒有遇到過那種“啊&#xff0c;我的文件呢&#xff1f;”的尷尬時刻&#xff1f;無論是因為手滑、電腦抽風還是其他原因&#xff0c;數據丟失都可能會讓我們抓狂&#xff0c;甚至有時候&#xff0c;我們可能一不小心就把存儲設備格式化了&#xff0c;…

香橙派OrangePI AiPro測評 【運行qt,編解碼,xfreeRDP】

實物 為AI而生 打開盒子 配置 扛把子的 作為業界首款基于昇騰深度研發的AI開發板&#xff0c;Orange Pi AIpro無論在外觀上、性能上還是技術服務支持上都非常優秀。采用昇騰AI技術路線&#xff0c;集成圖形處理器&#xff0c;擁有8GB/16GB LPDDR4X&#xff0c;可以外接32…

進程通信——管道

什么是進程通信&#xff1f; 進程通信是實現進程間傳遞數據信息的機制。要實現數據信息傳遞就要進程間共享資源——內存空間。那么是哪塊內存空間呢&#xff1f;進程間是相互獨立的&#xff0c;一個進程不可能訪問其他進程的內存空間&#xff0c;那么這塊空間只能由操作系統提…

什么是RPA自動化辦公?

RPA自動化辦公&#xff1a;提升效率的利器 如今&#xff0c;自動化辦公已成為提升效率、減少錯誤、節省成本的關鍵手段。RPA&#xff08;機器人流程自動化&#xff0c;Robotic Process Automation&#xff09;作為其中的重要組成部分&#xff0c;正受到越來越多企業的青睞。那…

【全開源】簡單商城系統源碼(PC/UniAPP)

提供PC版本、UniAPP版本(高級授權)、支持多規格商品、優惠券、積分兌換、快遞鳥電子面單、支持移動端樣式、統計報表等 提供全部前后臺無加密源代碼、數據庫離線部署。 構建您的在線商店的基石 一、引言&#xff1a;為什么選擇簡單商城系統源碼&#xff1f; 在數字化時代&am…

【Spring Cloud Alibaba】初識Spring Cloud Alibaba

目錄 回顧主流的微服務框架Spring Cloud 版本簡介Spring Cloud以往的版本發布順序排列如下&#xff1a; 由停更引發的"升級慘案"哪些Netflix組件被移除了&#xff1f; 替換方案服務注冊中心&#xff1a;服務調用&#xff1a;負載均衡&#xff1a;服務降級&#xff1a…

Python—面向對象小解(6)-閉包、裝飾器

一、閉包 在Python中&#xff0c;閉包&#xff08;closure&#xff09;是一個函數對象&#xff0c;即使在其詞法作用域外被調用&#xff0c;它仍然能訪問該作用域內的變量。閉包通過“捕獲”周圍作用域的變量&#xff0c;保持這些變量的狀態&#xff0c;即使在外部函數已經返回…