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

資料結構基石：堆疊從原理到 C++ 模板實作與經典應用

編輯：關於C語言

什麼是堆疊？

堆疊是限制插入/刪除僅能在表尾（堆疊頂）進行的線性表，遵循 先進後出 原則。三大核心操作：

push（入堆疊）：尾端新增元素
pop（出堆疊）：移除尾端元素
top（取頂）：檢視尾端元素

兩種儲存結構實作

陣列實作（循序儲存）

單一整數 top 索引堆疊頂：top == -1 為空，top == 0 有一元素。入堆疊 ++top，出堆疊 --top，所有操作 O(1)，記憶體連續、快取友好。

鏈表實作（鏈式儲存）

以單鏈表表頭作為堆疊頂，push 為頭插，pop 為刪頭，top 取頭節點資料。優點：無容量上限；缺點：頻繁 new/delete 開銷大、記憶體碎片化。

C++ 模板完整實作（鏈表版）

template <class T>
class stackNode {
public:
    stackNode() : next(NULL) {}
    T data;
    stackNode* next;
};

template <class T>
class mystack {
private:
    unsigned int stacklength;
    stackNode<T> *node, *headnode;
public:
    mystack() : node(NULL), headnode(NULL), stacklength(0) {}
    unsigned int length() { return stacklength; }
    void push(T x) {
        node = new stackNode<T>();
        node->data = x;
        node->next = headnode;
        headnode = node;
        ++stacklength;
    }
    bool isEmpty() { return stacklength == 0; }
    void pop() {
        if(isEmpty()) return;
        node = headnode;
        headnode = headnode->next;
        delete node;
        --stacklength;
    }
    T top() { return isEmpty() ? T() : headnode->data; }
    void clear() {
        while(headnode) {
            node = headnode;
            headnode = headnode->next;
            delete node;
        }
        node = headnode = NULL;
        stacklength = 0;
    }
};

除 clear() 為 O(n)，其餘操作均為 O(1)。生產環境建議優先使用 std::stack 或陣列模擬，避免動態分配開銷。