[資料結構] 使用 C 語言:以連結串列 (Linked List) 為基礎的堆疊 (Stack)

【分享本文】
Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email
【贊助商連結】

    堆疊的抽象資料結構

    堆疊 (stack) 是一種受限制的線性 (linear) 資料結構,僅能由單一出入口存取資料。堆疊的存取方式為 FILO (First-In, Last-Out),讀者可以將堆疊想像成一個長桶子,先放入的東西位於桶子的下方,後放入的東西位於桶子的上方。

    堆疊

    堆疊的抽象資料結構如下:

    S is a stack.
    
    sub IsEmpty(S): bool
    (Optional) sub IsFull(S): bool
    (Optional) sub Size(S): size >= 0
    sub Peek(S): data
    sub Push(S, data): void
    sub Pop(S): data
    

    由此可知,堆疊至少有以下四個公開行為:

    • IsEmpty(S):檢查堆疊是否為空
    • Peek(S):檢視堆疊最上方的元素,堆疊大小不變
    • Push(S, data):存入新的元素,堆疊大小加 1
    • Pop(S):取出堆疊最上方的元素,堆疊大小減少 1

    以下兩個是選擇性的:

    • IsFull(S):檢查堆疊是否已滿
    • Size(S):回傳堆疊的大小

    (影片教學) 堆疊的基本操作

    本影片講解堆疊的基本操作:

    本影片的內容偏概念上的說明,不影響程式碼閱讀,有興趣的讀者可自行觀看。

    宣告堆疊類別

    以串列實作堆疊時,通常會用額外的 node_t 類別做為內部儲存資料的節點:

    class Node:
        data <- none
        next <- null
    
    class Stack:
        top <- null
    

    如果想要取得堆疊的大小,建議額外新增一個屬性,用來儲存堆疊的大小。每次推入 (或移出) 元素時就將堆疊大小加 (或減) 一。

    以等效的 C 語言實作如下:

    typedef struct node node_t;
    
    struct node {
        int data;
        node_t *next;
    };
    
    typedef struct stack stack_t;
    
    struct stack {
        node_t *top;
    };

    堆疊使用雙向連結節點沒有額外的好處,故此處使用單向節點。

    有些教材會採用類似以下的宣告:

    typedef struct node node_t;
    typedef node_t * node_p;
    
    struct node {
        int data;
        node_p next;
    };
    
    typedef struct stack stack_t;
    
    struct stack {
        node_p top;
    };

    關鍵的差別在於用 node_p 做為指標型別 node_t * 的別名。一般來說,不建議對指標型別用別名,因為我們會在心理上誤以為該變數不是指標,因而造成撰碼時的錯誤。如果要對指標型別做別名,要在名稱上加上一些可辨識的名稱,像是 _pPtr 等變數的後綴。我們之後不會採用這種方式撰寫程式碼。

    堆疊的建構函式

    以 C 語言實作堆疊的的建構函式:

    stack_t * stack_new()
    {
        stack_t *s = malloc(sizeof(stack_t));
        if (!s)
            return s;
    
        s->top = NULL;
    
        return s;
    }

    malloc 實際上是有可能失敗的,故需撰寫錯誤處理相關的程式碼。這裡在 malloc 失敗時,回傳空的指標。

    堆疊的解構函式

    堆疊內部的節點以連結串列的方式相接,我們要逐一釋放掉這些節點。我們會用到兩個額外的指標,currtempcurr 一開始指向內部節點的頭端,而 temp 是暫存值。

    一開始先將 temp 指向 curr 所在的節點:

    釋放堆疊內部節點 (第一步)

    我們將 curr 移至下一個節點,這時候就可以將 temp 所在的節點釋放掉:

    釋放堆疊內部節點 (第二步)

    重覆這個動作,就可以把所有的內部節點釋放掉。實際上這些動作會寫在迴圈裡,就可以自動迭代。

    以下是解構函式的 C 語言實作:

    void stack_delete(void *self)
    {
        if (!self)
            return;
        
        node_t *curr = ((stack_t *) self)->top;
        while (curr) {
            node_t *temp = curr;
            curr = curr->next;
            free(temp);
        }
        
        free(self);
    }

    釋放記憶體時要由內而外釋放,要不然會無法追蹤內部節點的記憶體區塊。

    檢查堆疊是否為空

    堆疊的頂端本身是一個指標,檢查該指標是否為空,即可確認堆疊是否為空。以下是檢查堆疊是否為空的虛擬碼:

    S is a stack.
    
    sub IsEmpty(S): bool
        return S.top == null
    

    此處的 top 是指標,我們以 top 是否為空來檢查堆疊是否為空。除了這個方式,可以在類別中多放一個欄位,用來存堆疊大小的資訊,這樣就不用每次都從頭開始算,也可以用來檢查堆疊大小是否為 0。

    以下是等效的 C 語言實作:

    bool stack_is_empty(const stack_t *self)
    {
        assert(self);
    
        return !(self->top) ? true : false;
    }

    檢視堆疊頂端的資料但不取出

    以下是檢視堆疊頂端資料的虛擬碼:

    S is a stack.
    
    sub Peek(S): data
        assert not IsEmpty(S)
    
        return self.top.data;
    

    要先確認堆疊不為空,之後直接存取首節點的資料即可。

    以下是 Peek 等效的 C 語言實作:

    int stack_peek(const stack_t *self)
    {
        assert(!stack_is_empty(self));
        
        return self->top->data;
    }

    將資料推入堆疊

    先建立一個新的資料節點 (node),將該節點指向 top 所在的節點,並將 top 也指向該節點:

    將資料推入堆疊 (步驟一)

    接著再將 top 重新指向該節點即可:

    將資料推入堆疊 (步驟二)

    以下是將資料推入堆疊的虛擬碼:

    S is a stack.
    
    sub Push(S): void
        n <- node(data)
        
        n.next <- S.top
        S.top <- n
    

    不論目前首節點為 null 或有節點存在,本虛擬碼皆適用,讀者可試著追蹤一下程式碼即可了解。

    以下是等效的 C 語言實作:

    bool stack_push(stack_t *self, int data)
    {
        node_t *n = node_new(data);
        if (!n) {
            return false;
        }
    
        n->next = self->top;
        self->top = n;
        
        return true;
    }

    由於這裡牽涉到配置記憶體,故我們將公開界面改為回傳布林值,表示程式成功與否的狀態。

    node_new 的參考實作如下:

    static node_t * node_new(const int data)
    {
        node_t *n = malloc(sizeof(node_t));
        if (!n) {
            return n;
        }
    
        n->data = data;
        n->next = NULL;
    
        return n;
    }

    將資料從堆疊取出

    為了要將資料移出堆疊,我們會用到一個額外的指標 curr。一開始先將 curr 指向 top 所在的節點:

    將資料移出堆疊 (步驟一)

    top 移往下一個節點後,就可以將 curr 指向的節點釋放掉:

    將資料移出堆疊 (步驟二)

    如果堆疊只有單一節點呢?這時候同樣的步驟也成立,只是 top 在移動後會剛好指向空值 (NULL)。

    以下是將資料從堆疊取出的虛擬碼:

    S is a stack.
    
    sub Pop(S): data
        assert(not IsEmpty(S))
    
        curr <- S.top   
        popped <- curr.data
        
        S.top <- curr.next
        delete curr
        
        return popped
    

    由於我們一開始就先排除堆疊為空的情形,之後的虛擬碼是建立在堆疊不為空的假設上。只要將頭端指標指向下一個節點後釋放原節點即可。即使下一個節點為 null,本虛擬碼仍適用,讀者可自行追蹤虛擬碼即可了解。

    以下是等效的 C 語言實作:

    int stack_pop(stack_t *self)
    {
        assert(!stack_is_empty(self));
        
        node_t *temp = self->top;
        int popped = temp->data;
        
        self->top = temp->next;
        free(temp);
        
        return popped;
    }

    在演算法上的效率

    根據本範例的實作得到的程式效率如下:

    • IsEmptyO(1)
    • PeekO(1)
    • PushO(1)
    • PopO(1)

    由於 mallocfree 是函式,實際上的效率會因實作而異。如果考試或檢定將 mallocfree 函式的效率視為 O(1),那麼 PushPop 的效率就會是 O(1)。我們在後續的文章中,不特別考慮 mallocfree 的效率。

    【分享本文】
    Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email
    【支持站長】
    Buy me a coffeeBuy me a coffee
    【贊助商連結】
    標籤: DATA STRUCTURES
    【分類瀏覽】