C++之stack類(lèi)的代碼及其邏輯舉例詳解
1. stack介紹及使用方法
stack是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu),所以在C++的STL庫(kù)中也同樣遵循了這一點(diǎn),我們?cè)谑褂玫臅r(shí)候
不支持隨機(jī)訪(fǎng)問(wèn)或迭代器遍歷。
注意事項(xiàng)
- 調(diào)用
top()
或pop()
前需確保棧非空,否則可能引發(fā)未定義行為。 stack
沒(méi)有clear()
函數(shù),如需清空棧需手動(dòng)循環(huán)調(diào)用pop()
。- 性能:所有操作的時(shí)間復(fù)雜度為 O(1)。
stack的底層是一個(gè) deque<T>(雙端隊(duì)列),雖然deque是可以從兩端來(lái)進(jìn)行操作的,但是我們只要只提供一端的接口,那么就可以來(lái)把它當(dāng)做stack來(lái)使用。
我們?cè)诳臻g上要把它理解成這個(gè)樣子,瘟疫這樣更好理解。
2. stack的常用接口
函數(shù)名 | 作用 |
---|---|
void push(const T& x) | 放一個(gè)元素進(jìn)入stack |
void pop() | 拋出一個(gè)元素 |
T& top() | 返回最后一個(gè)放入的元素 |
size_t size() | 返回stack里面的元素個(gè)數(shù) |
bool empty() | 判斷是否為空 |
接下來(lái)我會(huì)一一實(shí)現(xiàn)這些端口。
3. template
在這里寫(xiě)兩個(gè)calss是為了方便使用,這兩個(gè)模板參數(shù)實(shí)際上是各司其職,只是語(yǔ)法上要求寫(xiě)在同一個(gè) template<>
里,使用時(shí)會(huì)根據(jù)場(chǎng)景自動(dòng)匹配對(duì)應(yīng)的參數(shù)。
- 前面的
T
是明確指定棧中元素的類(lèi)型(比如int
、string
等),這是棧對(duì)外提供的 “數(shù)據(jù)類(lèi)型契約”—— 棧里只能存T
類(lèi)型的東西。- 后面的
Container
是指定用什么容器來(lái)存儲(chǔ)這些 T 類(lèi)型的元素,而默認(rèn)的deque<T>
就是 “用雙端隊(duì)列來(lái)存T
類(lèi)型元素” 的意思。
PS:只寫(xiě)后面那一個(gè)理論上來(lái)說(shuō)也是可以的,但是會(huì)讓用戶(hù)使用門(mén)檻變高,比如想聲明一個(gè)存 int 的棧,用戶(hù)不能直接寫(xiě) stack<int>,而必須寫(xiě)成 stack<deque<int>>(如果想用默認(rèn)容器),或者 stack<vector<int>>。這會(huì)讓接口變得不直觀(guān) —— 用戶(hù)需要先知道底層容器的類(lèi)型,才能正確聲明棧,違背了 “棧是容器適配器,用戶(hù)無(wú)需關(guān)心底層實(shí)現(xiàn)” 的設(shè)計(jì)初衷。
PS:只寫(xiě)前面哪一個(gè)是不行的,如果只寫(xiě) template<class T>,就意味著用戶(hù)無(wú)法指定底層容器了 —— 因?yàn)闆](méi)有 Container 這個(gè)參數(shù)來(lái)接收用戶(hù)自定義的容器類(lèi)型。
template<class T, class Container = deque<T>>
4. private
這就是申明一個(gè)私有成員_con。
private: Container _con;
5.pop()
拋出最后一個(gè)元素(因?yàn)槭呛筮M(jìn)先出)。
void pop() { _con.pop_back(); }
6. top()
返回最后一個(gè)元素(不拋出)。
T& top() { return _con.back(); }
7. size()
返回stack里面元素的個(gè)數(shù)。
size_t size() { return _con.size(); }
8.empty
判斷是否為空,為空的話(huà)就返回true。
bool empty() { return _con.empty(); }
9. push()
在尾部的位置上插入一個(gè)元素。
void push(const T& x) { _con.push_back(x); }
10. 總結(jié)
stack到這邊就講完了,作為 C++ 中常用的容器適配器,以簡(jiǎn)潔的接口和靈活的底層設(shè)計(jì),為 LIFO 場(chǎng)景提供了高效支持。理解其底層依賴(lài)deque
的原因、掌握核心接口的使用規(guī)范,能幫助開(kāi)發(fā)者在實(shí)際場(chǎng)景中更合理地選擇和使用stack
,避免因誤用接口導(dǎo)致的邏輯錯(cuò)誤。
以下是完整代碼:
#pragma once #include<vector> #include<deque> namespace struggle { // template<class T, class Container = deque<T>> class stack { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_back(); } T& top() { return _con.back(); } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } private: Container _con; };
總結(jié)
到此這篇關(guān)于C++之stack類(lèi)的代碼及其邏輯的文章就介紹到這了,更多相關(guān)C++ stack類(lèi)代碼內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
一篇文章帶你了解C語(yǔ)言中volatile關(guān)鍵字
這篇文章主要給大家介紹了關(guān)于C語(yǔ)言中volatile關(guān)鍵字,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-09-09關(guān)于虛函數(shù)實(shí)現(xiàn)多態(tài)的原理及分析
這篇文章主要介紹了C++中如何實(shí)現(xiàn)多態(tài)問(wèn)題,具有很好的參考價(jià)值,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-02-02C++ 中malloc()和free()函數(shù)的理解
這篇文章主要介紹了C++ 中malloc()和free()函數(shù)的理解的相關(guān)資料,這里提供用法示例幫助大家理解這部分知識(shí),需要的朋友可以參考下2017-08-08C++編程使用findfirst和findnext查找及遍歷文件實(shí)現(xiàn)示例
這篇文章主要為大家介紹了C++編程如何使用findfirst和findnext查找及遍歷文件實(shí)現(xiàn)示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助2021-10-10C語(yǔ)言實(shí)現(xiàn)大數(shù)據(jù)文件的內(nèi)存映射機(jī)制
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)大數(shù)據(jù)文件的內(nèi)存映射機(jī)制的相關(guān)資料,需要的朋友可以參考下2017-01-01C++采用TLS線(xiàn)程局部存儲(chǔ)的用法實(shí)例
這篇文章主要介紹了C++采用TLS線(xiàn)程局部存儲(chǔ)的用法實(shí)例,詳細(xì)講述了TLS索引及線(xiàn)程的操作,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2014-10-10C語(yǔ)言中6組指針和自增運(yùn)算符結(jié)合方式的運(yùn)算順序問(wèn)題
本文通過(guò)代碼實(shí)現(xiàn)分析了6種組合:* p++,(* p)++,* (p++),++* p,++( * p), * (++p),需要的朋友可以參考下2015-07-07