C++棧

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

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

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

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

棧常用操作

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

表 5-1   棧的操作效率

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

stack.cpp

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

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

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

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

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

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

棧的實(shí)現(xiàn)

為了深入了解棧的運(yùn)行機(jī)制，我們來(lái)嘗試自己實(shí)現(xiàn)一個(gè)棧類。

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

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

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

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

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

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

linkedlist_stack.cpp

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

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

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

    /* 獲取棧的長(zhǎng)度 */
    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--;
    }

    /* 訪問(wèn)棧頂元素 */
    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ù)組的實(shí)現(xiàn)

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

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

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

array_stack.cpp

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

  public:
    /* 獲取棧的長(zhǎng)度 */
    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();
    }

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

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

兩種實(shí)現(xiàn)對(duì)比

支持操作

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

時(shí)間效率

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

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

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

• 基于數(shù)組實(shí)現(xiàn)的棧在觸發(fā)擴(kuò)容時(shí)效率會(huì)降低，但由于擴(kuò)容是低頻操作，因此平均效率更高。
• 基于鏈表實(shí)現(xiàn)的?？梢蕴峁└臃€(wěn)定的效率表現(xiàn)。

空間效率

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

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

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

棧典型應(yīng)用

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