054. 使用链表实现栈

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

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 
清空栈后是否为空：是

栈的特点

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

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

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)