054. 使用链表实现栈

在C语言中，使用链表实现栈是一种常见的方法。栈是一种后进先出（LIFO）的数据结构，支持两种主要操作：入栈（push） 和 出栈（pop）。使用链表实现栈可以动态地管理内存，避免固定大小数组的限制。

---

一、链表栈的核心实现方法

1. 数据结构定义

链表栈通过动态内存管理实现，需定义节点结构体与栈管理结构体：

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

// 节点结构体（存储数据与指针）
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 栈管理结构体（记录栈顶与容量）
typedef struct {
    Node* top;   // 栈顶指针
    int size;    // 栈元素数量
} LinkedListStack;

2. 核心操作函数

• 初始化栈：创建空栈，栈顶指针初始化为NULL，大小为0。
• 入栈（Push）：在链表头部插入新节点，时间复杂度为(O(1))。
• 出栈（Pop）：删除链表头部节点并释放内存，需判空处理。
• 获取栈顶元素（Peek）：直接访问栈顶节点的数据。
• 判空与容量查询：通过size字段或top指针判断。

3. 代码实现

// 初始化栈
LinkedListStack* createStack() {
    LinkedListStack* stack = (LinkedListStack*)malloc(sizeof(LinkedListStack));
    stack->top = NULL;
    stack->size = 0;
    return stack;
}

// 入栈（头插法）
void push(LinkedListStack* stack, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = stack->top;  // 新节点指向原栈顶
    stack->top = newNode;        // 更新栈顶指针
    stack->size++;
}

// 出栈
int pop(LinkedListStack* stack) {
    if (stack->size == 0) {
        printf("栈空，无法出栈！\n");
        return -1;
    }
    Node* temp = stack->top;
    int value = temp->data;
    stack->top = stack->top->next;  // 栈顶下移
    free(temp);                     // 释放原栈顶内存
    stack->size--;
    return value;
}

// 获取栈顶元素
int peek(LinkedListStack* stack) {
    if (stack->size == 0) {
        printf("栈空！\n");
        return -1;
    }
    return stack->top->data;
}

// 销毁栈（释放所有节点）
void destroyStack(LinkedListStack* stack) {
    while (stack->top != NULL) {
        Node* temp = stack->top;
        stack->top = stack->top->next;
        free(temp);
    }
    free(stack);
}

---

二、链表栈的适用范围

1. 适用场景

• 动态内存需求：数据量不可预估时（如实时数据流处理）。
• 频繁插入/删除：算法中需要临时存储中间结果（如递归模拟、表达式求值）。
• 复杂数据结构：需与其他链表结构配合（如内存管理中的空闲块链）。

2. 优缺点对比

特性	链表栈	数组栈
内存管理	动态分配，无空间浪费，但需额外存储指针	固定大小，可能溢出或浪费内存
性能	插入/删除快（(O(1))），访问慢（无法随机访问）	访问快，但扩容需拷贝数据（(O(n))）
适用场景	数据量变化频繁、需动态扩展的场景	数据量固定、访问速度优先的场景

---

三、典型应用场景

1. 函数调用栈模拟：递归算法中保存函数调用状态。
2. 表达式求值：处理后缀表达式（如 3 4 * 5 +）的运算符优先级。
3. 括号匹配校验：通过栈结构检查代码中的括号嵌套合法性。
4. 撤销操作（Undo）：记录操作历史，按后进先出顺序回退。

---

四、完整测试示例

int main() {
    LinkedListStack* stack = createStack();
    push(stack, 10);
    push(stack, 20);
    push(stack, 30);

    printf("栈顶元素：%d\n", peek(stack));  // 输出30
    printf("出栈元素：%d\n", pop(stack));    // 输出30
    printf("剩余栈大小：%d\n", stack->size); // 输出2

    destroyStack(stack);  // 释放内存
    return 0;
}

---

五、注意事项

1. 内存泄漏：每次pop需释放节点内存，销毁时需遍历释放所有节点。
2. 错误处理：操作空栈时需返回错误码或抛出异常（如返回-1或自定义异常）。
3. 性能优化：若需高频访问栈元素，可结合数组实现混合结构。

---

C语言实现链表栈

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

// 定义链表节点结构
typedef struct Node {
    int data;             // 数据域
    struct Node* next;    // 指针域，指向下一个节点
} Node;

// 定义栈结构
typedef struct {
    Node* top;            // 栈顶指针
} Stack;

// 初始化栈
void initStack(Stack* stack) {
    stack->top = NULL;    // 栈顶指针初始化为空
}

// 判断栈是否为空
int isEmpty(Stack* stack) {
    return stack->top == NULL;
}

// 入栈操作
void push(Stack* stack, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->data = value;    // 设置节点数据
    newNode->next = stack->top; // 新节点指向当前栈顶
    stack->top = newNode;      // 更新栈顶指针
}

// 出栈操作
void pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("栈为空，无法出栈！\n");
        return;
    }
    Node* temp = stack->top;  // 保存当前栈顶节点
    stack->top = stack->top->next; // 更新栈顶指针
    free(temp);               // 释放原栈顶节点
}

// 查看栈顶元素
int peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("栈为空，无法查看栈顶元素！\n");
        return -1; // 返回一个错误标志
    }
    return stack->top->data; // 返回栈顶元素
}

// 打印栈内容
void printStack(Stack* stack) {
    Node* temp = stack->top;
    printf("栈内容（从栈顶到栈底）：");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// 清空栈
void clearStack(Stack* stack) {
    while (!isEmpty(stack)) {
        pop(stack);
    }
}

int main() {
    Stack stack;
    initStack(&stack); // 初始化栈

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    printf("栈顶元素：%d\n", peek(&stack)); // 查看栈顶元素
    printStack(&stack); // 打印栈内容

    pop(&stack); // 出栈
    printf("出栈后栈顶元素：%d\n", peek(&stack)); // 查看栈顶元素
    printStack(&stack); // 打印栈内容

    clearStack(&stack); // 清空栈
    printf("清空栈后是否为空：%s\n", isEmpty(&stack) ? "是" : "否");

    return 0;
}

代码说明

链表节点结构 Node：每个节点包含一个数据域 data 和一个指针域 next，指向下一个节点。

栈结构 Stack：栈结构包含一个指针 top，指向栈顶节点。

初始化栈 initStack：将栈顶指针初始化为空。

判断栈是否为空 isEmpty：如果栈顶指针为空，返回 1（真），否则返回 0（假）。

入栈操作 push：创建一个新节点，将新节点的 next 指向当前栈顶，然后更新栈顶指针。

出栈操作 pop：

• 如果栈为空，打印错误信息并返回。

• 保存当前栈顶节点，更新栈顶指针，释放原栈顶节点。

查看栈顶元素 peek：

• 如果栈为空，打印错误信息并返回错误标志。

• 返回栈顶节点的数据。

打印栈内容 printStack：遍历链表，从栈顶到栈底打印所有元素。

清空栈 clearStack：通过循环调用 pop 函数，直到栈为空。

示例运行

输入：

无输入

输出：

栈顶元素：30
栈内容（从栈顶到栈底）：30 20 10 
出栈后栈顶元素：20
栈内容（从栈顶到栈底）：20 10 
清空栈后是否为空：是

栈的特点

1. 后进先出（LIFO）：最后入栈的元素最先出栈。
2. 动态内存管理：使用链表实现栈可以动态地分配和释放内存，避免固定大小数组的限制。
3. 效率：入栈和出栈操作的时间复杂度为 O(1)。
4. 适用性：栈适用于需要后进先出处理的场景，如函数调用、括号匹配、表达式求值等。

通过使用链表实现栈，可以灵活地管理栈中的元素，满足后进先出的特性。