[資料結構] 使用 C 語言:以陣列 (Array) 為基礎的堆疊 (Stack)

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

    堆疊的抽象資料結構

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

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

    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
    

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

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

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

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

    宣告堆疊類別

    以陣列實作堆疊時,類別宣告如下:

    class Stack:
        size <- 0
        capacity <- n
        top <- 0
        elements <- an zero-based array which size == capacity
    

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

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

    以陣列為基礎的堆疊

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

    將上述類別宣告換成等效的 C 程式碼如下:

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

    堆疊的建構函式

    以 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;
        
        free(((stack_t *) self)->elements);
        free(self);
    }

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

    檢查堆疊是否為空

    以下是 IsEmpty 的虛擬碼:

    S is a stack.
    
    sub IsEmpty(S): bool
        return S.size == 0
    

    利用陣列大小來檢查堆疊是否為空即可。以下是等效的的 C 語言實作:

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

    檢視堆疊頂端的資料

    以下是 Peek 的虛擬碼:

    S is a stack.
    
    sub Peek(S): data
        assert(not IsEmpty(S))
        
        return S.elements[S.top]
    

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

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

    將資料推入堆疊頂端

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

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

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

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

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

    以下是 Push 的虛擬碼:

    sub Push(S, data): void
        Expand(S)
        
        if Size(S) > 0 then
            S.top <- (S.top + 1) % S.capacity
        end if
        
        S.elements[S.top] <- data
        S.size <- S.size + 1
    

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

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

    以下是等效的 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;
    }

    以下是 Expand 的示意圖:

    擴展堆疊陣列

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

    以下是 Expand 的虛擬碼:

    S is a stack.
    
    sub Extend(S): void
        if S.size < S.capacity then
            return
        end if
        
        S.capacity <- S.size * 2
        oldArr <- S.elements
        newArr <- a zero-based array with size is S.capacity
        
        sz <- 0
        i <- S.top
        j <- S.top
        while sz < S.size do
            newArr[i] <- oldArr[j]
            
            i <- i <= 0 ? S.capacity - 1 : i - 1
            j <- j <= 0 ? S.size -1 : j - 1
            sz <- sz + 1
        end while
        
        S.elements <- newArr
        delete oldArr
    

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

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

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

    由於 stack_expand 是私有函式,我們將其設為 static

    將資料移出堆疊頂端

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

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

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

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

    以下是 Pop 的虛擬碼:

    S is a stack.
    
    sub Pop(S): data
        assert(not IsEmpty(S))
        
        popped <- S.elements[S.top]
        S.top <- (S.top - 1) % S.capacity
        S.size <- S.size - 1
        
        return popped
    

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

    以下是等效的 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;
    }

    在實作時,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 Email
    【支持站長】
    Buy me a coffeeBuy me a coffee
    【贊助商連結】
    標籤: DATA STRUCTURES
    【分類瀏覽】