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

鏈棧及(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 執行出棧操作時,棧已經是空的了,所以拋出了一個異常。程序會捕獲異常和打印一條消息。

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

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

底部Logo