您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

C++ 資料結構實戰：鏈式堆疊與佇列的設計與實作

編輯：C++ 入門

前言：為何選擇鏈式結構實作堆疊與佇列？

順序結構（陣列）實作的堆疊與佇列雖然隨機存取快，但存在空間預先固定、擴容麻煩、隨機存取優勢因限定存取點而失效等缺陷。鏈式結構以動態節點配置、彈性擴展、無容量上限成為工程首選。本文展示以單向鏈表為基底的堆疊與佇列完整實作。

一、堆疊（Stack）類別設計

採用公開繼承 List<Type>，複用鏈表操作：

template <class Type>
class Stack : public List<Type> {
public:
    void Push(Type value) { Insert(value); }  // 列表頭插入 = 堆疊推入
    
    Type Pop() {
        Type val = *GetNext();  // 取得第一個節點資料
        RemoveAfter();          // 刪除該節點
        return val;
    }
    
    Type GetTop() { return *GetNext(); }  // 僅檢視不移除
    
    // 繼承基底類別操作
    using List<Type>::MakeEmpty;
    using List<Type>::IsEmpty;
};

設計精華：堆疊 LIFO 特性完美對應鏈表頭部插入/刪除，時間複雜度 O(1)。

二、佇列（Queue）類別設計

template <class Type>
class Queue : public List<Type> {
public:
    void EnQueue(const Type& value) { LastInsert(value); }  // 尾部插入
    
    Type DeQueue() {
        Type val = *GetNext();  // 取頭部資料
        RemoveAfter();          // 移除頭部
        IsEmpty();              // 維護狀態（原碼邏輯）
        return val;
    }
    
    Type GetFront() { return *GetNext(); }  // 檢視隊首
    
    using List<Type>::MakeEmpty;
    using List<Type>::IsEmpty;
};

關鍵差異：佇列 FIFO 對應鏈表尾部插入、頭部刪除，需維護尾節點指標以達 O(1) 入隊。

三、測試驗證程式

// 堆疊測試
void StackTest_int() {
    Stack<int> s;
    for (int i = 1; i <= 20; ++i) s.Push(i);  // 1~20 入堆疊
    while (!s.IsEmpty()) cout << s.Pop() << ' ';  // 輸出: 20 19 ... 1
}

// 佇列測試
void QueueTest_int() {
    Queue<int> q;
    for (int i = 1; i <= 20; ++i) q.EnQueue(i);  // 1~20 入佇列
    while (!q.IsEmpty()) cout << q.DeQueue() << ' ';  // 輸出: 1 2 ... 20
}

測試結果完美驗證 LIFO 與 FIFO 語意。