棧(stack)
什么是棧?
棧是一種線性的數(shù)據(jù)結(jié)構(gòu),其是一種運(yùn)算受限(限定僅在表尾進(jìn)行插入和刪除的線性表)的線性表。棧的結(jié)構(gòu)類似下圖的容器:
如上圖所示,棧的結(jié)構(gòu)就像一個(gè)端封閉,另一端開口的容器,往容器放入小球(對(duì)應(yīng)棧中的元素),先放入的小球就越靠近容器的底部,最早進(jìn)入的小球?qū)?yīng)的位置就是 棧底 (bottom),最后放入的小球?qū)?yīng)的位置就是 棧頂 (top),放入小球的動(dòng)作就叫做 入棧 (push);取出小球的時(shí)候,只能按照放入順序相反的順序來取,即先取后放入的,再去先放入的,每次取小球的動(dòng)作就叫做 出棧 (pop)。由于棧的單端口進(jìn)出的限制,決定了棧中的元素只能先進(jìn)后出(FILO, First In Last Out)。棧的數(shù)據(jù)結(jié)構(gòu)可以使用數(shù)組來實(shí)現(xiàn),也可以用鏈表來實(shí)現(xiàn),具體如下圖所示:
棧的基本操作和應(yīng)用
入棧(push)
入棧就是把元素存放入棧中,由于棧的結(jié)構(gòu)只允許從一次存放元素,所以新元素的存入后所在的位置就是該棧新的棧頂,我們以棧的數(shù)組實(shí)現(xiàn)為例,入棧的過程如下圖所示:
出棧(pop)
出棧就是把元素從棧中彈出,同樣的由于棧結(jié)構(gòu)單端進(jìn)出的限制,出棧時(shí)候的元素就是棧頂對(duì)應(yīng)的元素,取出元素后,出棧元素前面的那個(gè)元素對(duì)應(yīng)的位置將變成新的棧頂。出棧的過程如下:
入棧和出棧的復(fù)雜度和應(yīng)用場(chǎng)景
由于棧的后進(jìn)先出的特性,使得入棧和出棧只會(huì)影響到棧中最后一個(gè)元素,不會(huì)涉及到其他元素的移動(dòng),因此入棧和出棧的時(shí)間復(fù)雜都為。同樣的,棧的先入后出的特性,也使得棧不能擁有遍歷、隨機(jī)訪問和隨機(jī)插入的功能。
由于棧的特殊結(jié)構(gòu),棧常用于以下場(chǎng)景:
- 逆序輸出:由于棧先入后出的特性,使用棧結(jié)構(gòu)可以輕松實(shí)現(xiàn)逆序輸出的操作。
- 語法檢測(cè):對(duì)于一些成對(duì)出現(xiàn)的符號(hào),如"[]"、"()"等,凡是遇到符號(hào)的前半部分,即入棧(push)該符號(hào),凡是遇到括號(hào)后半部分的,就與棧頂元素進(jìn)行匹配,如果匹配成功,則出棧(pop),否則就是匹配失敗,語法錯(cuò)誤。
- 數(shù)字進(jìn)制轉(zhuǎn)換:順序計(jì)算,繼續(xù)結(jié)果逆序輸出。
棧的應(yīng)用場(chǎng)景還有很多,這里就不一一舉例,實(shí)際上棧的應(yīng)用都是基于棧的先入后出的特性。
類模板std::satck
stack類是C++標(biāo)準(zhǔn)庫提供的一個(gè)容器適配器,它給使用者提供了棧的功能,實(shí)現(xiàn)的棧的先進(jìn)后出(FILO)的數(shù)據(jù)結(jié)構(gòu),并提供了特定的函數(shù)集合,其定義如下所示:
template<
class T,
class Container = std::deque< T >
> class stack;
該類模板在頭文件中定義。
形參T和Container
- T :代表存儲(chǔ)元素的類型
- Container :用于存儲(chǔ)元素的底層容器類型。該類型必須滿足序列容器的要求,同時(shí)該容器類型能夠提供通常語義下的back()、push_back()和pop_back()函數(shù)。默認(rèn)情況下使用標(biāo)準(zhǔn)容器std::deque。滿足該要求的標(biāo)準(zhǔn)容器還有std::vector和std::list。
成員函數(shù)
元素訪問
訪問棧頂元素使用top()函數(shù),該函數(shù)的定義如下:
reference top();
const_reference top() const;
該函返回棧中棧頂元素的引用。實(shí)際上調(diào)用的就是底層容器的back()。
棧的容量
- size :返回底層容器中的元素?cái)?shù) 。實(shí)際上調(diào)用的就是底層容器的size()。
- empty :檢查底層容器是否為空,如果為空返回true,否則false。實(shí)際上調(diào)用的就是底層容器的empty()。
棧的修改
- push :向棧中推入元素。其函數(shù)聲明如下:
void push( const value_type& value );
void push( value_type&& value ); //C++11 起
- emplace :推入新元素到棧中,與push不同的是該函數(shù)是原位構(gòu)造元素(直接在容器內(nèi)構(gòu)造對(duì)象,不用拷貝一個(gè)復(fù)制品再使用),既不進(jìn)行也不進(jìn)行復(fù)制操作。其函數(shù)聲明如下:
template< class... Args >
void emplace( Args&&... args ); //C++11 起 C++17 前
template< class... Args >
decltype(auto) emplace( Args&&... args ); //C++17 起
其中args為轉(zhuǎn)發(fā)給元素構(gòu)造函數(shù)的參數(shù)。也正是由于emplace的原位構(gòu)造元素,省去了拷貝構(gòu)造的過程,使得emplace的效率高于push。
- pop :從棧中移除站定元素。實(shí)際上調(diào)用的就是底層元素的pop_back()。
- swap :交換棧與另一個(gè)棧中的內(nèi)容,其函數(shù)聲明如下:
void swap( stack& other ) noexcept(/* see below */); //C++11 起
用法示例
#include < iostream >
#include < stack >
using namespace std;
int main() {
stack< int > s;
// push()
s.push(1);
s.push(2);
s.push(3);
cout < < "按順push元素1、2、3后" < < endl;
cout < < "棧s中元素的數(shù)量, 即s.size() = " < < s.size() < < endl;
cout < < "此時(shí), 棧s是否為空,即s.empty() = " < < s.empty() < < endl;
if (!s.empty())
cout < < "此時(shí), 棧s非空, 棧頂元素,即s.top() = " < < s.top() < < endl;
else
cout < < "此時(shí), 棧s為空, 不能使用top訪問棧頂元素 = " < < s.top() < < endl;
s.pop(); // 彈出棧頂元素
cout < < "n彈出棧頂元素3, 即pop()后" < < endl;
cout < < "棧s中元素的數(shù)量, 即s.size() = " < < s.size() < < endl;
cout < < "此時(shí), 棧s是否為空,即s.empty() = " < < s.empty() < < endl;
if (!s.empty())
cout < < "此時(shí), 棧s非空, 棧頂元素,即s.top() = " < < s.top() < < endl;
else
cout < < "此時(shí), 棧s為空, 不能使用top訪問棧頂元素 = " < < s.top() < < endl;
s.pop();
cout < < "n彈出棧頂元素2, 即pop()后" < < endl;
cout < < "棧s中元素的數(shù)量, 即s.size() = " < < s.size() < < endl;
cout < < "此時(shí), 棧s是否為空,即s.empty() = " < < s.empty() < < endl;
if (!s.empty())
cout < < "此時(shí), 棧s非空, 棧頂元素,即s.top() = " < < s.top() < < endl;
else
cout < < "此時(shí), 棧s為空, 不能使用top訪問棧頂元素 = " < < s.top() < < endl;
s.pop();
cout < < "n彈出棧頂元素1, 即pop()后" < < endl;
cout < < "棧s中元素的數(shù)量, 即s.size() = " < < s.size() < < endl;
cout < < "此時(shí), 棧s是否為空,即s.empty() = " < < s.empty() < < endl;
if (!s.empty())
cout < < "此時(shí), 棧s非空, 棧頂元素,即s.top() = " < < s.top() < < endl;
else
cout < < "此時(shí), 棧s為空, 不能使用top訪問棧頂元素" < < endl;
// swap()操作
s.emplace(1);
s.emplace(2);
s.emplace(3);
stack< int > s1;
cout < < "n-----------棧s和s1交換前----------" < < endl;
cout < < "ns的狀態(tài): " < < endl;
cout < < "棧s中元素的數(shù)量, 即s.size() = " < < s.size() < < endl;
cout < < "此時(shí), 棧s是否為空,即s.empty() = " < < s.empty() < < endl;
if (!s.empty())
cout < < "此時(shí), 棧s非空, 棧頂元素,即s.top() = " < < s.top() < < endl;
else
cout < < "此時(shí), 棧s為空, 不能使用top訪問棧頂元素" < < endl;
cout < < "ns1的狀態(tài): " < < endl;
cout < < "棧s1中元素的數(shù)量, 即s1.size() = " < < s1.size() < < endl;
cout < < "此時(shí), 棧s1是否為空,即s1.empty() = " < < s1.empty() < < endl;
if (!s1.empty())
cout < < "此時(shí), 棧s1非空, 棧頂元素,即s1.top() = " < < s1.top() < < endl;
else
cout < < "此時(shí), 棧s1為空, 不能使用top訪問棧頂元素" < < endl;
s1.swap(s); // s和s1進(jìn)行交換
cout < < "n-----------棧s和s1交換后----------" < < endl;
cout < < "ns的狀態(tài): " < < endl;
cout < < "棧s中元素的數(shù)量, 即s.size() = " < < s.size() < < endl;
cout < < "此時(shí), 棧s是否為空,即s.empty() = " < < s.empty() < < endl;
if (!s.empty())
cout < < "此時(shí), 棧s非空, 棧頂元素,即s.top() = " < < s.top() < < endl;
else
cout < < "此時(shí), 棧s為空, 不能使用top訪問棧頂元素" < < endl;
cout < < "ns1的狀態(tài): " < < endl;
cout < < "棧s1中元素的數(shù)量, 即s1.size() = " < < s1.size() < < endl;
cout < < "此時(shí), 棧s1是否為空,即s1.empty() = " < < s1.empty() < < endl;
if (!s1.empty())
cout < < "此時(shí), 棧s1非空, 棧頂元素,即s1.top() = " < < s1.top() < < endl;
else
cout < < "此時(shí), 棧s1為空, 不能使用top訪問棧頂元素" < < endl;
return 0;
}
輸出結(jié)果:
按順push元素1、2、3后
棧s中元素的數(shù)量, 即s.size() = 3
此時(shí), 棧s是否為空,即s.empty() = 0
此時(shí), 棧s非空, 棧頂元素,即s.top() = 3
彈出棧頂元素3, 即pop()后
棧s中元素的數(shù)量, 即s.size() = 2
此時(shí), 棧s是否為空,即s.empty() = 0
此時(shí), 棧s非空, 棧頂元素,即s.top() = 2
彈出棧頂元素2, 即pop()后
棧s中元素的數(shù)量, 即s.size() = 1
此時(shí), 棧s是否為空,即s.empty() = 0
此時(shí), 棧s非空, 棧頂元素,即s.top() = 1
彈出棧頂元素1, 即pop()后
棧s中元素的數(shù)量, 即s.size() = 0
此時(shí), 棧s是否為空,即s.empty() = 1
此時(shí), 棧s為空, 不能使用top訪問棧頂元素
-----------棧s和s1交換前----------
s的狀態(tài):
棧s中元素的數(shù)量, 即s.size() = 3
此時(shí), 棧s是否為空,即s.empty() = 0
此時(shí), 棧s非空, 棧頂元素,即s.top() = 3
s1的狀態(tài):
棧s1中元素的數(shù)量, 即s1.size() = 0
此時(shí), 棧s1是否為空,即s1.empty() = 1
此時(shí), 棧s1為空, 不能使用top訪問棧頂元素
-----------棧s和s1交換后----------
s的狀態(tài):
棧s中元素的數(shù)量, 即s.size() = 0
此時(shí), 棧s是否為空,即s.empty() = 1
此時(shí), 棧s為空, 不能使用top訪問棧頂元素
s1的狀態(tài):
棧s1中元素的數(shù)量, 即s1.size() = 3
此時(shí), 棧s1是否為空,即s1.empty() = 0
此時(shí), 棧s1非空, 棧頂元素,即s1.top() = 3
-
適配器
+關(guān)注
關(guān)注
8文章
1901瀏覽量
67782 -
交換機(jī)
+關(guān)注
關(guān)注
20文章
2601瀏覽量
98896 -
C++語言
+關(guān)注
關(guān)注
0文章
147瀏覽量
6944
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
評(píng)論