棧(stack)

什么是棧？

棧是一種線性的數據結構，其是一種運算受限（限定僅在表尾進行插入和刪除的線性表）的線性表。棧的結構類似下圖的容器：

如上圖所示，棧的結構就像一個端封閉，另一端開口的容器，往容器放入小球（對應棧中的元素），先放入的小球就越靠近容器的底部，最早進入的小球對應的位置就是 棧底 （bottom），最后放入的小球對應的位置就是 棧頂 （top），放入小球的動作就叫做 入棧 （push）；取出小球的時候，只能按照放入順序相反的順序來取，即先取后放入的，再去先放入的，每次取小球的動作就叫做 出棧 （pop）。由于棧的單端口進出的限制，決定了棧中的元素只能先進后出（FILO, First In Last Out）。棧的數據結構可以使用數組來實現，也可以用鏈表來實現，具體如下圖所示：

棧的基本操作和應用

入棧（push)

入棧就是把元素存放入棧中，由于棧的結構只允許從一次存放元素，所以新元素的存入后所在的位置就是該棧新的棧頂，我們以棧的數組實現為例，入棧的過程如下圖所示：

出棧（pop)

出棧就是把元素從棧中彈出，同樣的由于棧結構單端進出的限制，出棧時候的元素就是棧頂對應的元素，取出元素后，出棧元素前面的那個元素對應的位置將變成新的棧頂。出棧的過程如下：

入棧和出棧的復雜度和應用場景

由于棧的后進先出的特性，使得入棧和出棧只會影響到棧中最后一個元素，不會涉及到其他元素的移動，因此入棧和出棧的時間復雜都為。同樣的，棧的先入后出的特性，也使得棧不能擁有遍歷、隨機訪問和隨機插入的功能。

由于棧的特殊結構，棧常用于以下場景：

• 逆序輸出：由于棧先入后出的特性，使用棧結構可以輕松實現逆序輸出的操作。
• 語法檢測：對于一些成對出現的符號，如"[]"、"()"等，凡是遇到符號的前半部分，即入棧（push）該符號，凡是遇到括號后半部分的，就與棧頂元素進行匹配，如果匹配成功，則出棧（pop），否則就是匹配失敗，語法錯誤。
• 數字進制轉換：順序計算，繼續(xù)結果逆序輸出。

棧的應用場景還有很多，這里就不一一舉例，實際上棧的應用都是基于棧的先入后出的特性。

類模板std::satck

stack類是C++標準庫提供的一個容器適配器，它給使用者提供了棧的功能，實現的棧的先進后出（FILO）的數據結構，并提供了特定的函數集合，其定義如下所示：

template<
    class T,
    class Container = std::deque< T >
> class stack;

該類模板在頭文件中定義。

形參T和Container

• T ：代表存儲元素的類型
• Container ：用于存儲元素的底層容器類型。該類型必須滿足序列容器的要求，同時該容器類型能夠提供通常語義下的back()、push_back()和pop_back()函數。默認情況下使用標準容器std::deque。滿足該要求的標準容器還有std::vector和std::list。

成員函數

元素訪問

訪問棧頂元素使用top()函數，該函數的定義如下：

reference top();
const_reference top() const;

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

棧的容量

• size ：返回底層容器中的元素數 。實際上調用的就是底層容器的size()。
• empty ：檢查底層容器是否為空，如果為空返回true，否則false。實際上調用的就是底層容器的empty()。

棧的修改

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

void push( const value_type& value );
void push( value_type&& value ); //C++11 起

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

template< class... Args >
void emplace( Args&&... args ); //C++11 起 C++17 前

template< class... Args >
decltype(auto) emplace( Args&&... args ); //C++17 起

其中args為轉發(fā)給元素構造函數的參數。也正是由于emplace的原位構造元素，省去了拷貝構造的過程，使得emplace的效率高于push。

• pop ：從棧中移除站定元素。實際上調用的就是底層元素的pop_back()。
• swap ：交換棧與另一個棧中的內容，其函數聲明如下：

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中元素的數量, 即s.size() = " < < s.size() < < endl;
    cout < < "此時, 棧s是否為空,即s.empty() = " < < s.empty() < < endl;
    if (!s.empty())
        cout < < "此時, 棧s非空, 棧頂元素,即s.top() = " < < s.top() < < endl;
    else
        cout < < "此時, 棧s為空, 不能使用top訪問棧頂元素 = " < < s.top() < < endl;

    s.pop();  // 彈出棧頂元素
    cout < < "n彈出棧頂元素3, 即pop()后" < < endl;
    cout < < "棧s中元素的數量, 即s.size() = " < < s.size() < < endl;
    cout < < "此時, 棧s是否為空,即s.empty() = " < < s.empty() < < endl;
    if (!s.empty())
        cout < < "此時, 棧s非空, 棧頂元素,即s.top() = " < < s.top() < < endl;
    else
        cout < < "此時, 棧s為空, 不能使用top訪問棧頂元素 = " < < s.top() < < endl;

    s.pop();
    cout < < "n彈出棧頂元素2, 即pop()后" < < endl;
    cout < < "棧s中元素的數量, 即s.size() = " < < s.size() < < endl;
    cout < < "此時, 棧s是否為空,即s.empty() = " < < s.empty() < < endl;
    if (!s.empty())
        cout < < "此時, 棧s非空, 棧頂元素,即s.top() = " < < s.top() < < endl;
    else
        cout < < "此時, 棧s為空, 不能使用top訪問棧頂元素 = " < < s.top() < < endl;

    s.pop();
    cout < < "n彈出棧頂元素1, 即pop()后" < < endl;
    cout < < "棧s中元素的數量, 即s.size() = " < < s.size() < < endl;
    cout < < "此時, 棧s是否為空,即s.empty() = " < < s.empty() < < endl;
    if (!s.empty())
        cout < < "此時, 棧s非空, 棧頂元素,即s.top() = " < < s.top() < < endl;
    else
        cout < < "此時, 棧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中元素的數量, 即s.size() = " < < s.size() < < endl;
    cout < < "此時, 棧s是否為空,即s.empty() = " < < s.empty() < < endl;
    if (!s.empty())
        cout < < "此時, 棧s非空, 棧頂元素,即s.top() = " < < s.top() < < endl;
    else
        cout < < "此時, 棧s為空, 不能使用top訪問棧頂元素" < < endl;

    cout < < "ns1的狀態(tài): " < < endl;
    cout < < "棧s1中元素的數量, 即s1.size() = " < < s1.size() < < endl;
    cout < < "此時, 棧s1是否為空,即s1.empty() = " < < s1.empty() < < endl;
    if (!s1.empty())
        cout < < "此時, 棧s1非空, 棧頂元素,即s1.top() = " < < s1.top() < < endl;
    else
        cout < < "此時, 棧s1為空, 不能使用top訪問棧頂元素" < < endl;

    s1.swap(s);  // s和s1進行交換

    cout < < "n-----------棧s和s1交換后----------" < < endl;
    cout < < "ns的狀態(tài): " < < endl;
    cout < < "棧s中元素的數量, 即s.size() = " < < s.size() < < endl;
    cout < < "此時, 棧s是否為空,即s.empty() = " < < s.empty() < < endl;
    if (!s.empty())
        cout < < "此時, 棧s非空, 棧頂元素,即s.top() = " < < s.top() < < endl;
    else
        cout < < "此時, 棧s為空, 不能使用top訪問棧頂元素" < < endl;

    cout < < "ns1的狀態(tài): " < < endl;
    cout < < "棧s1中元素的數量, 即s1.size() = " < < s1.size() < < endl;
    cout < < "此時, 棧s1是否為空,即s1.empty() = " < < s1.empty() < < endl;
    if (!s1.empty())
        cout < < "此時, 棧s1非空, 棧頂元素,即s1.top() = " < < s1.top() < < endl;
    else
        cout < < "此時, 棧s1為空, 不能使用top訪問棧頂元素" < < endl;

    return 0;
}

輸出結果：

按順push元素1、2、3后
棧s中元素的數量, 即s.size() = 3
此時, 棧s是否為空,即s.empty() = 0
此時, 棧s非空, 棧頂元素,即s.top() = 3

彈出棧頂元素3, 即pop()后
棧s中元素的數量, 即s.size() = 2
此時, 棧s是否為空,即s.empty() = 0
此時, 棧s非空, 棧頂元素,即s.top() = 2

彈出棧頂元素2, 即pop()后
棧s中元素的數量, 即s.size() = 1
此時, 棧s是否為空,即s.empty() = 0
此時, 棧s非空, 棧頂元素,即s.top() = 1

彈出棧頂元素1, 即pop()后
棧s中元素的數量, 即s.size() = 0
此時, 棧s是否為空,即s.empty() = 1
此時, 棧s為空, 不能使用top訪問棧頂元素

-----------棧s和s1交換前----------

s的狀態(tài): 
棧s中元素的數量, 即s.size() = 3
此時, 棧s是否為空,即s.empty() = 0
此時, 棧s非空, 棧頂元素,即s.top() = 3

s1的狀態(tài): 
棧s1中元素的數量, 即s1.size() = 0
此時, 棧s1是否為空,即s1.empty() = 1
此時, 棧s1為空, 不能使用top訪問棧頂元素

-----------棧s和s1交換后----------

s的狀態(tài): 
棧s中元素的數量, 即s.size() = 0
此時, 棧s是否為空,即s.empty() = 1
此時, 棧s為空, 不能使用top訪問棧頂元素

s1的狀態(tài): 
棧s1中元素的數量, 即s1.size() = 3
此時, 棧s1是否為空,即s1.empty() = 0
此時, 棧s1非空, 棧頂元素,即s1.top() = 3