順序棧及其（C++）實現

現在來研究一個 IntStack 類，它儲存了一個靜態的整數棧並將執行剛才討論過的棧操作。該類具有的成員變數如表 1 所示。

表 1 棧類的成員變數

成員變數	描 述
stackArray	指向整數陣列的 unique_ptr 獨佔指標。當建構函式執行時，它使用 stackArray 動態分配陣列的儲存
capacity	一個儲存棧的大小的整數。這是棧最多可以儲存的元素的個數，而不是當前棧中元素的最大值
Top	用來標記棧頂的整數。它指定將被新增到棧的下一個專案的位置

該類的成員函數如表 2 所示：

表 2 棧類的成員函數

成員函數	描 述
建構函式	該類別建構函式將接受一個整數引數，該引數指定了棧的大小。這個大小的整數陣列被動態分配儲存並賦值給 stackArray。另外，變數 top 被初始化為 0，表示棧當前為空
push	push 函數接受一個整數引數，該引數將被壓入棧頂
pop	pop 函數使用一個整數參照形參。棧頂部的值被刪除並複製到參照形參中
isEmpty	如果棧為空則返回 true，否則返回 false。top 設定為 0 時則棧為空

注意，即使建構函式會動態地為棧陣列分配儲存，但是它仍然被視為一個順序棧，因為一旦分配完畢，該棧的大小就不能改變。

該類的程式碼顯示如下：

//IntStack.h 的內容
#include <memory>
using namespace std;
class IntStack
{
    unique_ptr<int[]>stackArray;
    int capacity;
    int top;
  public:
    // Constructor
    IntStack(int capacity);
    // Member functions
    void push(int value);
    void pop (int &value);
    bool isEmpty() const;
    // Stack Exceptions
    class Overflow {};
    class Underflow {};
};

除了表 2 中描述的棧成員之外，IntStack 類還定義了兩個名為 Overflow 和 Underflow 的內部類，用作棧異常。

如果在程式碼執行過程中，遇到了程式碼無法按既定任務執行的情況，則稱該程式碼段出現異常。在順序棧的情況下，如果棧中沒有更多的空間，則在呼叫 push 壓棧的過程中就會發生溢位異常。同樣，如果在呼叫 pop 出棧時棧內卻沒有任何內容可以返回，則會發生下溢異常。

程式碼在檢測到異常發生之後，會立即通知程式的其餘部分，方法是建立描述異常的值並使用 throw 語句將該值傳遞給程式的其餘部分。

例如，push 函數可通過執行以下語句來通知發生溢位異常：

throw InstStack::Overflow();

而 pop 函數則可以執行以下語句：

throw IntStack::Underflow();

該語句通知程式發生了下溢異常。預設情況下，當程式的任何部分丟擲異常時，程式將終止並顯示錯誤訊息。這個預設行為可以通過一個被稱為捕獲異常的進程來改變。

IntStack 建構函式可分配一個指定容量的陣列，並將成員變數 top 設定為 0。所有的棧函數都使用 top，使它始終指向棧陣列中的下一個可用槽。當 top 等於 capacity 時，沒有更多的槽用於儲存值，下一次 push 的呼叫就會拋出異常。

同樣，當 top 為零時，棧就是空的，對 pop 的呼叫會丟擲一個異常。因為在程式中沒有任何規定來捕捉這兩個異常，所以它們中的任何一個都會以錯誤資訊終止程式。注意，在向棧中新增一個值之後，push 會遞增 top 的值；而在返回儲存在 stackArray[top] 中的值之前，pop 會遞減 top 的值。

//IntStack.cpp 的內容
#include "intstack.h"
IntStack::IntStack(int capacity)
{
    stackArray = make_unique<int[]>(capacity);
    this->capacity = capacity;
    top = 0;
}
void IntStack::push(int value)
{
    if (top == capacity)
        throw IntStack::Overflow();
    stackArray[top] = value;
    top++;
}
bool IntStack::isEmpty() const
{
    return top == 0;
}
void IntStack::pop(int &value)
{
    if (isEmpty()) throw IntStack::Underflow();
    top--;
    value = stackArray[top];
}

下面的程式演示了棧類及其成員函數的使用。請注意，在出棧的時候，其順序剛好和值入棧的順序相反。

// This program illustrates the IntStack class.
#include "intstack.h"
#include <iostream>
using namespace std;
int main()
{
    IntStack stack(5);
    int values[] = { 5, 10, 15, 20, 25 };
    int value;
    cout << "Pushing. . . n";
    for (int k = 0; k < 5; k++)
    {
        cout << values[k] << " ";
        stack.push(values[k]);
    }
    cout << "nPopping. . .n";
    while (!stack.isEmpty())
    {
        stack.pop(value);
        cout << value << " ";
    }
    cout << endl;
    return 0;
}

程式輸出結果：

Pushing. . .
5 10 15 20 25
Popping. . .
25 20 15 10 5

在此程式中，使用引數 5 呼叫建構函式，這將如圖 1 所示設定成員變數。由於 top 被設定為 0，所以該棧是空的。

---