美思 [資料結構] 使用 C 語言:以連結串列 (Linked List) 為基礎的堆疊 (Stack)

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):回傳堆疊的大小

堆疊型態的公開界面

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

#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, const int data);
int stack_pop(stack_t *self);

#ifdef __cplusplus
}
#endif

#endif  /* STACK_H */

扣除建構函式和解構函式外,這個堆疊型態有四個公開操作,算是中規中矩的界面。

我們使用 forward declaration 來製作 opaque pointer,這是為了防止外部程式直接接觸堆疊型態的屬性。在這樣的宣告下,只能使用我們宣告的函式來操作堆疊。我們在之後的資料結構也會採用這種方式。

宣告堆疊型態

以串列實作堆疊時,通常會用額外的 node_t 類別做為內部儲存資料的節點:

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;    /*  1 */
typedef node_t * node_p;       /*  2 */

struct node {                  /*  3 */
    int data;                  /*  4 */
    node_p next;               /*  5 */
};                             /*  6 */

typedef struct stack stack_t;  /*  7 */

struct stack {                 /*  8 */
    node_p top;                /*  9 */
};                             /* 10 */

本範例的關鍵處是我們在第 2 行時用 node_p 做為指標型別 node_t * 的別名。之後分別在第 5 行及第 9 行使用該別名。

一般來說,不建議對指標型別用別名,因為我們會在心理上誤以為該變數不是指標,因而造成撰碼時的錯誤。如果要對指標型別做別名,要在名稱上加上一些可辨識的名稱,像是 _pPtr 等做為別名的後綴。我們之後不會採用這種方式撰寫程式碼。

堆疊的建構函式

以 C 語言實作堆疊的的建構函式:

stack_t * stack_new()
{
    stack_t *s = malloc(sizeof(stack_t));
    if (!s)
        return s;

    s->top = NULL;

    return s;
}

malloc() 呼叫實際上是有可能失敗的,故需撰寫錯誤處理相關的程式碼。這裡在 malloc() 呼叫失敗時,回傳空的指標。

堆疊的解構函式

堆疊內部的節點以連結串列的方式相接,我們要逐一釋放掉這些節點。我們會用到兩個額外的指標,currtempcurr 一開始指向內部節點的頭端,而 temp 是暫存值。

一開始先將 temp 指向 curr 所在的節點:

釋放堆疊內部節點 (第一步)

我們將 curr 移至下一個節點,這時候就可以將 temp 所在的節點釋放掉:

釋放堆疊內部節點 (第二步)

重覆這個動作,就可以把所有的內部節點釋放掉。實際上這些動作會寫在迴圈裡,就可以自動迭代。

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

釋放記憶體時要由內而外釋放,要不然會無法追蹤內部節點的記憶體區塊。

檢查堆疊是否為空

堆疊的頂端本身是一個指標,檢查該指標是否為空,即可確認堆疊是否為空。以下是 C 語言實作:

bool stack_is_empty(const stack_t *self)
{
    assert(self);

    return !(self->top) ? true : false;
}

此處的 top 是指標,我們以 top 是否為空來檢查堆疊是否為空。

除了這個方式,可以在類別中多放一個欄位,用來存堆疊大小的資訊,這樣就不用每次都從頭開始算,也可以用來檢查堆疊大小是否為 0。

檢視堆疊頂端的資料但不取出

以下是檢視堆疊頂端資料的 C 程式碼:

int stack_peek(const stack_t *self)
{
    assert(!stack_is_empty(self));

    return self->top->data;
}

要先確認堆疊不為空,之後直接存取首節點的資料即可。

將資料推入堆疊

先建立一個新的資料節點 (node),將該節點指向 top 所在的節點,並將 top 也指向該節點:

將資料推入堆疊 (步驟一)

接著再將 top 重新指向該節點即可:

將資料推入堆疊 (步驟二)

以下是將資料推入堆疊的 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;
}

由於這裡牽涉到配置記憶體,故我們的公開界面會回傳布林值,表示程式成功與否的狀態。

不論目前首節點為 NULL 或有節點存在,本虛擬碼皆適用,讀者可試著追蹤一下程式碼即可了解。

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

將資料從堆疊取出

為了要將資料移出堆疊,我們會用到一個額外的指標 curr。一開始先將 curr 指向 top 所在的節點:

將資料移出堆疊 (步驟一)

top 移往下一個節點後,就可以將 curr 指向的節點釋放掉:

將資料移出堆疊 (步驟二)

如果堆疊只有單一節點呢?這時候同樣的步驟也成立,只是 top 在移動後會剛好指向空值 (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;
}

由於我們一開始就先排除堆疊為空的情形,之後的虛擬碼是建立在堆疊不為空的假設上。只要將頭端指標指向下一個節點後釋放原節點即可。即使下一個節點為 NULL,本虛擬碼仍適用,讀者可自行追蹤虛擬碼即可了解。

在演算法上的效率

根據本範例的實作得到的程式效率如下:

  • IsEmptyO(1)
  • PeekO(1)
  • PushO(1)
  • PopO(1)

由於 mallocfree 是函式,實際上的效率會因實作而異。如果考試或檢定將 mallocfree 函式的效率視為 O(1),那麼 PushPop 的效率就會是 O(1)。我們在後續的文章中,不特別考慮 mallocfree 的效率。

關於作者

身為資訊領域碩士,美思認為開發應用程式的目的是為社會帶來價值。如果在這個過程中該軟體能成為永續經營的項目,那就是開發者和使用者雙贏的局面。

美思喜歡用開源技術來解決各式各樣的問題,但必要時對專有技術也不排斥。閒暇之餘,美思將所學寫成文章,放在這個網站上和大家分享。