408

数据结构

DS-03-01 栈的基本概念与实现（顺序栈/链栈）

---

一、定位信息

项目	内容
所属圈层	核心层
考点热度	H级（高频重点） — 栈是408数据结构中的常考知识点，近5年真题中选择题和大题均频繁出现，累计分值5–10分；栈的应用（表达式求值、递归模拟）更是大题高频考点
前置知识回顾	需掌握"线性表的基本概念与操作"（DS-02-01），理解顺序存储与链式存储的实现方式（DS-02-02、DS-02-03）
知识网络定位	栈是线性表的受限版本（只能在一端操作），是后续学习栈的应用（表达式求值、括号匹配、递归）的基础，也是理解深度优先搜索（DFS）等算法的必备知识

---

二、知识点讲解

2.1 栈的定义

栈（Stack） 是只允许在一端（称为栈顶，Top）进行插入和删除操作的线性表。另一端称为栈底（Bottom）。

栈遵循 后进先出（LIFO, Last In First Out）原则：最后入栈的元素最先出栈。

直观理解：栈就像一摞盘子——你只能从最上面放（入栈/Push）和取（出栈/Pop），不能从中间或底部抽。最后放上去的盘子一定最先被取走。

例子：依次将 A、B、C 入栈，然后执行两次出栈操作：

• 入栈顺序：A → B → C（此时栈顶为C）
• 第一次出栈得到 C
• 第二次出栈得到 B
• 栈中剩余：A（栈底）

2.2 栈的基本操作

操作	功能	时间复杂度
InitStack(&S)	初始化空栈	$O(1)$
Push(&S, e)	元素 e 入栈	$O(1)$
Pop(&S, &e)	栈顶元素出栈，用 e 返回	$O(1)$
GetTop(S, &e)	读取栈顶元素（不出栈）	$O(1)$
StackEmpty(S)	判断栈是否为空	$O(1)$
DestroyStack(&S)	销毁栈	$O(n)$

注意：Pop 与 GetTop 的区别——Pop 会移除栈顶元素并返回，GetTop 只读取不移除。

2.3 顺序栈（数组实现）

顺序栈 使用数组存储栈元素，用一个整型变量 top 指示栈顶位置。

初始化约定：

• top = -1 表示空栈（最常用约定，栈顶指针指向当前栈顶元素的位置）
• 入栈时先 top++ 再赋值
• 出栈时先取值再 top--

#define MaxSize 100           // 栈的最大容量

typedef struct {
    ElemType data[MaxSize];   // 存放栈元素的数组
    int top;                  // 栈顶指针，指向当前栈顶元素的下标
} SqStack;

// 初始化：栈顶指针设为-1表示空栈
void InitStack(SqStack &S) {
    S.top = -1;               // top=-1表示空栈
}

// 判断栈空
bool StackEmpty(SqStack S) {
    return S.top == -1;       // top为-1则栈空
}

// 入栈
bool Push(SqStack &S, ElemType e) {
    if (S.top == MaxSize - 1) // 栈满，无法入栈（上溢）
        return false;
    S.top++;                  // 栈顶指针上移
    S.data[S.top] = e;        // 将元素e放入栈顶
    return true;
}

// 出栈
bool Pop(SqStack &S, ElemType &e) {
    if (S.top == -1)          // 栈空，无法出栈（下溢）
        return false;
    e = S.data[S.top];        // 取出栈顶元素
    S.top--;                  // 栈顶指针下移
    return true;
}

// 获取栈顶元素
bool GetTop(SqStack S, ElemType &e) {
    if (S.top == -1)          // 栈空
        return false;
    e = S.data[S.top];        // 读取栈顶元素，不修改top
    return true;
}

关键点：top 的初始值不同教材可能有差异（有的用 top=0 表示空栈，入栈时先赋值再 top++），408 考试中以具体题目约定为准。最常用的是 top=-1 约定。

共享栈（两栈共享空间）：将一个数组的两端分别作为两个栈的栈底，两个栈顶向中间靠拢。当 top1 + 1 == top2 时栈满。适用于两个栈空间互补的场景。

2.4 链栈

链栈 使用单链表实现栈，链表头部作为栈顶。

typedef struct StackNode {
    ElemType data;            // 数据域
    struct StackNode *next;   // 指针域，指向下一个节点
} StackNode, *LinkStack;

// 初始化：空栈即为空链表（头指针为NULL）
void InitStack(LinkStack &S) {
    S = NULL;                 // 头指针为空
}

// 入栈：头插法
bool Push(LinkStack &S, ElemType e) {
    StackNode *p = (StackNode*)malloc(sizeof(StackNode)); // 分配新节点
    if (p == NULL) return false;                          // 内存分配失败
    p->data = e;              // 设置数据域
    p->next = S;              // 新节点指向原栈顶
    S = p;                    // 更新栈顶指针
    return true;
}

// 出栈：删除头节点
bool Pop(LinkStack &S, ElemType &e) {
    if (S == NULL)            // 栈空
        return false;
    StackNode *p = S;         // p指向栈顶节点
    e = p->data;              // 取出栈顶元素
    S = p->next;              // 栈顶指针后移
    free(p);                  // 释放原栈顶节点
    return true;
}

链栈不需要判满（除非内存耗尽），因为链表可以动态扩展。

---

三、记忆与理解辅助

技巧1：栈的核心口诀

"后进先出LIFO，栈顶操作最积极；入栈top往上走，出栈top往下移"

技巧2：顺序栈 vs 链栈对比表

比较项	顺序栈	链栈
存储方式	数组（连续空间）	链表（离散空间）
空间大小	固定容量（MaxSize）	动态分配，理论无限
判满条件	top == MaxSize-1	无需判满（仅内存不足时失败）
判空条件	top == -1	S == NULL
入栈/出栈时间	$O(1)$	$O(1)$
额外开销	无指针开销	每个节点多一个指针域
适用场景	栈大小可预估	栈大小不确定

技巧3：top 指针的两种约定

约定	初始值	入栈顺序	出栈顺序	判满
约定一（常用）	top = -1	top++ 再赋值	取值再 top--	top == MaxSize-1
约定二	top = 0	赋值再 top++	top-- 再取值	top == MaxSize

技巧4：栈的操作与线性表操作的类比

栈的操作本质是受限的线性表操作：

• Push ≈ 在表尾插入（ListInsert(L, n+1, e)）
• Pop ≈ 删除表尾元素（ListDelete(L, n, e)）
• GetTop ≈ 获取表尾元素（GetElem(L, n, e)）

---

四、例题与精解

例题1（基础）

题目：一个栈的入栈序列为 1, 2, 3, 4，则不可能的出栈序列是（ ）。 A. 4, 3, 2, 1 B. 1, 2, 3, 4 C. 1, 4, 2, 3 D. 3, 2, 1, 4

命题意图：考查对栈"后进先出"特性的理解，以及判断出栈序列合法性的能力。

审题分析：

• 已知：入栈顺序为 1→2→3→4
• 求解：哪个出栈序列不可能实现

解题思路： 逐一模拟每个选项的出入栈过程，判断是否存在矛盾。

完整步骤：

选项A（4,3,2,1）：全部入栈后依次出栈 → ✓

选项B（1,2,3,4）：

• 1入栈，1出栈
• 2入栈，2出栈
• 3入栈，3出栈
• 4入栈，4出栈 → ✓

选项C（1,4,2,3）：

• 1入栈，1出栈（栈空）
• 2入栈，3入栈，4入栈（栈：底[2,3,4]顶）
• 4出栈（栈：底[2,3]顶）
• 3出栈（栈：底[2]顶）
• 需要2出栈，但接下来需要3出栈，而3已出栈 ✗ → 不可能！

选项D（3,2,1,4）：

• 1入栈，2入栈，3入栈（栈：底[1,2,3]顶）
• 3出栈，2出栈，1出栈（栈空）
• 4入栈，4出栈 → ✓

答案：C

方法反思：

• 判断出栈序列合法性的方法：模拟法——按给定出栈顺序逐个元素模拟，检查是否矛盾
• 核心规律：若 $i < j < k$ 且出栈序列为 $\ldots, k, \ldots, i, \ldots, j, \ldots$（即 k 先出，i 次之，j 最后），则不可能——因为 k 出栈时 i 和 j 必须在栈中，且 i 在 j 下面，i 必须比 j 先出

例题2（中等）

题目：利用两个栈 S1 和 S2 模拟一个队列，写出入队（EnQueue）和出队（DeQueue）的算法。

命题意图：考查栈与队列特性的理解，以及利用受限数据结构模拟另一种数据结构的能力。

审题分析：

• 已知：两个栈可以使用
• 求解：实现队列的先进先出（FIFO）语义

解题思路：

• 核心思想：S1 作为入队栈，S2 作为出队栈
• 入队：直接压入 S1
• 出队：若 S2 非空则弹出 S2 栈顶；若 S2 为空则将 S1 中所有元素依次弹出并压入 S2，再弹出 S2 栈顶

完整步骤：

// 入队：直接将元素压入S1
void EnQueue(SqStack &S1, SqStack &S2, ElemType e) {
    Push(S1, e);              // 入队元素直接压入S1
}

// 出队：从S2弹出；若S2为空则将S1倒入S2
bool DeQueue(SqStack &S1, SqStack &S2, ElemType &e) {
    if (StackEmpty(S2)) {     // S2为空时
        while (!StackEmpty(S1)) { // 将S1中所有元素
            ElemType x;
            Pop(S1, x);       // 从S1弹出
            Push(S2, x);      // 压入S2（顺序翻转，变为FIFO）
        }
    }
    if (StackEmpty(S2))       // S1和S2都为空，队列为空
        return false;
    Pop(S2, e);               // 从S2弹出队首元素
    return true;
}

原理说明：

• S1 接收入队元素（顺序：1, 2, 3）
• 出队时将 S1 倒入 S2（S2 变为：底[3,2,1]顶），S2 弹出即为 1（队首）
• 关键：倒入操作只在 S2 为空时执行，保证每个元素最多被移动两次（入S1一次、倒入S2一次），摊还时间复杂度 $O(1)$

方法反思：

• 两栈模拟队列的核心是用两次翻转恢复先进先出顺序
• 类似地，可以用两个队列模拟一个栈（将一个队列的元素倒入另一个，留下最后一个作为栈顶弹出）
• 此题是408大题的经典考点，务必熟练掌握

---

五、考情分析

分析维度	内容
考查频次	栈的基本概念和操作近5年几乎每年都有涉及（选择题为主），栈的应用（表达式、递归）在大题中高频出现
常见题型	选择题（判断出栈序列、栈空栈满条件）、大题（栈的应用算法设计）
分值占比	选择题2分左右，大题结合应用可达5–10分
命题趋势	基本概念以选择题考查为主，趋势是与栈的应用结合出综合题（如表达式求值、括号匹配等）

注：以上频次基于大纲权重与通用命题规律推测，待真题分析后校准。

---

六、易错点提醒

易错点1

• 错误表现：混淆栈空和栈满的条件，特别是 top 的两种约定搞混
• 错误原因：不同教材对 top 初始值的定义不同（-1 或 0），考试时未看清题目约定
• 正确做法：先确认题目中 top 的约定，再推导判空/判满条件。记住：top=-1 约定下，判空为 top==-1，判满为 top==MaxSize-1

易错点2

• 错误表现：判断出栈序列时，遗漏某些合法序列或误判非法序列为合法
• 错误原因：仅凭直觉判断而没有系统模拟，特别是"部分入栈再出栈再入栈"的情况容易遗漏
• 正确做法：严格按照入栈顺序逐个模拟，对每个出栈元素检查"它是否已经入栈且在栈顶"

易错点3

• 错误表现：链栈入栈时忘记更新头指针，或出栈时忘记释放节点内存
• 错误原因：对链表头插法/删除头节点的操作不够熟练
• 正确做法：入栈三步——分配节点、设置next、更新头指针；出栈三步——保存节点、更新头指针、释放节点

易错点4

• 错误表现：顺序栈出栈时没有检查栈空，导致数组越界访问
• 错误原因：忽略边界条件检查
• 正确做法：每次 Pop 操作前必须先判断 StackEmpty

---

七、来源标注

• 依据2026考研统考大纲（408计算机学科专业基础综合）
• 依据《数据结构（C语言版）》严蔚敏版
• 依据《数据结构》王道考研辅导讲义

---