棧與C++中的std::stack詳解

棧(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