From Gossip@caterpillar

Algorithm Gossip: 堆疊 - 使用鏈結實作（C 語言動態記憶體宣告）

說明

使用陣列實作堆疊，會受到陣列大小必須事先宣告好的限制，我們可以使用鏈結（link）的方式來實作堆疊，以動態記憶體宣告的方式來新增每一個元素。

解法

鏈結（link）是由節點組成，每一個節點儲存資料之外，還儲存下一個節點的位置，如下圖所示：

對堆疊而言，加入新節點與刪除節點的方法如下圖所示：
新增節點：

刪除節點：

鏈結也可以使用陣列來實作，不過在這邊我們以動態記憶體宣告的方式來進行，在C語言中，這是實作鏈結的基本作法，可以不受陣列大小必須先行宣告的限制，所以使用鏈結實作堆疊時，就不會有堆疊已滿的問題（除了記憶體用盡之外）。

上面的圖說只是個示意，在演算的時候，會需要一些暫存變數來協助節點新增與刪除時的連結更動，請直接參照以下的程式實作。

實作

#include <stdio.h> 
#include <stdlib.h> 

struct node { 
    int data; 
    struct node *next; 
}; 

typedef struct node getnode; 

getnode* creates(void);         // 建立堆疊 
int isEmpty(getnode*);           // 堆疊已空 
int stacktop(getnode*);   // 傳回頂端元素 
getnode* add(getnode*, int);   // 新增元素 
getnode* delete(getnode*);     // 刪除元素 
void list(getnode*);      // 顯示所有內容 

int main(void) { 
    getnode* sTop; 
    int input, select; 

    sTop = creates(); 

    while(1) { 
        printf("\n\n請輸入選項(-1結束)："); 
        printf("\n(1)插入值至堆疊"); 
        printf("\n(2)顯示堆疊頂端"); 
        printf("\n(3)刪除頂端值"); 
        printf("\n(4)顯示所有內容"); 
        printf("\n$c>"); 
        scanf("%d", &select); 
        
        if(select == -1) 
            break; 

        switch(select) { 
            case 1: 
                printf("\n輸入值："); 
                scanf("%d", &input); 
                sTop = add(sTop, input); 
                break; 
            case 2: 
                printf("\n頂端值：%d", stacktop(sTop)); 
                break; 
            case 3: 
                sTop = delete(sTop); 
                break; 
            case 4: 
                list(sTop); 
                break; 
            default: 
                printf("\n選項錯誤！"); 
        } 
    } 

    printf("\n"); 

    return 0; 
} 

getnode* creates() { 
    return NULL; 
} 

int isEmpty(getnode* top) { 
    return (top == NULL); 
} 

int stacktop(getnode* top) { 
    return top->data; 
} 

getnode* add(getnode* top, int item) { 
    getnode* newnode; 

    newnode = (getnode*) malloc(sizeof(getnode)); 

    if(newnode == NULL) { 
        printf("\n記憶體配置失敗！"); 
        exit(1); 
    } 

    newnode->data = item; 
    newnode->next = top; 
    top = newnode; 

    return top; 
} 

getnode* delete(getnode* top) { 
    getnode* tmpnode; 

    tmpnode = top; 
    if(tmpnode == NULL) { 
        printf("\n堆疊已空！"); 
        return NULL; 
    } 

    top = top->next; 
    free(tmpnode); 

    return top; 
} 

void list(getnode* top) { 
    getnode* tmpnode; 
    tmpnode = top; 

    printf("\n堆疊內容："); 
    while(tmpnode != NULL) { 
        printf("%d ", tmpnode->data); 
        tmpnode = tmpnode->next; 
    } 
}