數據結構：鏈棧完整實現（初始化、入棧、出棧、遍歷）

數據結構：鏈棧完整實現（初始化、入棧、出棧、遍歷）

用鏈表實現棧（LIFO），包含結點定義、棧結構、四大核心操作、主函數測試、運行結果圖示。

結構定義

#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>

// 結點
typedef struct Node {
    int data;
    struct Node *next;
} Node, *PNode;

// 棧
typedef struct Stack {
    PNode top;
    PNode bottom;
} Stack, *PStack;

核心操作實現

初始化：建立頭結點

void init_stack(PStack s) {
    s->bottom = (PNode)malloc(sizeof(Node));
    s->top = s->bottom;
    s->bottom->next = NULL;
}

入棧：頭插法

void push(PStack s, int val) {
    PNode n = (PNode)malloc(sizeof(Node));
    n->data = val;
    n->next = s->top;
    s->top = n;
    printf("入棧：%d\n", val);
}

出棧：刪除頭結點後第一個

bool pop(PStack s, int *val) {
    if (s->top == s->bottom) {
        printf("棧空！\n");
        return false;
    }
    PNode n = s->top;
    *val = n->data;
    s->top = n->next;
    free(n);
    return true;
}

遍歷：從頂向下

void traverse(PStack s) {
    if (s->top == s->bottom) {
        printf("棧空！\n");
        return;
    }
    PNode p = s->top;
    printf("棧內元素：");
    while (p != s->bottom) {
        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n");
}

主函數測試

int main() {
    Stack s;
    int val;
    init_stack(&s);
    push(&s, 1); push(&s, 2); push(&s, 3);
    push(&s, 4); push(&s, 5); push(&s, 6);
    traverse(&s);  // 6 5 4 3 2 1
    if (pop(&s, &val)) {
        printf("出棧：%d\n", val);  // 6
        traverse(&s);  // 5 4 3 2 1
    }
    return 0;
}

運行結果

入棧：1
入棧：2
入棧：3
入棧：4
入棧：5
入棧：6
棧內元素：6    5    4    3    2    1
出棧：6
棧內元素：5    4    3    2    1

關鍵點總結

• 頭結點不存數據，簡化邊界處理
• 入棧/出棧均在棧頂操作，O(1)
• 出棧必須 free 釋放內存
• 遍歷不修改棧結構
• 可擴展：棧滿判斷(鏈棧無上限)、銷毀棧