C++棧

「棧 stack」是一種遵循先入后出的邏輯的線性數(shù)據(jù)結(jié)構(gòu)。

我們可以將棧類比為桌面上的一摞盤子，如果需要拿出底部的盤子，則需要先將上面的盤子依次取出。我們將盤子替換為各種類型的元素（如整數(shù)、字符、對象等），就得到了棧數(shù)據(jù)結(jié)構(gòu)。

如圖 5-1 所示，我們把堆疊元素的頂部稱為“棧頂”，底部稱為“棧底”。將把元素添加到棧頂?shù)牟僮鹘凶觥叭霔！?，刪除棧頂元素的操作叫做“出?！?。

圖 5-1   棧的先入后出規(guī)則

棧常用操作

棧的常用操作如表 5-1 所示，具體的方法名需要根據(jù)所使用的編程語言來確定。在此，我們以常見的 push()、pop()、peek() 命名為例。

表 5-1   棧的操作效率

通常情況下，我們可以直接使用編程語言內(nèi)置的棧類。然而，某些語言可能沒有專門提供棧類，這時我們可以將該語言的“數(shù)組”或“鏈表”視作棧來使用，并在程序邏輯上忽略與棧無關(guān)的操作。

stack.cpp

/* 初始化棧 */
stack<int> stack;

/* 元素入棧 */
stack.push(1);
stack.push(3);
stack.push(2);
stack.push(5);
stack.push(4);

/* 訪問棧頂元素 */
int top = stack.top();

/* 元素出棧 */
stack.pop(); // 無返回值

/* 獲取棧的長度 */
int size = stack.size();

/* 判斷是否為空 */
bool empty = stack.empty();

棧的實現(xiàn)

為了深入了解棧的運行機制，我們來嘗試自己實現(xiàn)一個棧類。

棧遵循先入后出的原則，因此我們只能在棧頂添加或刪除元素。然而，數(shù)組和鏈表都可以在任意位置添加和刪除元素，因此?？梢员灰暈橐环N受限制的數(shù)組或鏈表。換句話說，我們可以“屏蔽”數(shù)組或鏈表的部分無關(guān)操作，使其對外表現(xiàn)的邏輯符合棧的特性。

1.   基于鏈表的實現(xiàn)

使用鏈表來實現(xiàn)棧時，我們可以將鏈表的頭節(jié)點視為棧頂，尾節(jié)點視為棧底。

如圖 5-2 所示，對于入棧操作，我們只需將元素插入鏈表頭部，這種節(jié)點插入方法被稱為“頭插法”。而對于出棧操作，只需將頭節(jié)點從鏈表中刪除即可。

圖 5-2   基于鏈表實現(xiàn)棧的入棧出棧操作

以下是基于鏈表實現(xiàn)棧的示例代碼。

linkedlist_stack.cpp

/* 基于鏈表實現(xiàn)的棧 */
class LinkedListStack {
  private:
    ListNode *stackTop; // 將頭節(jié)點作為棧頂
    int stkSize;        // 棧的長度

  public:
    LinkedListStack() {
        stackTop = nullptr;
        stkSize = 0;
    }

    ~LinkedListStack() {
        // 遍歷鏈表刪除節(jié)點，釋放內(nèi)存
        freeMemoryLinkedList(stackTop);
    }

    /* 獲取棧的長度 */
    int size() {
        return stkSize;
    }

    /* 判斷棧是否為空 */
    bool isEmpty() {
        return size() == 0;
    }

    /* 入棧 */
    void push(int num) {
        ListNode *node = new ListNode(num);
        node->next = stackTop;
        stackTop = node;
        stkSize++;
    }

    /* 出棧 */
    void pop() {
        int num = top();
        ListNode *tmp = stackTop;
        stackTop = stackTop->next;
        // 釋放內(nèi)存
        delete tmp;
        stkSize--;
    }

    /* 訪問棧頂元素 */
    int top() {
        if (isEmpty())
            throw out_of_range("棧為空");
        return stackTop->val;
    }

    /* 將 List 轉(zhuǎn)化為 Array 并返回 */
    vector<int> toVector() {
        ListNode *node = stackTop;
        vector<int> res(size());
        for (int i = res.size() - 1; i >= 0; i--) {
            res[i] = node->val;
            node = node->next;
        }
        return res;
    }
};

2.   基于數(shù)組的實現(xiàn)

使用數(shù)組實現(xiàn)棧時，我們可以將數(shù)組的尾部作為棧頂。如圖 5-3 所示，入棧與出棧操作分別對應(yīng)在數(shù)組尾部添加元素與刪除元素，時間復(fù)雜度都為 O(1) 。

圖 5-3   基于數(shù)組實現(xiàn)棧的入棧出棧操作

由于入棧的元素可能會源源不斷地增加，因此我們可以使用動態(tài)數(shù)組，這樣就無須自行處理數(shù)組擴容問題。以下為示例代碼。

array_stack.cpp

/* 基于數(shù)組實現(xiàn)的棧 */
class ArrayStack {
  private:
    vector<int> stack;

  public:
    /* 獲取棧的長度 */
    int size() {
        return stack.size();
    }

    /* 判斷棧是否為空 */
    bool isEmpty() {
        return stack.size() == 0;
    }

    /* 入棧 */
    void push(int num) {
        stack.push_back(num);
    }

    /* 出棧 */
    void pop() {
        int oldTop = top();
        stack.pop_back();
    }

    /* 訪問棧頂元素 */
    int top() {
        if (isEmpty())
            throw out_of_range("棧為空");
        return stack.back();
    }

    /* 返回 Vector */
    vector<int> toVector() {
        return stack;
    }
};

兩種實現(xiàn)對比

支持操作

兩種實現(xiàn)都支持棧定義中的各項操作。數(shù)組實現(xiàn)額外支持隨機訪問，但這已超出了棧的定義范疇，因此一般不會用到。

時間效率

在基于數(shù)組的實現(xiàn)中，入棧和出棧操作都是在預(yù)先分配好的連續(xù)內(nèi)存中進行，具有很好的緩存本地性，因此效率較高。然而，如果入棧時超出數(shù)組容量，會觸發(fā)擴容機制，導(dǎo)致該次入棧操作的時間復(fù)雜度變?yōu)?nbsp;O(n) 。

在鏈表實現(xiàn)中，鏈表的擴容非常靈活，不存在上述數(shù)組擴容時效率降低的問題。但是，入棧操作需要初始化節(jié)點對象并修改指針，因此效率相對較低。不過，如果入棧元素本身就是節(jié)點對象，那么可以省去初始化步驟，從而提高效率。

綜上所述，當(dāng)入棧與出棧操作的元素是基本數(shù)據(jù)類型時，例如 int 或 double ，我們可以得出以下結(jié)論。

• 基于數(shù)組實現(xiàn)的棧在觸發(fā)擴容時效率會降低，但由于擴容是低頻操作，因此平均效率更高。
• 基于鏈表實現(xiàn)的棧可以提供更加穩(wěn)定的效率表現(xiàn)。

空間效率

在初始化列表時，系統(tǒng)會為列表分配“初始容量”，該容量可能超過實際需求。并且，擴容機制通常是按照特定倍率（例如 2 倍）進行擴容，擴容后的容量也可能超出實際需求。因此，基于數(shù)組實現(xiàn)的?？赡茉斐梢欢ǖ目臻g浪費。

然而，由于鏈表節(jié)點需要額外存儲指針，因此鏈表節(jié)點占用的空間相對較大。

綜上，我們不能簡單地確定哪種實現(xiàn)更加節(jié)省內(nèi)存，需要針對具體情況進行分析。

棧典型應(yīng)用

• 瀏覽器中的后退與前進、軟件中的撤銷與反撤銷。每當(dāng)我們打開新的網(wǎng)頁，瀏覽器就會將上一個網(wǎng)頁執(zhí)行入棧，這樣我們就可以通過后退操作回到上一頁面。后退操作實際上是在執(zhí)行出棧。如果要同時支持后退和前進，那么需要兩個棧來配合實現(xiàn)。
• 程序內(nèi)存管理。每次調(diào)用函數(shù)時，系統(tǒng)都會在棧頂添加一個棧幀，用于記錄函數(shù)的上下文信息。在遞歸函數(shù)中，向下遞推階段會不斷執(zhí)行入棧操作，而向上回溯階段則會執(zhí)行出棧操作。