C語言中文網 目錄
首頁 > 編程筆記 > C++筆記 閱讀:285

順序棧及其(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,所以該棧是空的。

使用構造函數和參數 5 創建的棧
圖 1 使用構造函數和參數 5 創建的棧

圖 2 顯示了第一次調用 push 函數(以 5 為參數)后的成員變量的狀態。top 的值現在是 1。

調用 push 函數(以 5 為參數)壓棧之后棧的狀態
圖 2 調用 push 函數(以 5 為參數)壓棧之后棧的狀態

圖 3 顯示了 5 次調用 push 函數后的成員變量的狀態。現在最高有 5 個值,該棧已滿。

調用 push 函數執行 5 次壓棧操作之后的狀態
圖 3 調用 push 函數執行 5 次壓棧操作之后的狀態

注意看 pop 函數,它使用了一個引用形參 value。出棧的值將被復制到 value 中,以便稍后在程序中使用。圖 4 描述了在調用 pop 函數使第一個值出棧之后,類成員和 value 參數的狀態。

調用 pop 函數使棧頂的值出棧并復制到形參中
圖 5 調用 pop 函數使棧頂的值出棧并復制到形參中

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo