棧的鏈式存儲結構與操作實現（C語言）

棧的鏈式存儲結構與操作實現（C語言）

鏈棧：以單鏈表為存儲結構的棧，通常帶頭結點，棧頂指針指向頭結點。入棧/出棧均在表頭操作，O(1)。

結構定義

typedef struct node {
    StackElementType data;
    struct node *next;
} LinkStackNode;
typedef LinkStackNode *LinkStack;

進棧

int Push(LinkStack top, StackElementType x) {
    LinkStackNode *temp = malloc(sizeof(LinkStackNode));
    if (!temp) return FALSE;
    temp->data = x;
    temp->next = top->next;
    top->next = temp;  // 新節點成為首元節點
    return TRUE;
}

出棧

int Pop(LinkStack top, StackElementType *x) {
    LinkStackNode *temp = top->next;
    if (!temp) return FALSE;  // 棧空
    top->next = temp->next;
    *x = temp->data;
    free(temp);
    return TRUE;
}

多棧共存管理

定義指針數組 LinkStack top[M]，每棧獨立操作：

#define M 10
LinkStack top[M];

int push_i(LinkStack top[], int i, StackElementType x) {
    LinkStackNode *temp = malloc(sizeof(LinkStackNode));
    if (!temp) return FALSE;
    temp->data = x;
    temp->next = top[i]->next;
    top[i]->next = temp;
    return TRUE;
}

int pop_i(LinkStack top[], int i, StackElementType *x) {
    LinkStackNode *temp = top[i]->next;
    if (!temp) return FALSE;
    top[i]->next = temp->next;
    *x = temp->data;
    free(temp);
    return TRUE;
}

鏈棧無固定容量限制，適合元素數量動態變化大的場景；多棧共存只需管理棧頂指針數組。