C / C++ / 系统课时

用链表实现一个动态栈

用链表实现一个动态栈

链式栈把每个元素放进独立节点,并让 top 指向链表头部。入栈只需在头部插入节点,出栈只需删除头节点,因此无需预先声明固定容量,但必须正确处理 malloc 失败、节点释放和最终清理。

学习目标

  • 用链表头节点表示动态栈的栈顶
  • 正确实现动态入栈、出栈和读取栈顶
  • 管理节点的分配与释放,避免内存泄漏和悬空指针

为什么把链表头部当作栈顶

单链表在头部插入和删除都不需要遍历。把 top 直接指向头节点后,入栈可以把新节点的 next 指向旧栈顶,再更新 top;出栈则保存旧栈顶,令 top 指向下一个节点,最后释放旧节点。

若反过来把链表尾部当作栈顶,普通单链表在出栈时还需要寻找尾节点的前驱,操作会退化为 O(n)O(n)。因此“头部就是栈顶”是链式栈最关键的结构选择。

链式栈头部作为栈顶的指针变化

完整实现

下面用 Stack 保存栈顶指针和元素个数。stack_push 在内存分配失败时返回 false;stack_pop 成功后立即释放被移除的节点。

c
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *next;
} Node;

typedef struct {
    Node *top;
    size_t size;
} Stack;

void stack_init(Stack *stack) {
    stack->top = NULL;
    stack->size = 0;
}

bool stack_push(Stack *stack, int value) {
    Node *node = malloc(sizeof(*node));
    if (node == NULL) {
        return false;
    }

    // 新节点先连接旧栈顶,再成为新的 top。
    node->value = value;
    node->next = stack->top;
    stack->top = node;
    stack->size++;
    return true;
}

bool stack_pop(Stack *stack, int *out_value) {
    if (stack->top == NULL) {
        return false;
    }

    // 保存待删除节点,移动 top 后再释放它。
    Node *removed = stack->top;
    *out_value = removed->value;
    stack->top = removed->next;
    stack->size--;
    free(removed);
    return true;
}

bool stack_peek(const Stack *stack, int *out_value) {
    if (stack->top == NULL) {
        return false;
    }

    *out_value = stack->top->value;
    return true;
}

void stack_destroy(Stack *stack) {
    Node *current = stack->top;

    // 即使调用方没有逐个 pop,也要释放所有剩余节点。
    while (current != NULL) {
        Node *next = current->next;
        free(current);
        current = next;
    }

    stack->top = NULL;
    stack->size = 0;
}

int main(void) {
    Stack stack;
    int value;

    stack_init(&stack);

    if (!stack_push(&stack, 10) ||
        !stack_push(&stack, 20) ||
        !stack_push(&stack, 30)) {
        stack_destroy(&stack);
        return 1;
    }

    if (stack_peek(&stack, &value)) {
        printf("top=%d size=%zu\n", value, stack.size);
    }

    while (stack_pop(&stack, &value)) {
        printf("pop=%d size=%zu\n", value, stack.size);
    }

    stack_destroy(&stack);
    return 0;
}

预期输出

text
top=30 size=3
pop=30 size=2
pop=20 size=1
pop=10 size=0

最后一次出栈后 top == NULL,循环停止。stack_destroy 此时没有剩余节点可释放,但保留它仍然有价值:只要程序中途结束栈的使用,就可以统一调用它清理尚未出栈的节点。

内存管理是链式栈的边界

动态栈“不依赖固定容量”并不等于容量无限。每次入栈都需要 malloc 成功,实际容量受可用内存限制,因此 stack_push 必须把分配失败反馈给调用方。

出栈时,不能先 free(stack->top) 再读取它的 next,因为释放后继续访问该节点属于未定义行为。正确顺序是先保存旧栈顶指针与 next,更新 top,再 free 旧节点。

复杂度与适用场景

链式栈的入栈、出栈和读取栈顶都只修改头部指针,因此时间复杂度都是 O(1)O(1)。若当前有 nn 个元素,节点总空间为 O(n)O(n),但每个节点除了数据外还要额外保存一个 next 指针,并承担动态分配开销。

当元素数量波动明显、无法提前给出合理上限,或者希望栈只按实际元素数量占用节点空间时,链式栈很适合。若容量可预估且追求更好的连续内存访问、较少的分配开销,数组顺序栈通常更简单高效。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用链表实现一个动态栈

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通