以陣列 (Array) 為基礎的堆疊 (Stack)

    堆疊的抽象資料結構

    在本文中,我們仍然實作堆疊,但將內部實作從串列抽換成陣列。讀者可以和我們先前的文章相比較。

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

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

    由這個例子可以發現,即使在不同的實作中,公開界面可以是相同的。

    (影片教學) 以陣列為基礎的堆疊的基本操作

    以下影片介紹以陣列實作堆疊的方式:

    這個影片會拆解過程,供有需要的讀者參考。這個影片不影響程式碼的閱讀。

    堆疊型態的公開界面

    以下是堆疊型態的公開界面:

    #ifndef STACK_H
    #define STACK_H
    
    #ifndef __cplusplus
        #include <stdbool.h>
    #endif
    
    typedef struct stack_t stack_t;
    
    #ifdef __cplusplus
    extern "C" {
    #endif
    
    stack_t * stack_new(void);
    void stack_delete(void *self);
    bool stack_is_empty(const stack_t *self);
    int stack_peek(const stack_t *self);
    bool stack_push(stack_t *self, int data);
    int stack_pop(stack_t *self);
    
    #ifdef __cplusplus
    }
    #endif
    
    #endif  /* STACK_H */
    

    如果和前一篇文章比較,可以發現公開界面是相同的。在實作程式時,公開界面和內部實作是分開。在不更動公開界面的前提下,改善內部實作,就是對程式碼重構 (refactoring)。

    宣告堆疊類別

    以陣列為基礎的堆疊的內部如下:

    以陣列為基礎的堆疊

    在這個堆疊陣列中,隱含著兩個長度,size 表示堆疊當下的大小,capacity 表示堆疊的最大容量。另外 top 是陣列的索引 (index),指向堆疊的頭端。

    以陣列實作堆疊時,型態宣告如下:

    typedef struct stack stack_t;
    
    struct stack {
        size_t size;
        size_t capacity;
        size_t top;
        int *elements;
    };
    

    我們會在類別中儲存兩個堆疊大小的資訊,size 是目前的堆疊大小,capacity 則是堆疊的最大容量。由於我們使用環狀陣列,top 所指向的位置會移動,top 使用索引值取代指標來指向堆疊的頂點。

    堆疊的建構函式

    以 C 語言實作堆疊的建構子如下:

    stack_t * stack_new(void)
    {
        stack_t *s = malloc(sizeof(stack_t));
        if (!s)
            return s;
    
        s->size = 0;
        s->capacity = 2;
        s->top = 0;
        s->elements = malloc(s->capacity * sizeof(int));
        if (!(s->elements)) {
            stack_delete(s);
            s = NULL;
            return s;
        }
    
        return s;
    }
    

    在此處的 s->capacity 的值可設為任意大於等於 2 的值,一開始時通常會先預先配置某個大小的容量,像是 16 或 32;此處故意設為 2 是要測試擴展容量的情境。

    堆疊的解構函式

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

    void stack_delete(void *self)
    {
        if (!self) {
            return;
        }
    
        int *elements = ((stack_t *) self)->elements;
        if (elements)
            free(elements);
        
        free(self);
    }
    

    要先釋放堆疊內部的陣列後再釋放堆疊物件本身。由於內部陣列是整塊的記憶體,可以直接把整塊記憶體釋放掉,不需使用迴圈。

    檢查堆疊是否為空

    以下是 IsEmpty(S) 的 C 程式碼:

    bool stack_is_empty(const stack_t *self)
    {
        assert(self);
        return self->size == 0;
    }
    

    利用陣列大小來檢查堆疊是否為空即可。

    檢視堆疊頂端的資料

    以下是 Peek(S) 的 C 程式碼:

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

    以陣列實作堆疊時,top 是一個整數,作為陣列索引值,用來取代指標,指向堆疊的頂點。

    將資料推入堆疊頂端

    當我們要堆入節點時,要先將 top 移動到下一個節點所在的位置:

    將資料推入堆疊陣列 (步驟 1)

    接著推入新的資料節點即可:

    將資料推入堆疊陣列 (步驟 2)

    細心的讀者可能會想到堆疊容量滿出來的情境,其實我們會在推入資料節點前預先擴展堆疊陣列,詳見下文。

    以下是 Push 的 C 語言實作:

    bool stack_push(stack_t *self, int data)
    {
        if (!stack_expand(self))
            return false;
    
        if (stack_size(self) > 0)
            self->top = (self->top + 1) % self->capacity;
    
        self->elements[self->top] = data;
        self->size++;
    
        return true;
    }
    

    我們在要推入元素前,會先檢查堆疊是否已滿,若堆疊容量已達上限,則擴充容量;下文會再說明 stack_expand() 部分的程式碼。我們將 top 推移後塞入 data 並將 size 遞增 1,在這裡採用環狀陣列,故 top 的值要用環狀平移來處理。

    在平移 top 時,注意我們是將 top 指向陣列的後端而非前端,故其值為加 1 而非減 1。讀者自行追蹤程式碼就知道在此處指向尾端或頭端效果是相同的,只要方向一致即可。

    以下是等效的

    以下是 stack_expand() 的示意圖:

    擴展堆疊陣列

    我們建立一個新的陣列,新陣列的容量為原陣列的大小的兩倍,再逐一將元素從舊陣列拷貝到新陣列即可。

    以下是 stack_expand() 的 C 語言實作:

    static bool stack_expand(stack_t *self)
    {
        if (self->size < self->capacity) {
            return true;
        }
    
        int *old_arr = self->elements;
        self->capacity = self->size * 2;
        int *new_arr = malloc(self->capacity * sizeof(int));
        if (!new_arr) {
            return false;
        }
    
        size_t sz = 0;
        int i = self->top;
        int j = self->top;
        while (sz < self->capacity) {
            new_arr[i] = old_arr[j];
    
            i = i == 0 ? self->capacity - 1 : i - 1;
            j = j == 0 ? self->size - 1 : j - 1;
            sz++;
        }
    
        self->elements = new_arr;
        free(old_arr);
    
        return true;
    }
    

    當堆疊大小小於堆疊容量時,不需擴展容量,這時直接結束函式即可。反之,則使用環狀陣列的手法逐一複製元素。要注意 ij 平移的距離相異,因為 new_arrold_arr 的大小不同。

    將資料移出堆疊頂端

    當我們要將資料移出節點時,先將 top 節點的資料拷貝出來,再將 top 移動:

    將資料移出堆疊陣列 (步驟 1)

    其實我們已經完成了。原本舊的 top 節點所在的資料呢?在下一次推入資料時會自動覆蓋:

    將資料移出堆疊陣列 (步驟 2)

    以下是 Pop 的 C 程式碼:

    int stack_pop(stack_t *self)
    {
        assert(!stack_is_empty(self));
    
        int popped = self->elements[self->top];
    
        self->top = self->top == 0 ? self->capacity - 1 : self->top - 1;
        self->size--;
    
        return popped;
    }
    

    在本文的範例中,我們沒有縮減 (shrink) 堆疊,故只要將 top 遞移並將 size 遞減即可。由於我們的 S.top 指向陣列的尾端,故其值為減 1 而非加 1。隨著使用本範例程式的堆疊的過程,該堆疊所占的記憶體會漸增,如果很在意記憶體的消耗,可以自行嘗試實作縮減堆疊的函式。

    在實作時,self->top 的型別為 size_t,該型別的值無法小於 0,故採用範例中的方式來實作環狀佇列。

    演算法上的效率

    以本文實作的程式效率如下:

    • IsEmpty(S)O(1)
    • Peek(S)O(1)
    • Push(S, data):amortized O(1)
    • Pop(S)O(1)

    Push 在堆疊擴張時,程式效率為 O(n),但不是每次推入元素時都要擴張堆疊,透過攤平分析法 (amortized analysis) 可知效率為約略為 O(1)

    【分享本文】
    Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Yahoo
    【追蹤本站】
    Facebook Facebook Twitter