C / C++ / 系统课时
用链表实现一个动态栈
用链表实现一个动态栈
链式栈把每个元素放进独立节点,并让 top 指向链表头部。入栈只需在头部插入节点,出栈只需删除头节点,因此无需预先声明固定容量,但必须正确处理 malloc 失败、节点释放和最终清理。
学习目标
- 用链表头节点表示动态栈的栈顶
- 正确实现动态入栈、出栈和读取栈顶
- 管理节点的分配与释放,避免内存泄漏和悬空指针
为什么把链表头部当作栈顶
单链表在头部插入和删除都不需要遍历。把 top 直接指向头节点后,入栈可以把新节点的 next 指向旧栈顶,再更新 top;出栈则保存旧栈顶,令 top 指向下一个节点,最后释放旧节点。
若反过来把链表尾部当作栈顶,普通单链表在出栈时还需要寻找尾节点的前驱,操作会退化为 。因此“头部就是栈顶”是链式栈最关键的结构选择。

完整实现
下面用 Stack 保存栈顶指针和元素个数。stack_push 在内存分配失败时返回 false;stack_pop 成功后立即释放被移除的节点。
#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;
}预期输出
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 旧节点。
复杂度与适用场景
链式栈的入栈、出栈和读取栈顶都只修改头部指针,因此时间复杂度都是 。若当前有 个元素,节点总空间为 ,但每个节点除了数据外还要额外保存一个 next 指针,并承担动态分配开销。
当元素数量波动明显、无法提前给出合理上限,或者希望栈只按实际元素数量占用节点空间时,链式栈很适合。若容量可预估且追求更好的连续内存访问、较少的分配开销,数组顺序栈通常更简单高效。