Warning

含AI生成内容

栈（Stack）#

定义#

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

核心特性：后进先出（Last In First Out, LIFO）。

1
      ┌───┐ ← 栈顶（插入/删除端）
2
      │ e₃│
3
      ├───┤
4
      │ e₂│
5
      ├───┤
6
      │ e₁│
7
      └───┘ ← 栈底

基本操作#

操作	说明	时间复杂度
InitStack(&S)	初始化空栈	O(1)
Push(&S, e)	入栈（栈顶插入）	O(1)
Pop(&S, &e)	出栈（栈顶删除）	O(1)
GetTop(S, &e)	读栈顶元素	O(1)
StackEmpty(S)	判空	O(1)

易错：栈是”操作受限的线性表”，不是”特殊的存储结构”。栈描述的是逻辑结构上的操作限制，底层可以用顺序存储（顺序栈）或链式存储（链栈）实现。

卡特兰数（出栈序列计数）#

n 个不同元素依次入栈，合法的出栈序列总数为卡特兰数：

C(n) = \frac{C(2n, n)}{n + 1}

n	合法序列数
1	1
2	2
3	5
4	14
5	42

408 选择题常问”以下哪个不是合法的出栈序列”，可用卡特兰数验证总数，也可逐步模拟判断。

顺序栈#

存储结构#

1
#define MaxSize 50
2
typedef struct {
3
    int data[MaxSize];
4
    int top;                // 栈顶指针
5
} SqStack;

栈顶指针的两种约定（⭐选择题陷阱）#

约定	初始值	栈空	栈满	入栈	出栈
`top` 指向栈顶元素	`top = -1`	`top == -1`	`top == MaxSize-1`	先 `++top`，再赋值	先取值，再 `top--`
`top` 指向栈顶下一个位置	`top = 0`	`top == 0`	`top == MaxSize`	先赋值，再 `++top`	先 `top--`，再取值

408 考研默认采用 top = -1 的约定，但做题务必看清题目条件。两种约定下入栈/出栈的操作顺序恰好相反。

核心操作#

入栈（top=-1 约定）：

1
bool Push(SqStack *S, int x) {
2
    if (S->top == MaxSize - 1)    // 栈满上溢
3
        return false;
4
    S->data[++S->top] = x;       // 先移指针，再赋值
5
    return true;
6
}

出栈（top=-1 约定）：

1
bool Pop(SqStack *S, int *x) {
2
    if (S->top == -1)             // 栈空下溢
3
        return false;
4
    *x = S->data[S->top--];      // 先取值，再移指针
5
    return true;
6
}

复杂度分析#

操作	时间复杂度	说明
入栈/出栈/取栈顶	O(1)	只在栈顶操作，无需移动元素
空间复杂度	O(1)	辅助空间常数级

与顺序表对比：顺序表的插入/删除需要 O(n) 时间移动元素，而栈由于只在一端操作，所有操作均为 O(1)。

共享栈#

核心思想#

用一个大小为 MaxSize 的数组同时存放两个栈，相向生长：

1
下标:  0   1   2   ...       ...  MaxSize-2  MaxSize-1
2
      [s1  s1  s1] → 空闲区 ← [s2  s2        s2      ]
3
            ↑ top1                    ↑ top2

栈 1：栈底在下标 0，top1 从左向右增长
栈 2：栈底在下标 MaxSize-1，top2 从右向左增长

状态判断（⭐高频）#

状态	条件
栈 1 空	`top1 == -1`
栈 2 空	`top2 == MaxSize`
栈满	`top1 + 1 == top2`

⚠️ 易错：栈满条件是两个栈顶指针相邻，不是某一个栈到达数组中点。一个栈可以占用超过一半的空间，只要另一个栈还有余量。

入栈/出栈#

1
bool Push(SharedStack *s, int stackNum, int x) {
2
    if (s->top1 + 1 == s->top2)   // 栈满
3
        return false;
4
    if (stackNum == 1)
5
        s->data[++s->top1] = x;   // 栈1：指针右移后入栈
6
    else
7
        s->data[--s->top2] = x;   // 栈2：指针左移后入栈
8
    return true;
9
}

优点#

提高空间利用率
适用于两个栈此消彼长的场景（如一个增长时另一个收缩）

链栈#

存储结构#

1
typedef struct LinkNode {
2
    int data;
3
    struct LinkNode *next;
4
} LinkNode, *LinkStack;

逻辑结构（以链表头部作为栈顶）：

1
栈顶 → [a₃|next] → [a₂|next] → [a₁|NULL]

核心操作#

入栈（头插法）：

1
bool Push(LinkStack &top, int x) {
2
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
3
    if (s == NULL) return false;
4
    s->data = x;
5
    s->next = top;
6
    top = s;
7
    return true;
8
}

出栈（删头结点）：

1
bool Pop(LinkStack &top, int &x) {
2
    if (top == NULL) return false;  // 栈空
3
    LinkNode *p = top;
4
    x = p->data;
5
    top = p->next;
6
    free(p);
7
    return true;
8
}

易错：链栈通常不需要头结点，栈顶指针直接指向链表第一个结点。判空条件是 top == NULL。

顺序栈 vs 链栈#

对比项	顺序栈	链栈
存储方式	静态数组，连续空间	链表，离散空间
栈满溢出	可能溢出	不会溢出
空间利用	可能浪费（预分配过大）	按需分配
存储密度	高（无指针开销）	低（每个结点多一个指针）
缓存性能	好（连续存储）	差（离散存储）

考研高频考点#

⭐ 合法出栈序列的判断（选择题超高频）
⭐ top 初始值不同时入栈/出栈代码的区别
⭐ 共享栈栈满条件 top1 + 1 == top2
⭐ 链栈 vs 顺序栈的优缺点对比（简答题）
卡特兰数计算合法出栈序列总数
栈的三种实现（顺序栈、共享栈、链栈）的适用场景选择

关联页面#

队列（Queue） — 栈的姊妹结构，FIFO 线性表
栈和队列的应用 — 括号匹配、表达式求值、递归

音乐

音乐

栈（Stack）#

定义#

基本操作#

卡特兰数（出栈序列计数）#

顺序栈#

存储结构#

栈顶指针的两种约定（⭐选择题陷阱）#

核心操作#

复杂度分析#

共享栈#

核心思想#

状态判断（⭐高频）#

入栈/出栈#

优点#

链栈#

存储结构#

核心操作#

顺序栈 vs 链栈#

考研高频考点#

关联页面#

文章分享

评论区