C++之stack類的代碼及其邏輯舉例詳解
1. stack介紹及使用方法
stack是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu),所以在C++的STL庫中也同樣遵循了這一點(diǎn),我們在使用的時(shí)候
不支持隨機(jī)訪問或迭代器遍歷。
注意事項(xiàng)
- 調(diào)用
top()
或pop()
前需確保棧非空,否則可能引發(fā)未定義行為。 stack
沒有clear()
函數(shù),如需清空棧需手動(dòng)循環(huán)調(diào)用pop()
。- 性能:所有操作的時(shí)間復(fù)雜度為 O(1)。
stack的底層是一個(gè) deque<T>(雙端隊(duì)列),雖然deque是可以從兩端來進(jìn)行操作的,但是我們只要只提供一端的接口,那么就可以來把它當(dāng)做stack來使用。
我們在空間上要把它理解成這個(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() | 判斷是否為空 |
接下來我會(huì)一一實(shí)現(xiàn)這些端口。
3. template
在這里寫兩個(gè)calss是為了方便使用,這兩個(gè)模板參數(shù)實(shí)際上是各司其職,只是語法上要求寫在同一個(gè) template<>
里,使用時(shí)會(huì)根據(jù)場景自動(dòng)匹配對(duì)應(yīng)的參數(shù)。
- 前面的
T
是明確指定棧中元素的類型(比如int
、string
等),這是棧對(duì)外提供的 “數(shù)據(jù)類型契約”—— 棧里只能存T
類型的東西。- 后面的
Container
是指定用什么容器來存儲(chǔ)這些 T 類型的元素,而默認(rèn)的deque<T>
就是 “用雙端隊(duì)列來存T
類型元素” 的意思。
PS:只寫后面那一個(gè)理論上來說也是可以的,但是會(huì)讓用戶使用門檻變高,比如想聲明一個(gè)存 int 的棧,用戶不能直接寫 stack<int>,而必須寫成 stack<deque<int>>(如果想用默認(rèn)容器),或者 stack<vector<int>>。這會(huì)讓接口變得不直觀 —— 用戶需要先知道底層容器的類型,才能正確聲明棧,違背了 “棧是容器適配器,用戶無需關(guān)心底層實(shí)現(xiàn)” 的設(shè)計(jì)初衷。
PS:只寫前面哪一個(gè)是不行的,如果只寫 template<class T>,就意味著用戶無法指定底層容器了 —— 因?yàn)闆]有 Container 這個(gè)參數(shù)來接收用戶自定義的容器類型。
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
判斷是否為空,為空的話就返回true。
bool empty() { return _con.empty(); }
9. push()
在尾部的位置上插入一個(gè)元素。
void push(const T& x) { _con.push_back(x); }
10. 總結(jié)
stack到這邊就講完了,作為 C++ 中常用的容器適配器,以簡潔的接口和靈活的底層設(shè)計(jì),為 LIFO 場景提供了高效支持。理解其底層依賴deque
的原因、掌握核心接口的使用規(guī)范,能幫助開發(fā)者在實(shí)際場景中更合理地選擇和使用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類的代碼及其邏輯的文章就介紹到這了,更多相關(guān)C++ stack類代碼內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
關(guān)于虛函數(shù)實(shí)現(xiàn)多態(tài)的原理及分析
這篇文章主要介紹了C++中如何實(shí)現(xiàn)多態(tài)問題,具有很好的參考價(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語言實(shí)現(xiàn)大數(shù)據(jù)文件的內(nèi)存映射機(jī)制
這篇文章主要介紹了C語言實(shí)現(xiàn)大數(shù)據(jù)文件的內(nèi)存映射機(jī)制的相關(guān)資料,需要的朋友可以參考下2017-01-01C語言中6組指針和自增運(yùn)算符結(jié)合方式的運(yùn)算順序問題
本文通過代碼實(shí)現(xiàn)分析了6種組合:* p++,(* p)++,* (p++),++* p,++( * p), * (++p),需要的朋友可以參考下2015-07-07