链栈

2026 大纲 三（三）栈和队列的链式存储结构 · 栈部分（队列部分见《链式队列》）。

栈顶为什么必须在表头

链栈就是"一条单链表，但只允许在表头操作"，top 直接指向栈顶元素。

栈顶设在表头不是约定俗成，是被效率逼出来的。 假设把栈顶设在表尾：入栈要在尾部追加（有尾指针的话还行），但出栈要删掉尾结点，就必须先找到它的前驱——单链表没法往回走，只能从头遍历， $O (n)$ ，加尾指针也救不了。反过来把栈顶设在表头，入栈就是头插、出栈就是删首结点，两者都只动常数个指针， $O (1)$ 。

text

top → [a₃|next] → [a₂|next] → [a₁|NULL]
      栈顶元素                 栈底元素

同样的道理还解释了为什么链栈通常不设头结点：头结点的价值在于统一"首元结点"与其他结点的插删代码，而链栈只在表头操作，这个价值直接消失了。严蔚敏教材的原话是："由于栈的主要操作是在栈顶插入和删除，显然以链表的头部作为栈顶是最方便的，而且没必要像单链表那样为了操作方便附加一个头结点。"

先看一眼

加载可视化中...

对着动画确认一件事：入栈时新结点先接住原栈顶、top 后改。这两步的顺序和单链表头插法是同一个坑，反过来写会让新结点指向自己。

结构定义与四个基本操作

下面统一采用不带头结点的链栈。

typedef struct LinkNode {
    int data;               // 数据域
    struct LinkNode *next;  // 指针域，指向下一个结点（栈中"下面"那个元素）
} LinkNode, *LinkStack;

void InitStack(LinkStack *top) {
    *top = NULL;               // 不设头结点，空栈就是空指针
}

bool StackEmpty(LinkStack top) {
    return top == NULL;        // 与初始化保持一致
}

bool Push(LinkStack *top, int x) {
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    if (s == NULL) return false;   // 内存分配失败——链栈唯一的"失败"来源
    s->data = x;
    s->next = *top;                // 必须先接上原栈顶
    *top = s;                      // 再让 top 指向新结点
    return true;
}

bool Pop(LinkStack *top, int *x) {
    if (*top == NULL) return false;   // 栈空
    LinkNode *p = *top;               // 暂存待删结点，否则 free 时找不到它
    *x = p->data;                     // 先取数据，free 之后再读就是野指针
    *top = p->next;                   // 栈顶下移
    free(p);                          // 归还空间
    return true;
}

bool GetTop(LinkStack top, int *x) {
    if (top == NULL) return false;
    *x = top->data;                   // 只读，不改动任何指针
    return true;
}

这段代码里有三条纪律，每一条都对应一类常见错误：

🔴 参数必须是二级指针。 不带头结点时，入栈出栈都要改动 top 这个变量本身，所以形参写 LinkStack *top（或 C++ 引用）。写成传值的 LinkStack top，函数里的 top = s 只改副本，调用方那边纹丝不动——这是链栈代码题的头号错误。GetTop 与 StackEmpty 反而应该传值，因为它们不该修改栈。

🔴 入栈两步不能颠倒。 先 s->next = *top; 再 *top = s;。反过来的话，*top 已经变成 s，于是 s->next 指向了 s 自己——自环，原来整条链全部丢失，后续遍历死循环。

🔴 出栈必须留一个临时指针。 "先存地址、再改指针、最后释放"是链式删除的固定三步。直接写 *top = (*top)->next; 之后就再也找不到原结点的地址，free 不掉，内存泄漏。

带头结点的对照写法（题目要求带头结点时展开）

有的题目会要求链栈带头结点。此时 top 恒指向头结点，头结点不存数据：

// 带头结点：判空条件变了
bool StackEmpty_H(LinkStack top) { return top->next == NULL; }

bool Push_H(LinkStack top, int x) {          // 注意：不再需要二级指针
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    if (s == NULL) return false;
    s->data = x;
    s->next = top->next;                     // 插到头结点之后
    top->next = s;
    return true;
}

bool Pop_H(LinkStack top, int *x) {
    if (top->next == NULL) return false;     // 栈空
    LinkNode *p = top->next;
    *x = p->data;
    top->next = p->next;
    free(p);
    return true;
}

两种写法的差别只有一处根源：头结点让"栈顶指针"这个变量本身不再需要被修改，于是参数不必是二级指针（或引用），代价是多占一个结点、判空条件变成 top->next == NULL。

判空条件必须与初始化成对出现：不带头结点是 *top = NULL 配 top == NULL；带头结点是 top = malloc(...); top->next = NULL 配 top->next == NULL。代码题里两者写混，一定错。

没有上溢，但有下溢

链栈的空间按需 malloc，没有"栈满"这回事——唯一的失败来源是 malloc 返回 NULL。但空栈还 Pop 照样是错的：那是"对空栈做删除"这个逻辑错误，与存储方式无关。

🔴 上溢是顺序栈专有的，下溢两种实现都有。 把这两个混作一谈，是对比题里的典型失分点。

代价在另外两处。一是求栈长退化成 $O (n)$ ：链栈不存长度，只能从栈顶数到 NULL，而顺序栈用 top 一步算出。二是存储密度低于 1：设 int 与指针各 4 字节，每个结点 8 字节里只有 4 字节是数据，密度只有 $1 / 2$ ；64 位环境下指针 8 字节，密度降到 $1 / 3$ 。

所以"链式存储更省空间"是不对的——它省的是"预分配却没用上"的那部分，付出的是"每个已用结点固定多带一个指针"的开销。元素少时链栈省，元素多且容量能估准时顺序栈省。

求栈长、遍历、销毁，以及给链栈加计数器（要写这三个操作时展开）

// 求栈长：必须从栈顶数到 NULL
int StackLength(LinkStack top) {
    int len = 0;
    for (LinkNode *p = top; p != NULL; p = p->next)
        len++;
    return len;                    // O(n)
}

// 从栈顶到栈底遍历（注意方向：无法反向遍历）
void StackTraverse(LinkStack top) {
    for (LinkNode *p = top; p != NULL; p = p->next)
        visit(p->data);            // 访问次序是 栈顶 → 栈底
}

// 销毁：逐个释放，必须先存住 next
void DestroyStack(LinkStack *top) {
    while (*top != NULL) {
        LinkNode *p = *top;
        *top = p->next;            // 先把 next 取出来
        free(p);                   // 再释放，顺序不能反
    }
}

DestroyStack 里两句的顺序不能反：若先 free(p) 再读 p->next，读的是已释放内存，属于未定义行为。这与 Pop 里"先存地址、再改指针、最后释放"是同一条纪律。

顺序栈没有 DestroyStack 这一步（静态数组随结构体一起消失），但如果是动态分配的顺序栈（malloc 出来的数组），则只需一次 free(S.base)，仍然是 $O (1)$ ——这是"离散分配 vs 连续分配"在释放成本上的差别。

如果题目要求 $O (1)$ 求栈长，办法是给链栈加一个计数器：

typedef struct {
    LinkNode *top;   // 栈顶指针
    int count;       // 当前元素个数
} LinkStackWithCount;

入栈 count++、出栈 count--，求长度变成 $O (1)$ ，代价是多一个字段、且每处修改栈的地方都必须同步维护它——漏一处就长期不一致。这与《循环队列》里"增设 size 计数器"是同一种取舍。

链栈 vs 顺序栈

对比项	顺序栈	链栈
存储方式	静态数组，连续空间	链表，离散空间
容量	预分配 `MaxSize`，固定	按需 `malloc`，无固定上限
栈满（上溢）	会发生，`top == MaxSize-1`	不会，只可能 `malloc` 失败
栈空（下溢）	会发生，`top == -1`	会发生，`top == NULL`
空间利用	预分配过大则浪费，过小则上溢	按需分配，无浪费
存储密度	1	$< 1$ （每结点多一个指针域）
求栈长	$O (1)$ （由 `top` 算出）	$O (n)$ （需遍历，除非另设计数器）
缓存性能	好（连续存储，局部性强）	差（结点分散在堆上）
是否需要头结点	不涉及	通常不需要
适用场景	容量可预估、追求常数性能	容量不可预估、多个栈并存

入栈、出栈、取栈顶、判空这四个操作两种实现都是 $O (1)$ ，真正有量级差别的只有"求栈长"这一行。链栈还有一点与顺序栈不同：它不支持随机访问，要看栈中第 $i$ 个元素必须从栈顶走 $i - 1$ 步。

考点速记

这一节不单独成题。 链栈是栈的另一种实现，逻辑性质与顺序栈完全一致，真题不会单独问它的代码；它出现在卷面上的方式，是在对比题里作为"另一个选项"——问哪种实现会上溢、哪种求栈长更快、哪种存储密度高。所以这一篇要记的不是代码，是那张对比表里的差异项。

三条会被调用的结论：

栈顶设在表头是效率决定的：设在表尾则出栈要找前驱，退化成 $O (n)$ 。也正因为只在表头操作，链栈不需要头结点。
链栈没有上溢但有下溢，求栈长是 $O (n)$ ——这两点是对比题里最容易答错的。
"链式一定更省空间"是错的：存储密度只有 $1 / 2$ （64 位下 $1 / 3$ ），省下的是预分配的浪费，付出的是每结点一个指针。

易错：参数写成传值。 不带头结点的链栈，Push/Pop 必须用二级指针或引用，否则改的是副本。

易错：入栈两句写反。 先 s->next = *top 再 *top = s；反了会形成自环并丢掉整条链。

易错：出栈直接改指针不留临时变量。 先存地址、再改指针、最后 free，三步顺序固定。

教材出处

链栈的存储结构定义（StackNode / LinkStack），以及"以链表的头部作为栈顶最方便、 没必要附加头结点"：严蔚敏《数据结构（C 语言版）》（第 2 版）p60 「3.2.2 链栈——栈的链式存储表示」；链栈初始化算法 3.5、入栈算法 3.6 同页
链栈出栈算法 3.7（判空 → 取值 → 用 p 临时保存 → 修改栈顶指针 → 释放空间，五步顺序）与取栈顶算法 3.8：同书 p61

教材的出栈算法把"临时保存栈顶元素的空间，以备释放"单列为一个步骤，与本篇强调的"先存地址、再改指针、最后释放"完全一致。

链栈

栈顶为什么必须在表头

先看一眼

结构定义与四个基本操作

没有上溢，但有下溢

链栈 vs 顺序栈

考点速记

相关知识

相关文章

交互体验

真题练习

链栈 ​

栈顶为什么必须在表头 ​

先看一眼 ​

结构定义与四个基本操作 ​

没有上溢，但有下溢 ​

链栈 vs 顺序栈 ​

考点速记 ​

相关知识 ​

相关文章

交互体验

真题练习 ​

链栈

栈顶为什么必须在表头

先看一眼

结构定义与四个基本操作

没有上溢，但有下溢

链栈 vs 顺序栈

考点速记

相关知识

真题练习