開放原始碼技術文件網 以陣列 (Array) 為基礎的堆疊 (Stack)

最後修改日期為 MAR 11, 2019

堆疊的抽象資料結構

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

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

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