[資料結構] 使用 C 語言:堆疊 (Stack),以串列 (List) 實作

PUBLISHED ON MAR 4, 2019 — DATA STRUCTURES
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 失敗時,回傳空的指標。

    堆疊的解構函式

    以下是解構函式的 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;
    }

    將資料推入堆疊

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

    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;
    }

    將資料從堆疊取出

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

    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 的效率。

    你或許對以下產品有興趣:
    © 2014-2019. Michael Chen
    All code in the website is licensed under Apache 2.0 unless otherwise mentioned.