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

C++ 數據結構實戰：棧與隊列的模板化實現及應用

編輯：關於C++

棧與隊列屬於操作受限的線性表。順序存儲需預分配空間且隨機存取優勢盡失，鏈式結構應為首選。本文基於單鏈表模板，以繼承方式極簡實現兩者，並展示表達式求值與銀行排隊模擬兩大經典應用。

棧與隊列的模板定義

利用單鏈表 List<Type> 作為基類，棧僅允許表頭插刪，隊列則表頭刪除、表尾插入：

// Stack.h
template <class Type> class Stack : List<Type> {
public:
    void Push(Type value) { Insert(value); }
    Type Pop() { Type p = *GetNext(); RemoveAfter(); return p; }
    Type GetTop() { return *GetNext(); }
    using List<Type>::MakeEmpty;
    using List<Type>::IsEmpty;
};

// Queue.h
template <class Type> class Queue : List<Type> {
public:
    void EnQueue(const Type &value) { LastInsert(value); }
    Type DeQueue() { Type p = *GetNext(); RemoveAfter(); IsEmpty(); return p; }
    Type GetFront() { return *GetNext(); }
    using List<Type>::MakeEmpty;
    using List<Type>::IsEmpty;
}

測試代碼驗證了 1~20 入棧/入隊後出棧/出隊順序，清晰展示 LIFO 與 FIFO 特性。

棧的應用：表達式求值（中綴轉後綴 + 後綴計算）

定義 ExpNode 節點，以 type 區分操作數/操作符，表達式類繼承自鏈表，頭節點存儲類型標識（中綴/後綴）。核心功能：

輸入：按「操作數、操作符」交替讀取，以 '=' 結束，括號需輸入 "0(" 和 ")0" 以保持結構統一。
中綴轉後綴：利用操作符優先級表（isp 棧內優先級，icp 棧外優先級），經運算符棧轉換。
後綴求值：操作數入棧，遇操作符彈出兩操作數運算後結果入棧，最終棧頂即結果。

關鍵代碼片段：

Expression & Postfix() {
    if (Get()->type == POSTFIX) return *this;
    Stack<char> s; s.Push('=');
    Expression temp;
    for (ExpNode<Type> *p = Next(); p; p = Next()) {
        switch (p->type) {
            case OPND: temp.LastInsert(*p); break;
            case OPTR:
                while (isp(s.GetTop()) > icp(p->optr)) {
                    temp.LastInsert(ExpNode<Type>(s.Pop()));
                }
                if (isp(s.GetTop()) == icp(p->optr)) { s.Pop(); break; }
                s.Push(p->optr); break;
        }
    }
    *this = temp; pGetFirst()->data.type = POSTFIX; return *this;
}
Type Calculate() {
    Expression temp = *this;
    if (pGetFirst()->data.type != POSTFIX) temp.Postfix();
    Stack<Type> s; Type left, right;
    for (ExpNode<Type> *p = temp.Next(); p; p = temp.Next()) {
        if (p->type == OPND) s.Push(p->opnd);
        else { right = s.Pop(); left = s.Pop(); /* 根據運算符計算 */ s.Push(result); }
    }
    return s.Pop();
}

優先級表設計遵循經典規則：'=' 最低，'(' 棧外最高/棧內次低，')' 棧外次低不入棧，'^' 右結合，乘除模同級，加減同級。

隊列的應用：銀行多窗口掛號模擬

改良自教材「銀行營業模擬」，採用單隊列多窗口模式：顧客到達取號入隊，空閒窗口按號碼順序叫號，保證先來先服務，更符合現代銀行實況（如北京西直門工行）。模擬參數包括窗口數、營業時間、顧客到達間隔、服務時長範圍。核心邏輯：

時鐘 curTime 自然流逝；顧客到達事件觸發入隊；窗口服務完成觸發出隊並累計統計。
結果輸出：各窗口服務人數、總時長、平均時長；總服務人數、未服務人數、顧客總/平均等待時間。

void Run() {
    Initialize(); NextArrived();
    for (curTime = 0; curTime <= simuTime; curTime++) {
        if (curTime >= nextTime) { CustomerArrived(); NextArrived(); }
        for (int i = 1; i <= tellerNum; i++) {
            if (tellers[i].finishServiceTime < curTime) tellers[i].finishServiceTime = curTime;
            if (tellers[i].finishServiceTime == curTime && !customer.IsEmpty()) {
                int t = NextService();
                CustomerDeparture();
                tellers[i].totalCustomerCount++;
                tellers[i].totalServiceTime += t;
                tellers[i].finishServiceTime += t;
            }
        }
    }
    PrintResult();
}

雖算法效率非最高（可用事件驅動優化），但贴近實際業務邏輯，教學價值高。實測發現：不繁忙銀行 4~5 個窗口最合適，符合現狀。