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

PUBLISHED ON MAR 11, 2019 — DATA STRUCTURES
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 使用索引值取代指標來指向堆疊的頂點。

    將類別宣告換成等效的 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_free(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];
    }

    將資料推入堆疊頂端

    以下是 Push 的虛擬碼:

    sub Push(S, data): void
        Expand(S)
        
        S.top <- (S.top + 1) % S.capacity
        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;
        }
    
        self->top = (self->top + 1) % self->capacity;
        self->elements[self->top] = data;
        self->size++;
    
        return true;
    }

    以下是 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 + 1) % S.capacity
            j <- (j + 1) % S.size
            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 + 1) % self->capacity;
            j = (j + 1) % self->size;
            sz++;
        }
        
        self->elements = newArr;
        free(oldArr);
        
        return true;
    }

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

    將資料移出堆疊頂端

    以下是 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)

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