棧(stack)

什么是棧？

棧是一種線(xiàn)性的數(shù)據(jù)結(jié)構(gòu)，其是一種運(yùn)算受限（限定僅在表尾進(jìn)行插入和刪除的線(xiàn)性表）的線(xiàn)性表。棧的結(jié)構(gòu)類(lèi)似下圖的容器：

如上圖所示，棧的結(jié)構(gòu)就像一個(gè)端封閉，另一端開(kāi)口的容器，往容器放入小球（對(duì)應(yīng)棧中的元素），先放入的小球就越靠近容器的底部，最早進(jìn)入的小球?qū)?yīng)的位置就是棧底（bottom），最后放入的小球?qū)?yīng)的位置就是棧頂（top），放入小球的動(dòng)作就叫做入棧（push）；取出小球的時(shí)候，只能按照放入順序相反的順序來(lái)取，即先取后放入的，再去先放入的，每次取小球的動(dòng)作就叫做出棧（pop）。由于棧的單端口進(jìn)出的限制，決定了棧中的元素只能先進(jìn)后出（FILO, First In Last Out）。棧的數(shù)據(jù)結(jié)構(gòu)可以使用數(shù)組來(lái)實(shí)現(xiàn)，也可以用鏈表來(lái)實(shí)現(xiàn)，具體如下圖所示：

棧的基本操作和應(yīng)用

入棧（push)

入棧就是把元素存放入棧中，由于棧的結(jié)構(gòu)只允許從一次存放元素，所以新元素的存入后所在的位置就是該棧新的棧頂，我們以棧的數(shù)組實(shí)現(xiàn)為例，入棧的過(guò)程如下圖所示：

出棧（pop)

出棧就是把元素從棧中彈出，同樣的由于棧結(jié)構(gòu)單端進(jìn)出的限制，出棧時(shí)候的元素就是棧頂對(duì)應(yīng)的元素，取出元素后，出棧元素前面的那個(gè)元素對(duì)應(yīng)的位置將變成新的棧頂。出棧的過(guò)程如下：

入棧和出棧的復(fù)雜度和應(yīng)用場(chǎng)景

由于棧的后進(jìn)先出的特性，使得入棧和出棧只會(huì)影響到棧中最后一個(gè)元素，不會(huì)涉及到其他元素的移動(dòng)，因此入棧和出棧的時(shí)間復(fù)雜都為。同樣的，棧的先入后出的特性，也使得棧不能擁有遍歷、隨機(jī)訪(fǎng)問(wèn)和隨機(jī)插入的功能。

由于棧的特殊結(jié)構(gòu)，棧常用于以下場(chǎng)景：

• 逆序輸出：由于棧先入后出的特性，使用棧結(jié)構(gòu)可以輕松實(shí)現(xiàn)逆序輸出的操作。

• 語(yǔ)法檢測(cè)：對(duì)于一些成對(duì)出現(xiàn)的符號(hào)，如"[]"、"()"等，凡是遇到符號(hào)的前半部分，即入棧（push）該符號(hào)，凡是遇到括號(hào)后半部分的，就與棧頂元素進(jìn)行匹配，如果匹配成功，則出棧（pop），否則就是匹配失敗，語(yǔ)法錯(cuò)誤。

• 數(shù)字進(jìn)制轉(zhuǎn)換：順序計(jì)算，繼續(xù)結(jié)果逆序輸出。

棧的應(yīng)用場(chǎng)景還有很多，這里就不一一舉例，實(shí)際上棧的應(yīng)用都是基于棧的先入后出的特性。

類(lèi)模板std::satck

stack類(lèi)是C++標(biāo)準(zhǔn)庫(kù)提供的一個(gè)容器適配器，它給使用者提供了棧的功能，實(shí)現(xiàn)的棧的先進(jìn)后出（FILO）的數(shù)據(jù)結(jié)構(gòu)，并提供了特定的函數(shù)集合，其定義如下所示：

該類(lèi)模板在頭文件<stack>中定義。

形參T和Container

• T：代表存儲(chǔ)元素的類(lèi)型

• Container：用于存儲(chǔ)元素的底層容器類(lèi)型。該類(lèi)型必須滿(mǎn)足序列容器的要求，同時(shí)該容器類(lèi)型能夠提供通常語(yǔ)義下的back()、push_back()和pop_back()函數(shù)。默認(rèn)情況下使用標(biāo)準(zhǔn)容器std::deque。滿(mǎn)足該要求的標(biāo)準(zhǔn)容器還有std::vector和std::list。

成員函數(shù)

元素訪(fǎng)問(wèn)

訪(fǎng)問(wèn)棧頂元素使用top()函數(shù)，該函數(shù)的定義如下：

該函返回棧中棧頂元素的引用。實(shí)際上調(diào)用的就是底層容器的back()。

棧的容量

• size：返回底層容器中的元素?cái)?shù) 。實(shí)際上調(diào)用的就是底層容器的size()。

• empty：檢查底層容器是否為空，如果為空返回true，否則false。實(shí)際上調(diào)用的就是底層容器的empty()。

棧的修改

• push：向棧中推入元素。其函數(shù)聲明如下：

  


• emplace：推入新元素到棧中，與push不同的是該函數(shù)是原位構(gòu)造元素（直接在容器內(nèi)構(gòu)造對(duì)象，不用拷貝一個(gè)復(fù)制品再使用），既不進(jìn)行也不進(jìn)行復(fù)制操作。其函數(shù)聲明如下：

• pop：從棧中移除站定元素。實(shí)際上調(diào)用的就是底層元素的pop_back()。

• swap：交換棧與另一個(gè)棧中的內(nèi)容，其函數(shù)聲明如下：

用法示例

輸出結(jié)果：