鏈棧及（C++）實現

鏈棧的建立是基於連結串列而不是陣列。基於連結串列的棧相對於基於陣列的棧提供了兩個優點：

• 不需要指定棧的起始大小。鏈棧只需要從一個空的連結串列開始，然後每次壓入一個值時即擴充套件一個結點；
• 只要系統具有足夠的可用記憶體，鏈棧將永遠不會滿。

本節將可以看到一個鏈棧類 DynlntStack，該類的宣告如下所示：

//DynIntStack.h 的內容
class DynlntStack
{
    struct StackNode
    {
        int value;
        StackNode *next;
        // Constructor
        StackNode(int value1, StackNode *next1 = nullptr)
        {
            value = value1; next = next1;
        }
    };
    StackNode *top;
  public:
    DynlntStack() { top = nullptr; }
    ~DynlntStack();
    void push(int);
    void pop(int &);
    bool isEmpty() const;
    // Stack Exception
    class Underflow {};
};

StackNode 類是連結串列中每個結點的資料型別。因為在連結串列的開始處新增和刪除專案都很容易，所以將連結串列的開頭作為棧頂，並使用 top 指標指向連結串列中的第一個結點。這個指標被棧建構函式初始化為 nullptr，表示棧被建立為空。鏈棧沒有靜態分配的陣列要填充，所以不會有溢位的異常。但是，該類會定義一個 underflow 異常，當 pop 函數被呼叫而棧為空時就會丟擲該異常。

DynIntStack 棧類的成員函數如下所示：

//DynIntStack.cpp 的內容
#include <iostream>
#include "DynIntStack.h"
#include <cstdlib>
using namespace std;
void DynIntStack::push(int num)
    top = new StackNode(num, top);
}
void DynIntStack::pop(int &num)
{
    StackNode *temp;
    if (isEmpty()) { throw DynIntStack::Underflow(); }
    else {
        // Pop value off top of stack
        num = top->value;
        temp = top;
        top = top->next;
        delete temp;
    }
}
bool DynIntStack::isEmpty() const
{
    return top == nullptr;
}
DynIntStack::~DynIntStack()
{
    StackNode * garbage = top;
    while (garbage != nullptr)
    {
        top = top->next;
        garbage->next = nullptr;
        delete garbage;
        garbage = top;
    }
}

push 函數特別簡單。它只是建立一個新的結點，結點的值就是要 push 到棧上的數位，其後繼指標是當前棧頂的結點，然後使新建立的結點成為棧的新頂部：

top = new StackNode(num, top);

請注意，即使棧在 push 操作之前為空，以上語句也能正常工作，因為在這種情況下，棧頂部新結點的後繼指標將被正確設定為 nullptr。

接下來看一看 pop 函數。就像 push 函數必須在連結串列頭部插入結點一樣，pop 函數也必須刪除連結串列頭部的結點。首先，該函數呼叫 isEmpty 來確定棧中是否有任何結點。如果沒有，則拋出一個異常：

if (isEmpty())
{
    throw DynlntStack::Underflow();
}

如果 isEmpty 返回 false，則執行以下語句：

else //彈出棧頂的值
{
    num = top->value;
    temp = top;
    top = top->next;
    delete temp;
}

首先，棧頂結點的 value 成員的副本將儲存在 num 參照形參中，然後臨時指標 temp 被設定為指向要刪除的結點，即當前位於棧頂的結點。接下來將 top 指標設定為指向當前棧頂結點之後的結點。如果當前位於棧頂的結點之後沒有結點，則相同的程式碼會將 top 設定為 nullptr，然後就可以通過臨時指標安全地刪除棧頂結點。

下面的程式是一個驅動模組程式，它演示了 DynlntStack 類：

// This program demonstrates the dynamic stack class DynIntStack.
#include <iostream>
#include "DynIntStack.h"
using namespace std;

int main()
{
    DynIntStack stack;
    int popped_value;
    // Push values 5, 10, and 15 on the stack
    for (int value = 5; value <= 15; value = value + 5)
    {
        cout << "Push: " << value << "n";
        stack.push(value);
    }
    cout << "n";
    // Pop three values
    for (int k = 1; k <= 3; k++)
    {
        cout << "Pop: ";
        stack.pop(popped_value);
        cout << popped_value << endl;
    }
    // Stack is now empty, a pop will cause an exception
    try
    {
        cout << "nAttempting to pop again...";
        stack.pop(popped_value);
    }
    catch (DynIntStack::Underflow)
    {
        cout << "Underflow exception occured.n";
    }
    return 0;
}

程式輸出結果：

Push: 5
Push: 10
Push: 15

Pop: 15
Pop: 10
Pop: 5
Attempting to pop again...Underflow exception occurred.

該程式將建立一個棧並且將 3 個值壓入該棧，所有這 3 個值隨後又被彈出棧並列印。第 4 次（最後一次）呼叫 pop 執行出棧操作時，棧已經是空的了，所以拋出了一個異常。程式會捕獲異常和列印一條訊息。