數據結構筆記 03 - 鏈式堆疊

Data Structure: Linked Stack

什麼是堆疊#

堆疊（stack）是一種後進先出（Last In First Out, LIFO）的線性表，表尾有特殊含義，稱為堆疊頂（top）。

堆疊的操作#

堆疊最常用的操作有兩種，一種是在表尾插入元素的操作稱為入堆疊（push），也叫壓堆疊；另一種是在表尾刪除元素的操作稱為出堆疊（pop），也叫彈堆疊。

堆疊 | inline

堆疊的表示#

堆疊可以用數組表示，也即順序堆疊，也可以用鏈表表示，叫做鏈式堆疊，簡稱鏈堆疊（本文主要討論對象）。
單鏈表可以在表頭、表尾或者其他任意合法位置插入元素，如果只能在單鏈表的表尾插入和刪除元素，那麼就可以將其視為鏈堆疊。
因此，在單鏈表的基礎上，我們再維護一個top指針即可。

鏈式堆疊的表示 | inline

注意
圖中每個節點的指針域next指針指向下一個節點，而非下一個節點的指針域。

堆疊的節點定義與 top 指針#

定義表示鏈堆疊節點的結構體

typedef struct stack_node {
    struct stack_node *next;
    void *data;
} stack_node;

定義表示鏈堆疊的結構體

typedef struct stack {
    struct stack_node *top;
    int length; // 表示堆疊的高度
} stack;

注意，top指針指向的是一個表示堆疊的節點的結構體。

函數清單#

下面是用於操作堆疊的函數名及其作用與複雜度

函數	作用	算法複雜度
stack_create	創建新的鏈式堆疊	O(1)
stack_release	釋放堆疊，以及堆疊中的節點	O(N)
stack_push	入堆疊	O(1)
stack_pop	出堆疊	O(1)
stack_empty	釋放堆疊中所有節點，但不釋放堆疊本身	O(N)

創建堆疊#

/* 創建堆疊 */
stack *stack_create()
{
    stack *stack = (struct stack *)malloc(sizeof(struct stack));
    /* 等價寫法：
    stack *s = (stack *)malloc(sizeof(stack)); */
    if (stack == NULL)
        return NULL;
    /* 初始化 */
    stack->length = 0;
    stack->top = NULL;
    return stack;
}

入堆疊#

/* 入堆疊 */
stack *stack_push(stack *stack, void *data)
{
    /* 創建一個節點 */
    stack_node *node = (struct stack_node *)malloc(sizeof(struct stack_node));
    if (node == NULL)
        return NULL;
    node->data = data;

    /* 插入 */
    node->next = stack->top;
    stack->top = node;

    stack->length++;
    return stack;
}

在有元素入堆疊時，首先創建一個節點，然後執行插入操作，將新節點的後繼節點next指向堆疊頂節點，接著移動堆疊頂指針至指向新節點node。最後，堆疊的高度自增 1。

入堆疊操作

出堆疊#

/* 出堆疊 */
void *stack_pop(stack *stack)
{
    /* 臨時保存堆疊頂元素 */
    stack_node *curr = stack->top;
    if (curr == NULL)
        return NULL;
    void *data = curr->data;
    stack->top = stack->top->next;

    free(curr);
    stack->length--;
    return data;
}

出堆疊時，首先臨時保存堆疊頂節點指針，用於在返回堆疊頂節點數據域的值之前的釋放操作。接著移動堆疊頂指針至堆疊頂節點的下一個節點。最後釋放臨時保存的節點，堆疊的高度自減 1，返回數據，出堆疊操作完成。

清空堆疊#

/* 清空堆疊中所有元素，但不釋放堆疊本身 */
void stack_empty(stack *stack)
{
    int length = stack->length;
    stack_node *curr, *next;
    curr = stack->top;

    /* 根據堆疊的高度確定刪除節點的次數 */
    while (length--)
    {
        next = curr->next;
        free(curr);
        curr = next;
    }

    stack->length = 0;
    stack->top = NULL;
}

清除堆疊#

/* 清空堆疊中所有元素並刪除堆疊 */
void stack_release(stack *stack)
{
    stack_empty(stack);
    free(stack);
}

測試#

同樣的，我們在 main 函數中測試。

int main()
{
    char a = 'a';
    char b = 'b';
    char c = 'c';

    /* 創建一個堆疊 */
    stack *stack = stack_create();

    printf("%p\n", stack_pop(stack));

    /* 壓堆疊 */
    stack_push(stack, &a);
    stack_push(stack, &b);
    stack_push(stack, &c);
    /* 出堆疊 */
    while (stack->length > 0)
    {
        printf("%c\n", *(char *)stack_pop(stack));
    }

    /* 壓堆疊 */
    stack_push(stack, &a);
    stack_empty(stack);
    printf("%p\n", stack_pop(stack));

    /* 釋放堆疊 */
    stack_release(stack);
    return 0;
}

編譯並輸出

# gcc -fsanitize=address -fno-omit-frame-pointer -g stack.c && ./a.out
(nil)
c
b
a
(nil)

完整代碼#

完整代碼，詳見代碼清單。
https://github.com/austin2035/learn-data-structures