建议先阅读: 容器概览 — 理解栈的底层存储(数组 vs 链表)和扩容机制。


原理


栈(Stack)是受限的线性数据结构——所有操作均发生在同端(栈顶),遵循后进先出(LIFO: Last In, First Out)。这种”单向开口”的约束看似限制了灵活性,实则赋予了栈一种精确的时序语义:最近入栈的数据最优先被处理。

栈在哪里

在写第一行栈代码之前,先看它已经在哪运转:每次函数调用都在向调用栈压入一个新栈帧,return 就是弹栈;编辑器的 Ctrl-Z 弹出的正是最近一次操作;浏览器的后退按钮弹出的是上一个页面;编译器判断 ({[]}) 是否配对靠的是括号栈。这些场景的共同主题——需要按”最近发生优先”的次序回溯——正是 LIFO 的用武之地。本章沿这条线展开:先把基础操作写扎实,再逐一拆解括号匹配与表达式求值,最后深入到硬件调用栈的底层机制。

操作描述时间复杂度
push(x)将 x 压入栈顶
pop()弹出栈顶元素
top()不弹出,只读栈顶
empty()是否为空
size()元素个数

栈的物理实现

栈作为抽象数据类型,有两种物理实现方式。选择取决于对容量、内存开销和缓存行为的需求。

数组实现(连续存储):

  • 在内存中预留一块连续区域,用 top 索引标记栈顶
  • 扩容策略见 容器章节 的均摊分析
  • 缓存友好——push/pop 都是顺序访问栈顶附近的内存

链表实现(节点存储):

  • 无容量上限,每个节点单独 malloc
  • 每次 push 带有堆分配开销(~50-200ns),pop 有释放开销
  • 由于只在头部操作,链表的”指针追踪”问题比完整链表遍历轻微——但连续 10 万次 push/pop 的累计堆开销远超数组版

栈的抽象数据类型、逻辑结构与存储结构

学习任何一个数据结构,都要回答四个问题:它的逻辑结构是什么、存储结构可能有哪几种、定义了哪些运算、这些运算如何用一套**抽象数据类型(ADT)**接口描述。栈的答案是:

维度栈
逻辑结构线性结构(元素一对一),但运算受限:只允许在同一端(栈顶)插入和删除
存储结构顺序栈(数组)/ 链栈(单链表头部)/ 共享栈
基本运算InitStack、DestroyStack、StackEmpty、Push、Pop、GetTop
重要特性后进先出(LIFO);栈顶是唯一”活跃端”

栈属于操作受限的线性表:逻辑上仍是一对一的线性关系,只是把”任意位置插删”收紧为”只能在端点插删”。因此顺序表的两种存储方式(顺序/链式)在这里都适用,只是实现更简单——所有操作都围绕端点。这与 线性表 中”同一套 ADT 接口,底层换数组或指针”的思想一脉相承。

栈与队列:共同点与差异

栈和队列经常成对出现,把它们的异同一张表理清,后面遇到组合题可以直接调用:

对比项栈队列
操作规则后进先出 LIFO先进先出 FIFO
逻辑结构线性结构(一对一)线性结构(一对一)
受限方式仅在同一端(栈顶)插入、删除在一端(队尾)插入、另一端(队首)删除
顺序存储顺序栈(top 指针)循环队列(front/rear)
链式存储链栈(在头部操作,无需尾指针)链队列(需队首、队尾两个指针)
空判定(顺序)top == -1(视约定)front == rear
经典应用括号匹配、表达式求值、递归、DFSBFS、缓冲区、调度、生产者-消费者

共同点归纳:

  1. 都是操作受限的线性表,逻辑结构都是线性的(一对一),属于线性结构而非非线性;
  2. 都可以用顺序存储或链式存储实现,存储方式与逻辑结构无关;
  3. 插入、删除都只在端点进行,因此核心操作均为 (数组版在扩容均摊意义下也是 );
  4. 都可以用双端队列(Deque) 统一描述——限制 Deque 的一端只出不进得到栈,限制两端一进一出得到队列;
  5. 都能用于保存中间状态、消除递归、处理具有先后次序要求的问题。

一句话记忆:栈是”单端受限”的线性表,队列是”双端分工”的线性表,二者都是 Deque 的退化。


深入底层

硬件级栈:x86-64 调用栈

栈不仅是抽象数据结构,更是 CPU 硬件原生支持的核心机制。x86-64 架构通过 rsp(栈指针寄存器)和 rbp(基址指针寄存器)提供硬件级栈支持:

flowchart TB
  H["⬆ 高地址"]
  M["main 的栈帧(局部变量等)\n← rbp (main 的基址指针)"]
  R["返回地址 ← call 指令推入的 rip, 8 字节"]
  F["foo 的栈帧\n← rbp (foo 的基址指针) ← rsp\nint a = 3 [rbp-4]\nint b = 5 [rbp-8]\nchar buf[32] [rbp-40]"]
  L["⬇ 低地址"]
  H --- M --- R --- F --- L
; C 代码: int add(int a, int b) { return a + b; }
 
add:
 push rbp ; 保存调用者的 rbp
 mov rbp, rsp ; 建立自己的栈帧基址
 mov DWORD PTR [rbp-4], edi ; 参数 a (通过 edi 传入)
 mov DWORD PTR [rbp-8], esi ; 参数 b (通过 esi 传入)
 mov eax, DWORD PTR [rbp-4]
 add eax, DWORD PTR [rbp-8] ; eax = a + b
 pop rbp ; 恢复调用者的 rbp
 ret ; 弹出返回地址并跳转

call 指令等价于 push rip; jmp target。ret 指令等价于 pop rip。这两个指令在硬件层面由 CPU 的返回栈缓冲器(Return Stack Buffer, RSB)加速——RSB 是 CPU 内部的一个微型硬件栈,专门缓存返回地址,使得 ret 指令可以达到接近 0 周期的延迟。

栈溢出(Stack Overflow):

栈段的大小受操作系统限制(Linux 默认 8MB,ulimit -s)。以下场景触发栈溢出:

  • 递归过深(如无终止条件的递归)
  • 局部变量过大(如在栈上声明 int arr[1000000],占 4MB,超出剩余栈空间)
  • 无限递归相互调用(A 调 B,B 调 A)

栈溢出的后果是 SIGSEGV——CPU 访存时 MMU 检测到访问地址超出栈的映射范围,硬件触发 page fault,内核检查发现地址不合法后向进程发送段错误信号。

栈溢出利用(Stack Smashing):

在安全领域,栈溢出是最经典的攻击向量。当程序向栈上的局部缓冲区写入超出其大小的数据时,溢出数据会覆盖更高的栈帧内容——包括返回地址。攻击者构造恶意输入,使返回地址指向其注入的 shellcode 或 ROP 链中的 gadget。

// 典型的栈溢出漏洞
void vulnerable(char* input) {
 char buf[64];
 strcpy(buf, input); // 如果 input 长度 > 64,覆盖返回地址
}
graph TD
 subgraph "正常栈帧"
 BUF["buf[0..63] (64字节)"] --- SFP["保存的 rbp (8B)"] --- RET["返回地址 (8B)"]
 end
 subgraph "溢出后的栈帧"
 BUF2["buf[0..63] + 溢出数据"] -->|"覆盖"| SFP2["伪造的 rbp"] -->|"覆盖"| RET2["指向 shellcode 的地址"]
 end

现代防御:栈 canary(返回地址前放随机值,ret 前检查)、W^X(栈页不可执行)、ASLR(随机化地址)、影子栈(shadow stack,硬件/软件维护一份返回地址副本用于验证)。

递归如何映射到栈帧

“递归就是系统替你维护了一个栈”——落到硬件上,每次递归调用执行 call 压入一个新栈帧(返回地址 + 参数 + 局部变量),基准情形触发后逐层 ret 弹栈。以 factorial(4) 为例,递推阶段栈帧的堆积:

flowchart TB
  M["main 帧"]
  F4["factorial(4)  [n=4 | 返回地址 | 等待 4 × f(3)]"]
  F3["factorial(3)  [n=3 | ...]"]
  F2["factorial(2)  [n=2 | ...]"]
  F1["factorial(1) ← 基准情形:直接返回 1"]
  M --> F4 --> F3 --> F2 --> F1

随后进入回归阶段:factorial(1) 返回 → 其帧弹出 → factorial(2) 拿到结果算出 2 → 弹出……直到 main。三个要点:

  1. 空间消耗 = 递归深度:同时存活的帧数即深度,——这正是链表章递归反转空间为 O(n) 的原因
  2. 深度超限 = 栈溢出:8MB 栈 ÷ 每帧几十字节 ≈ 十万量级深度上限(E2 实验可实测)
  3. 尾递归可优化:若递归调用是函数的最后一个动作(返回值不依赖后续计算),编译器可复用当前帧——gcc -O2 会做此优化,但 C 标准并不保证,不能依赖

单调栈(Monotonic Stack)

单调栈是栈的最强大变体之一——它维护栈内元素的单调性(递增或递减),通过 pop 掉破坏单调性的元素来找到”下一个更大/更小”的位置。

问题:给定数组 ,对每个位置 ,找出右侧第一个比 大的元素的下标。

例: A = [73, 74, 75, 71, 69, 72, 76, 73]

i=0 (73): 栈空,push 0
i=1 (74): A[1]=74 > A[栈顶=0]=73 → 答案[0]=1, pop 0, push 1
i=2 (75): A[2]=75 > A[栈顶=1]=74 → 答案[1]=2, pop 1, push 2
i=3 (71): A[3]=71 < A[栈顶=2]=75 → 栈单调递减,直接 push 3
i=4 (69): push 4
i=5 (72): A[5]=72 > A[栈顶=4]=69 → 答案[4]=5, pop 4
 A[5]=72 > A[栈顶=3]=71 → 答案[3]=5, pop 3, push 5
i=6 (76): A[6]=76 逐个弹出 5,2 → 答案[5]=6, 答案[2]=6, push 6
i=7 (73): A[7]=73 < A[栈顶=6]=76 → push 7
// 单调递减栈:找右侧第一个更大元素
void next_greater(const int* A, int n, int* result) {
 int* stk = malloc(n * sizeof(int));
 int top = 0;
 for (int i = 0; i < n; i++) {
 while (top > 0 && A[i] > A[stk[top - 1]]) {
 result[stk[--top]] = i; // 当前元素是栈顶的"第一个更大"
 }
 stk[top++] = i;
 }
 while (top > 0)
 result[stk[--top]] = -1; // 无更大元素
 free(stk);
}

时间复杂度 —— 每个元素入栈一次、出栈至多一次,总操作数不超过 。这是均摊分析在栈上的典型应用。

单调栈揭示了一个深层原理:需要比较”前后元素关系”的问题,往往可以通过维护一个单调序列来避免 的朴素扫描。从直方图最大矩形到每日温度,单调栈是这类问题的统一解法框架。


实现

基于数组的栈(顺序存储方式)

一,声明和初始化

首先要先创建栈的数据结构体。

typedef struct{
  int*data;         //一个指针,也可以用数组来表示。
  size_t top;      //栈顶指针,始终指向栈顶,其实是下标数字来表示
}Stack;

这里使用int * data,是一个指针,在基于数组的栈里,我们的操作是对于数组的限制化操作,用指针来代指数组里的位置,是动态数组操作的标志。
其实还可以用下面更加易于理解的方式。

typedef struct{
  int data[100];  //这里用静态数组直接表示,但是有空间限制
  size_t top;  //栈顶指针不变
}Stack;

使用静态数组表示,有空间限制,要标明空间大小,若不然无法控制溢出边界

声明栈
无论是那种顺序栈,静态还是动态,在创建好之后需要对其声明
在主函数里使用结构体的变量创建对象。
直接使用

Stack S;

即可
初始化操作

void Init(Stack *S){
  S.top=-1;
}

初始化操作的逻辑是让栈顶指针指向空处。
在链表中,所有操作都是针对栈顶指针进行操控的,栈顶指针始终指向栈顶。
因此初始化只需要让指针指向的“顶部”赋值为指定值即可。

实际上,在一些可变化的栈设定里,对顶部赋值是一定需要的,若不然,指针会变为野指针,整个栈都会失效。而赋值操作是随意,并不一定要为-1,可以是任意数
注意:静态数组里确定空间大小,指针赋值一定要小于最大值-1

在一般初始化逻辑里有两种操作,一种就是如上所示,赋值为-1,加下来的数组空间是,整个数组大小,从下标0开始,符合数组逻辑
还有一种如下:

void Init(Stack *S){
S.top=0;
}

是按照数学和日常逻辑来的,将0设定为无,统计从1开始,接下来的操作也是按照数组下标+1的逻辑进行。
top指针指向的是插入元素的位置。

二,进栈与出栈

进栈
新元素入栈的逻辑思路很简单。就是指定让新的栈顶为你所准备的值。
根据上方的两种不同初始化思路,其入栈思路也不同。
S.top=-1的那种,思路如下:

bool Push(Stack* S,ElemType x){  //EltmType在这里可以换成任意实际需要的数据类型,比如int
  S.top ++;
  S.data[S.top]=x;
}

首先让栈顶指针进一位,此时新的top指向的位置是空的,这个时候对其进行赋值,就是我们准备好的x值
可以写成一个操作来简化流程:

S.data[++S.top]=x;   //先自增,所以++放在前面

而S.top=0的思路里,顺序相反,因为top指针指向的是插入元素的位置,所以先进行赋值,再进行进位。如下:

S.data[S.top++]=x;

动态操作和静态操作思路一样,唯一区别在于边界判断。
边界判断
在进行入栈时,为了防止溢出,要优先进行边界判断,看看栈是否已满。
静态下的两种判断方式:

if(S.top==MAX-1)return false;     //Max是数组的最大值,这是S.top初始化为=-1的情形。

数组的最大下标是Max-1,因此当判断此时指针就是这个值的时候,已经最大了,无法进一位。
而如果设定top为输入位置呢?情况是另一种,

if(S.top==MAX)false;

当是栈顶的下一位的时候,才判定已经满了。

接下来是动态的边界判断
理论上动态数组从堆上分配内存,空间大小取决于硬件设施。
因此我们需要自己定义一个静态的最大边界。手动检查是否越过最大值。

if(S.top == S.MAX)

判断区别与上方静态一样,S.top一开始是-1就是当等于时返回,如果是0则只赋值,不进位。
实际上就算进位也没有影响,在堆上是没有硬性最大值的。
出栈
在栈的逻辑力,进出栈只能在栈顶操作,所以出栈只能找到最上层的数据。
而想让最上层离开,最基本的思路就是指针向下移动一位,保证栈顶是原本栈顶的下一位。
而判断方式则是判断当前是不是在栈底部。
有的时候栈底初始化不一样,操作顺序也不一样。比如S.top=-1的情况如下:

bool pop(Stack*S,ElemType x){
x=S.data[S.top--];
}

因为top是指向栈顶的,所以优先取值,再进行下移。
那么同理,如果S.top=0则要相反:

bool pop(Stack*S,ElemType x){
x=S.data[--S.top];
}

边界判断的思路如下:
在S.top=-1的情况下,判断S.top是否为栈底,也就是top是否为-1。
如果是则返回。
在S.top=0的情况下,判断S.top是否为0,如果是则返回。
动态和静态在出栈思路一致。

获取栈顶值

bool pop(Stack*S,ElemType x){
x=S.data[S.top];
}
//或者
bool pop(Stack*S,ElemType x){
x=S.data[S.top-1];
}

三,清空栈与销毁栈

清空栈的思路就是让所有东西都回到远点。
比如我们top指针已经在n了,需要让他重新指向-1或0,对于动态数组,还需要释放中途调用的指针。

bool clear(Stack*S){
S.top=-1;
}

不用特意清空数组,重新操作又是栈顶操作,会继续覆盖。逻辑上不会报错。
但是要不没被覆盖的部分已经被写好了数据,也会会有信息泄露的风险,可以配合循环遍历函数,使其全部赋值为空。

for(size_t i=-1;i<Max;i++){
  S.data[i]=0;
}

亦或者使用封装库

void clear(int *a, size_t n) {
    memset(a, 0, n * sizeof(*a));
}

如果数组作为函数传参,也就是动态分析下,其已经退化为指针,不能再用sizeof求长度,可以使用指针赋值为空的操作来做到归零操作。

free(p);
p = NULL;                  // 释放

静态分配的栈是无法进行整个销毁的,不过可以完全清空,也能释放所有内存。
而想要真正做到销毁整个栈,需要进行动态分配。
比如CPP里的

Stack *S = new Stack; //或者stack();
 
delete[] S->data;    //先释放内部数组。
delete S;
S=nullptr;      //防止悬空指针。

在C里

Stack*S = malloc(sizeof(Stack*));
 
free(S->data); //先释放内容
S->data=NULL;
free(S);

销毁和完全清空不完全一样,销毁是释放全部内存,包括栈,后续无法再使用。
而安全清空,也就是完全清空,是不销毁指针的,只把有效数据清空,后续还可以使用。

完整实现:

这里是动态数组的完整实现,静态数组过于简单,这里不做示范

#include <stdlib.h>
 
typedef struct {
 int* data;
 size_t capacity;
 size_t top; // 指向下一个空位,也是元素个数
} ArrayStack;
 
void as_init(ArrayStack* s) {
 s->data = NULL;
 s->capacity = 0;
 s->top = 0;
}
 
void as_destroy(ArrayStack* s) {
 free(s->data);
 s->data = NULL;
 s->capacity = s->top = 0;
}
 
static int as_expand(ArrayStack* s) {
 size_t new_cap = s->capacity == 0 ? 8 : s->capacity * 2;
 int* new_data = realloc(s->data, new_cap * sizeof(int));
 if (!new_data) return -1;
 s->data = new_data;
 s->capacity = new_cap;
 return 0;
}
 
int as_push(ArrayStack* s, int value) {
 if (s->top >= s->capacity)
 if (as_expand(s) != 0) return -1;
 s->data[s->top++] = value;
 return 0;
}
 
int as_pop(ArrayStack* s) {
 if (s->top == 0) return -1;
 s->top--;
 return 0;
}
 
int as_top(const ArrayStack* s, int* out) {
 if (s->top == 0) return -1;
 *out = s->data[s->top - 1];
 return 0;
}

顺序栈的两种栈顶指针约定(易错点)

顺序栈所有的判空、判满、入栈、出栈都依赖 top 的初值约定。教材主要有两种流派,做题第一步必须先看清题目用的是哪一种:

约定top 的初值top 指向判空判满(容量 MaxSize)入栈出栈
约定 A(主流)-1栈顶元素top == -1top == MaxSize - 1S[++top] = xx = S[top--]
约定 B0下一个可写位置top == 0top == MaxSizeS[top++] = xx = S[--top]

两种约定都能正确工作,但判界的表达式与代码完全互换:约定 A 的 ++top/top-- 到了约定 B 就成了 top++/--top。本节”基于动态数组的栈”用的是约定 B(top 指向下一个空位,同时也是元素个数)。408 选择题常给出其中一种约定,让你写出另一操作的语句或判断边界,务必按题给约定推导,不要凭记忆套公式。

记忆抓手:约定 A 的 top 是”元素下标”,所以空在 -1、满在 MaxSize-1;约定 B 的 top 是”元素个数”,所以空在 0、满在 MaxSize。

基于链表的栈

链表版栈所有操作均在头部——单向链表的 push_front + pop_front:

简单的说,链栈就是单向链表,且只在顶部(也就是链表的尾部)进行操作,自然分出有无头结点的区别。具体在出栈还有初始化上

一,创建与初始化

其实可以参照D_链表_LinkedList里的相关知识,这里简单引述:

首先定义链表类型的结构体。

typedef struct SNode{
  int data;
  struct SNode* next;
}SNode;

不带头结点的初始化。

SNode *top=NULL;

带头节点的初始化。

Snode *initStack(void) {
    Snode *head = (Snode *)malloc(sizeof(Snode));
    head->next = NULL;
    return head;
}

二,入栈还有出栈

不带头结点的:
简单来说,链栈有一个头指针,始终指向顶部,要想入栈,就需要新增加节点,然后让头指针指向它,做到更新顶部。

void push(SNode **top,int val){
  SNode *newNode=(SNode*)malloc(sizeof(SNode));
  newNode->data=val;
  newNode->next=*top;
  *top=newNode;
}

SNode** top就是那个顶部的头指针
让新节点指向这个头指针位置,然后更新头指针指向这个新节点。和不带头结点的单链表使用头插是一样的思路。

同理,出栈的话需要保存栈顶节点,然后让指针右移,从而做到去掉顶部。

void pop(SNode **top,int *out){
  SNode *tmp=*top; //创建指针指向顶部
  *out=tmp->data; //获取顶部值
  *top=tmp->next; //头指针右移
  free(tmp);  //销毁指针
}

从这里就可以知道为什么要使用头插单链表来模拟栈而不是尾插了。单链表里每个节点只能获知后一位节点的信息,同样,在只有一个节点的情况下,只能通过后移来进行跳跃,更新指针。
更具体一点的例子:
假如你有一个指针p,一个链表的某个节点Q,p指向Q(p=Q),因为你只能得到Q的下一位,也就是Q->next,而不能得到Q的上一位,所以要想变换指针p,只能做到p=p->next,或者更加往后的p=p->next->next,而做不到往前。
因此使用头插还有头删。
可以尝试使用尾插法的链表变体来模仿链栈。但是相对麻烦,除了示例,或一些特殊场景,否则很少使用。

带头结点:
入栈操作和单向链表的头插是一样的:

void push(Snode *head, int val) {
    Snode *newNode = (Snode *)malloc(sizeof(Snode)); //创建新节点
    newNode->data = val;
    newNode->next = head->next;   // 新结点指向原栈顶,记住是head->next,head是空节点
    head->next = newNode;         // 头结点指向新栈顶
}

同理出栈操作也是一样的:

void pop(Snode *head, int *out) {
    Snode *tmp = head->next;          //创建指针指向顶部位置
    *out = tmp->data;                  //存储值
    head->next = tmp->next;         //头指针指向原顶部下一位
    free(tmp);                       //销毁指针
}

三,清理和销毁栈

清空和销毁不一样,清空释放所有数据节点,最后要求:所有节点被释放,top == NULL,栈还能使用可以接着push,销毁则不能继续使用。

在不带头结点的链栈里,所有节点都是数据节点,没有额外的头结点,所以清空和销毁的代码基本一样。

不带头节点的清空:
循环释放所有数据结点,最后 top = NULL
清空后:

所有结点被释放;
top == NULL;
栈还能继续用,可以继续 push。

void clearStack(Snode **top) {
    Snode *p = *top;
    while (p != NULL) {
        Snode *tmp = p;
        p = p->next;
        free(tmp);
    }
    *top = NULL;
}

不带头结点的销毁
不带头结点的链栈里,所有结点都是数据结点,没有额外的头结点。

void destroyStack(Snode **top) {
    clearStack(top);
}

带头节点的清空:
释放所有数据结点,但保留头结点
清空后:

数据结点全部释放;
头结点还在;
head->next == NULL;
栈还能继续用。

void clearStack(Snode *head) {
    if (head == NULL) return;
 
    Snode *p = head->next;
    while (p != NULL) {
        Snode *tmp = p;
        p = p->next;
        free(tmp);
    }
    head->next = NULL;
}

带头结点的销毁:
先释放所有数据结点,再释放头结点,最后把头指针置空
销毁后:
所有结点包括头结点都被释放;
外部 head == NULL;
栈不能再使用。

void destroyStack(Snode **head) {
    if (head == NULL || *head == NULL) return;
 
    Snode *p = (*head)->next;
    while (p != NULL) {
        Snode *tmp = p;
        p = p->next;
        free(tmp);
    }
 
    free(*head);      // 释放头结点
    *head = NULL;     // 外部头指针置空
}

具体实现(不带头结点):

带头结点的版本可以自行实现

#include <stdlib.h>
 
typedef struct SNode {
 int data;
 struct SNode* next;
} SNode;
 
typedef struct {
 SNode* head;
 size_t count;
} LinkedStack;
 
void ls_init(LinkedStack* s) { s->head = NULL; s->count = 0; }
 
void ls_destroy(LinkedStack* s) {
 while (s->head) {
 SNode* tmp = s->head;
 s->head = s->head->next;
 free(tmp);
 }
 s->count = 0;
}
 
int ls_push(LinkedStack* s, int value) {
 SNode* node = malloc(sizeof(SNode));
 if (!node) return -1;
 node->data = value;
 node->next = s->head;
 s->head = node;
 s->count++;
 return 0;
}
 
int ls_pop(LinkedStack* s) {
 if (!s->head) return -1;
 SNode* tmp = s->head;
 s->head = s->head->next;
 free(tmp);
 s->count--;
 return 0;
}

两栈共享空间(双端栈)

固定大小的内存区域里,两个栈从两端向中间生长,共享同一段空间——这是经典模型:

graph LR
 subgraph "双端栈 — 共享数组"
 direction LR
 PUSH1["Stack 1 →<br/>push → top1++"] -->|"← 空闲空间 →"| PUSH2["← Stack 2<br/>top2-- ← push"]
 end
typedef struct {
 int* data;
 size_t capacity;
 size_t top1; // Stack 1: 从左向右增长
 size_t top2; // Stack 2: 从右向左增长
} TwoStacks;
 
void ts_init(TwoStacks* ts, size_t cap) {
 ts->data = malloc(cap * sizeof(int));
 ts->capacity = cap;
 ts->top1 = 0;          // 栈 1 的下一个写入位(左端起)
 ts->top2 = cap - 1;    // 栈 2 的下一个写入位(右端起)
}
 
// push 到栈 1
int ts_push1(TwoStacks* ts, int value) {
 if (ts->top1 > ts->top2) return -1; // 两栈碰撞
 ts->data[ts->top1++] = value;
 return 0;
}
 
// push 到栈 2
int ts_push2(TwoStacks* ts, int value) {
 if (ts->top1 > ts->top2) return -1;
 ts->data[ts->top2--] = value; // 索引递减
 return 0;
}

三个必背结论(本代码的下标约定:top1 从 0 起、top2 从 cap−1 起,均指向”下一个写入位”):

栈满条件推导:空闲格是下标区间 ,共 个;它归零等价于 ,即代码里的碰撞检查。这种设计让两侧空间动态调剂——比对半分成两个独立数组更抗溢出,且全程无 realloc。

注意教材另有 top1=-1 / top2=cap 的”指向栈顶元素”约定,其判满为 、判空分别为 -1 与 cap——做题第一步先确认题目采用哪种初始值。

手算示范:cap=8,栈 1 压 3 次、栈 2 压 2 次 → top1=3,top2=5;空闲格 个,总元素 个。

自测:两栈共享

cap=10,栈 1 已压 4 次、栈 2 已压 3 次。① 当前还能再压几个元素?② 若此后只在栈 1 一侧继续压,压几次溢出?

答案:

① top1=4、top2=6,空闲格 个——两侧合计最多再压 3 个。
② 只压栈 1:top1 从 4 走到 7 时 触发拒绝,故能再压 3 次(top1=5、6 时都还满足 ,第 4 次被拒)。注意临界:top1==top2 时那一格仍可写入,属于最后的机会。

括号匹配:栈的第一应用

规则只有三条:左括号一律进栈;右括号到来时弹栈比对类型(( 配 )、[ 配 ]、{ 配 });扫描结束时栈必须为空。对应三种失败情形:

失败时机错误类型例
弹栈时类型不符交叉嵌套([)]
栈空遇右括号右括号多余())
结束时栈非空左括号多余(()
int brackets_ok(const char* s) {
    char stk[256]; int top = 0;
    for (int i = 0; s[i]; i++) {
        char ch = s[i];
        if (ch == '(' || ch == '[' || ch == '{') {
            stk[top++] = ch;
        } else if (ch == ')' || ch == ']' || ch == '}') {
            if (top == 0) return 0;                    // 右括号多余
            char open = stk[--top];
            if ((ch == ')' && open != '(') ||
                (ch == ']' && open != '[') ||
                (ch == '}' && open != '{')) return 0;  // 类型交叉
        }
    }
    return top == 0;                                   // 结束时必须空
}

手算轨迹:判定 {[()]}——

步字符动作栈内容(底→顶)
1{进栈{
2[进栈{ [
3(进栈{ [ (
4)弹 (,匹配{ [
5]弹 [,匹配{
6}弹 {,匹配(空)

结束时空栈 → 合法。反例 ([)]:第 3 步遇 ) 时弹出的却是 [,类型不符立即失败。

自测:括号匹配

① 判定 ([]{}) 的合法性并写出栈变化。
② 判定 ((] 在哪一步失败、属于哪种错误。
③ 若串中只含一种括号 (),能否用 空间判定合法性?

答案:

① 合法。轨迹:(→([→]弹出后剩(→({→}弹出后剩(→)弹出后空;结束空栈,判定成立。
② 第 3 步失败:遇 ] 时弹出的栈顶是 (,类型不符——属于交叉嵌套错误(] 只应配 [)。
③ 可以。用一个计数器:左括号 +1、右括号 −1;中途出现负值(右多)或结束时非零(左多)即非法。这是栈在”只有一种括号”时的退化形式,也是面试的经典追问。

最小栈(MinStack)—— 用差值压缩空间

常规 MinStack 用两个同步栈(一个存数据,一个存前缀最小值)。更紧凑的做法是只存差值:栈内不存原始值,而存”当前值与当前最小值的差值”。

// 差值法:栈存储 value - min_sofar。通过差值的正负恢复 value 和 min
typedef struct {
 long* diff; // value - min_sofar (可能需要 long 防溢出)
 int* min_val; // 栈顶元素对应的当前最小值
 size_t capacity;
 size_t top;
} MinStackDiff;

此方案将空间从 2n 降至 n+1(只需 diff 数组和当前 min_val 变量),但每个 push 都涉及一次减法计算和溢出判断。常规的双栈法(空间 2n)因其简单性和无溢出风险,在实际工程中更为常用。

表达式求值

中缀 → 后缀(调度场算法)

int precedence(char op) {
 if (op == '+' || op == '-') return 1;
 if (op == '*' || op == '/') return 2;
 return 0;
}
 
// 将中缀表达式转为后缀(RPN)表示
void infix_to_postfix(const char* expr, char* output) {
 int len = strlen(expr);
 char* stk = malloc(len);
 int top = 0, out_idx = 0;
 for (int i = 0; i < len; i++) {
 char ch = expr[i];
 if (ch >= '0' && ch <= '9') {
 output[out_idx++] = ch;
 } else if (ch == '(') {
 stk[top++] = ch;
 } else if (ch == ')') {
 while (top > 0 && stk[top - 1] != '(')
 output[out_idx++] = stk[--top];
 top--; // 丢弃 '('
 } else { // 运算符
 while (top > 0 && precedence(stk[top - 1]) >= precedence(ch))
 output[out_idx++] = stk[--top];
 stk[top++] = ch;
 }
 }
 while (top > 0)
 output[out_idx++] = stk[--top];
 output[out_idx] = '\0';
 free(stk);
}

手算轨迹:把 9+(3-1)*3+10/2 转为后缀——逐步列出运算符栈与输出区:

步读入动作运算符栈(底→顶)输出区
19直接入输出(空)9
2+栈空,进栈+9
3(进栈+ (9
43入输出+ (9 3
5-栈顶是 (,进栈+ ( -9 3
61入输出+ ( -9 3 1
7)弹栈输出至 (:弹出 -,丢弃 (+9 3 1 -
8*栈顶 + 优先级低,进栈+ *9 3 1 -
93入输出+ *9 3 1 - 3
10+弹出 *、+(均 ≥ 新运算符),再进栈+9 3 1 - 3 * +
1110入输出+9 3 1 - 3 * + 10
12/栈顶 + 优先级低,进栈+ /同上
132入输出+ /... 10 2
14结束连续弹栈:先 / 后 +(空)9 3 1 - 3 * + 10 2 / +

最终后缀式 9 3 1 - 3 * + 10 2 / +。三个关键规则对照表格记忆:括号内的运算符被 ( 保护(第 5 步 - 得以压在 + 上);弹栈条件是”栈顶优先级 ≥ 当前”(左结合);) 触发一次性清到 ( 为止。

自测:写出 (a+b)*c-d 的后缀式。

答案:a b + c * d -。轨迹要点:) 把 + 弹入输出;* 进栈后遇到 -,因 * ≥ - 先弹 * 再压 -;结尾弹 -。

后缀表达式求值

// 计算后缀表达式(操作数为单个数字 0-9)
int eval_postfix(const char* postfix) {
 int len = strlen(postfix);
 int* stk = malloc(len * sizeof(int));
 int top = 0;
 for (int i = 0; i < len; i++) {
 char ch = postfix[i];
 if (ch >= '0' && ch <= '9') {
 stk[top++] = ch - '0';
 } else {
 int b = stk[--top]; // 弹出右操作数
 int a = stk[--top]; // 弹出左操作数
 switch (ch) {
 case '+': stk[top++] = a + b; break;
 case '-': stk[top++] = a - b; break;
 case '*': stk[top++] = a * b; break;
 case '/': stk[top++] = a / b; break;
 }
 }
 }
 int result = stk[0];
 free(stk);
 return result;
}
sequenceDiagram
 participant Input as 输入: "3 4 2 * +"
 participant Stack as 求值栈

 Input->>Stack: push 3
 Note over Stack: [3]
 Input->>Stack: push 4
 Note over Stack: [3, 4]
 Input->>Stack: push 2
 Note over Stack: [3, 4, 2]
 Input->>Stack: op '*': pop 2, pop 4
 Note over Stack: [3]
 Input->>Stack: push 8 (4*2)
 Note over Stack: [3, 8]
 Input->>Stack: op '+': pop 8, pop 3
 Note over Stack: []
 Input->>Stack: push 11 (3+8)
 Note over Stack: [11 ← 结果]

前缀表达式(波兰表达式)的转换与求值

后缀(逆波兰)由 Lukasiewicz 提出,前缀(波兰)也是同一思想:运算符写在操作数之前。例如中缀 1 + 2 的前缀式是 + 1 2。三种记法对照:

中缀前缀(波兰)后缀(逆波兰)
a + b+ a ba b +
(a + b) * c* + a b ca b + c *
a + b * c+ a * b ca b c * +

前缀式没有括号且求值方向从右向左:从右往左扫描,遇到操作数就压栈,遇到运算符就弹出两个操作数(先弹出的是左操作数)做运算,再把结果压栈。以 - * + 3 4 5 6(即 ((3+4)*5)-6)为例:

扫描(右→左)动作栈(底→顶)
6压栈6
5压栈6 5
4压栈6 5 4
3压栈6 5 4 3
+弹 3、4 → 3+4=76 5 7
*弹 7、5 → 7×5=356 35
-弹 35、6 → 35−6=2929
// 前缀(波兰)表达式求值:从右向左扫描
int eval_prefix(const char* prefix) {
    int len = strlen(prefix);
    int* stk = malloc(len * sizeof(int));
    int top = 0;
    for (int i = len - 1; i >= 0; i--) {
        char ch = prefix[i];
        if (ch == ' ') continue;
        if (ch >= '0' && ch <= '9') {
            stk[top++] = ch - '0';
        } else {
            int a = stk[--top];   // 先弹出的是左操作数
            int b = stk[--top];
            switch (ch) {
                case '+': stk[top++] = a + b; break;
                case '-': stk[top++] = a - b; break;
                case '*': stk[top++] = a * b; break;
                case '/': stk[top++] = a / b; break;
            }
        }
    }
    int result = stk[0];
    free(stk);
    return result;
}

中缀 → 前缀(两种写法都要会):

  1. 先转后缀、再翻前缀(适合手算):把中缀表达式整体倒序(同时交换左右括号),当成普通中缀转后缀得到后缀式,再把这个后缀式整体倒序,即为前缀式。
    例:a + b * c → 倒序得 c * b + a → 转后缀得 c b * a + → 再倒序得 + a * b c ✅
  2. 双栈法(适合写代码):一个操作数栈、一个运算符栈,从右向左扫描;遇到操作数入操作数栈,遇到运算符按优先级弹栈,最后把两栈拼成”运算符 + 左操作数 + 右操作数”。

408 与期末题里,中缀转前缀的要求出现得比后缀少,但”给中缀写前缀/给前缀求值”很常见。记住对照:前缀 = 后缀整体倒序,只是运算符落在最左。


递归:逻辑与实现

递归与栈是同一件事的两面:递归 = 系统替你维护一个栈(见 递归如何映射到栈帧)。这一节从算法层面讲清”递归怎么想、怎么写、怎么分析、怎么改成循环”,考点提炼放在下面的 高频考点(含真题)。

递归的逻辑:先递推,再回归

一个递归算法把大问题化成同类型的小问题,过程分两个阶段:

  • 递推(下行):不断把问题规模缩小,直到缩小到可以直接求解的最小规模;
  • 回归(上行):从最小规模的结果出发,逐层把结果算回来,拼出原问题的解。

以 factorial(4) 为例:下行 4→3→2→1(递推),到 1 触发终止条件;上行 1→2→6→24(回归)。映射到调用栈,就是一路压栈再一路弹栈。递归成立的前提是:每缩小一次,问题都变成”同类型的更小问题”。

递归的三要素

  1. 终止条件(基准情形):满足时直接返回,不再递归;
  2. 递归部分(递归步):把问题规模缩小后调用自身;
  3. 收敛性:每次递归都让规模严格减小,保证有限步内到达终止条件。

缺终止条件 → 无限递归 → 栈溢出;缺收敛性 → 可能永远到不了终止条件。

递归的实现:四种典型写法

// ① 线性递归:每层一个递归调用(阶乘 / 求和)
long factorial(int n) {
    if (n <= 1) return 1;              // 终止条件
    return n * factorial(n - 1);       // 递归步
}
 
// ② 树形递归:每层多个递归调用(斐波那契 / 汉诺塔)
long fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}
void hanoi(int n, char a, char b, char c) {
    if (n == 0) return;                // 终止条件
    hanoi(n - 1, a, c, b);             // 把上面 n-1 个从 a 借 c 移到 b
    printf("%c -> %c\n", a, c);        // 移动最大盘
    hanoi(n - 1, b, a, c);             // 再把 n-1 个从 b 借 a 移到 c
}
 
// ③ 分治递归:缩小后求解再合并(二分 / 归并)
int bsearch(int* a, int lo, int hi, int x) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == x) return mid;
    return a[mid] < x ? bsearch(a, mid + 1, hi, x)
                      : bsearch(a, lo, mid - 1, x);
}
 
// ④ 回溯递归:试探 + 撤销(全排列 / N 皇后),是树形递归的变体
void permute(int* a, int k, int n) {
    if (k == n) { /* 输出一个排列 */ return; }
    for (int i = k; i < n; i++) {
        swap(&a[k], &a[i]);            // 选择
        permute(a, k + 1, n);          // 进入下一层
        swap(&a[k], &a[i]);            // 撤销(回溯)
    }
}

递归怎么改成非递归

方法做法适用
尾递归改循环递归调用是最后一步且返回值不被后续使用,可改写成 while阶乘、累加、线性递归
显式栈模拟用自定义栈保存”待处理的现场/返回点”二叉树遍历、DFS、快排、回溯
记忆化 / 动态规划保存已求解的子问题,避免重复计算斐波那契、背包、LCS
队列层序展开把递归的层序过程改成队列迭代BFS、层序遍历

任何递归都能用显式栈改写成迭代——这就是”栈消除递归”的含义;反过来,用栈模拟系统调用就是手动维护栈帧。

递归的复杂度怎么估

  • 递归调用次数 = 递归树的结点数(决定时间);
  • 递归深度 = 递归树的高度(决定空间,也就是系统栈的最大帧数)。

常用分析工具:递推方程 (主定理)、递归树展开、猜解归纳。

递归算法递推关系时间复杂度空间(深度)
阶乘
朴素斐波那契
汉诺塔
二分查找
归并排序

递归的优缺点

优点:代码简洁、贴近数学定义、天然契合分治 / 回溯 / 树形结构。
缺点:函数调用有开销、可能重复计算(朴素斐波那契)、递归过深会栈溢出、常数因子通常比迭代大。


高频考点(含真题)

这一节把栈的概念题与手算推演题集中起来,与正文的教学内容分开,便于考前对照复习。历年统考真题另见下一节 408 真题精选。

考点 1:出栈序列合法性判定

问题:给定入栈序列(通常为 )与一个候选出栈序列,判断后者能否由前者产生。

判定准则:对任意一个元素 ,在它之后出栈、且比它后入栈的元素,必须保持”入栈顺序的逆序”出现。等价地说,若候选序列中存在 使得 (即出现 312 模式),则不合法——这就是”栈排序排列”与 312 模式的关系(见 扩展:更多栈模型与数学)。

通用判定算法(模拟法,):

// 入栈序列固定为 1..n,判断 pop[] 是否为合法出栈序列
int is_valid_pop(int n, const int* pop) {
    int stk[100]; int top = 0; int next_push = 1;
    for (int i = 0; i < n; i++) {
        while (top == 0 || stk[top - 1] != pop[i]) {
            if (next_push > n) return 0;   // 已无可压入的元素,仍未匹配
            stk[top++] = next_push++;      // 继续压入,直到栈顶正好是目标
        }
        top--;                             // 匹配成功,弹出
    }
    return 1;
}

手算口诀:先入者必后出。例如入栈顺序 1 2 3,出栈序列 3 1 2 不合法——要让 3 先出,1、2 必然都已按序入栈,栈顶是 2,因此 2 只能比 1 先出。

考点 2:出栈序列的枚举与计数(卡特兰数)

个互不相同的元素依次入栈,所有可能的出栈序列个数为第 个卡特兰数:

123456
1251442132

记忆与推导:把”入栈”记作 、“出栈”记作 ,则任意前缀和都 (不能出多于入)。所有 个含 个 、 个 的序列中,不合法的序列(存在某前缀和 )与”含 个 、 个 “的序列一一对应(反射原理),故

注意区分:卡特兰数说的是” 个不同元素的出栈序列数”。若元素有重复,需去重,不能直接套 。出栈序列的个数也等于: 个结点能构成的不同形态的二叉树个数、 对括号的合法匹配方案数——它们都是卡特兰数族(见 扩展:更多栈模型与数学)。

考点 3:由入栈序列与目标出栈序列反推操作序列

问题:给入栈序列与想要的出栈序列,写出每一步执行的是 push 还是 pop。

方法:从左到右扫描目标出栈序列,维护指针 i 指向下一个待压入元素。对每个目标元素 x:若栈顶等于 x,则 pop;否则把尚未压入的元素依次 push,直到把 x 压入,再 pop。若所有元素都压完仍无法匹配,则目标序列非法。

例:入栈 1 2 3 4 5,目标出栈 2 4 5 3 1:

push 1, push 2, pop(2), push 3, push 4, pop(4),
push 5, pop(5), pop(3), pop(1)

即操作序列 P P O P P O P O O O(P=push,O=pop)。这套操作序列是唯一确定的(对应 LeetCode 946 验证栈序列)。

考点 4:根据操作序列 / 出栈序列计算栈的最小容量

问题:给定入栈与出栈的完整操作序列,求栈在整个过程中达到过的最大深度,就是能完成该任务的最小栈容量。

方法:直接模拟,用计数器 size 记录当前栈内元素数,每 push 加一、每 pop 减一,全程取最大值。

例:入栈顺序 1 2 3 4,操作序列 P P P O O P O O:

操作PPPOOPOO
栈内数12321210

最大深度为 3,故栈容量至少为 3。

考点 5:栈与队列组合模拟求栈容量

当元素的输入顺序由队列决定时(队列出队的元素才依次入栈),求栈的最小容量,思路仍是模拟——只是”下一个入栈元素”要从队首取。题目常见的两种表述:

  • 队列 → 栈 → 输出:元素先按 入队,允许”出队并入栈”或”出栈”,求实现目标输出所需的最小栈容量;
  • 栈 → 队列 → 输出:类似。

统一做法:把”队首元素”当作考点 4 中”下一个待压入元素”,按同一套模拟统计栈内最大元素数即可。不要被”队列”干扰——队列只改变”入栈次序”,栈容量的定义不变。

考点 6:限制连续退栈次数的出栈序列判定

问题:入栈序列 a b c d e f 依次入栈,允许进栈、退栈交替进行,但不允许连续三次退栈,判断某出栈序列是否可能(2010 年 408 第 1 题,见 408 真题精选)。

快速判定法:连续退栈时,弹出的必然是入栈顺序的逆序连续片段。因此若出栈序列中含长度 的连续逆序子串(就题给字母表而言),则违反”不允许连续三次退栈”。例如 d c e b f a 中没有连续三个逆序,可行;而 a f e d c b 的尾部 f e d c b 是连续 5 个逆序,必然需要连续退栈 ≥ 3 次,因此不可能。

考点 7:栈空时弹出元素构成序列的判定

问题:在”允许任意时刻入栈/出栈(含入栈未完成时)“的混合操作下,判定一个带限制的目标序列是否可达。

  • 若允许任意时刻进出,判定方法与考点 1 的模拟法一致;
  • 若限制某一侧的操作(如”入栈未完成前不允许出栈""只允许在某时刻出栈”),则在模拟时把限制编码进状态机,枚举/回溯所有合法操作序列;
  • 若问”栈为空时还能否 pop”,答案是不能:对空栈执行 pop 属于下溢(underflow),是非法操作。

考点 8:中缀转后缀时运算符栈的最大容量估算

问题:把一个中缀表达式转成后缀,估算运算符栈(调度场算法里那个栈)最多需要多少格。

结论:运算符栈的最大深度 = 括号的最大嵌套深度 + 同时挂起的运算符个数。而”同时挂起的运算符”至多等于表达式涉及的不同优先级层数(通常 一层、 一层,共 2 层;含括号时再加 1 层保护),所以一个实用的上界是

例:9+(3-1)*3+10/2 的运算符栈最多同时容纳 2 个运算符(+ * 或 + /),嵌套深度 1、优先级层数 2,故容量 3 足够。最坏情况也不会超过”运算符总数”,但通常远小于它。填估算值时要按具体表达式逐步模拟,不要直接写运算符个数。

考点 9:顺序栈栈顶指针的不同初始约定

见 顺序栈的两种栈顶指针约定(易错点):约定 A(top=-1,指向栈顶元素)与约定 B(top=0,指向下一个空位)的判空、判满、入栈、出栈表达式全部成对互换。做题第一步确认约定,再套公式。

考点 10:递归调用次数计算

定义:递归调用次数 = 递归树中结点的总数(含初始调用),递归深度 = 递归树的最大层数。

递归递推关系调用次数深度
factorial(n)
Fibonacci(朴素)约 量级
汉诺塔 hanoi(n)
二分查找

汉诺塔推导: 展开得 次移动,也对应 次函数调用。

复杂度对比:递归调用次数决定时间,递归深度决定空间(系统栈帧数)。二者不一定同阶——斐波那契朴素递归调用是 、但深度只有 。

考点 11:算法设计策略与递归技术的关系

递归不是一种独立的算法,而是实现策略的通用手段。常见关系:

策略与递归的关系是否必须递归
分治把问题分成同类子问题递归求解,再合并(快排、归并、大整数乘法)可用递归或显式栈/循环
减治每步排除一部分规模(二分、快速选择),是递归的特例通常可改写成循环
动态规划递归 + 记忆化 = 自顶向下;填表 = 自底向上可递归可迭代
回溯递归枚举所有候选,失败则撤销(N 皇后、全排列)强烈依赖递归
树/图遍历DFS 天然递归,BFS 用队列迭代DFS 可手动栈改写

任何递归都能用显式栈改写为迭代(“栈消除递归”的核心);反过来,用栈模拟系统调用就是手动维护栈帧。

考点 12:递归算法必须包含终止条件与递归部分

一个正确的递归算法由三要素构成,缺一不可(选择题高频):

  1. 终止条件(基准情形 / base case):满足时直接返回,不再递归;
  2. 递归部分(递归步):把问题规模缩小后调用自身;
  3. 收敛性:每次递归都让规模严格减小,保证有限步内到达终止条件。

缺少终止条件会导致无限递归、进而栈溢出;缺少收敛性则可能永远到不了终止条件。例如 factorial 的终止条件是 n == 0 || n == 1,递归部分是 n * factorial(n-1)。

考点 13:递归与迭代的对比

对比项递归迭代(循环)
实现方式函数调用自身for / while 重复执行
空间靠系统调用栈,通常 (用显式栈时除外)
时间每层有函数调用开销,常数因子大常数因子小
可读性贴近数学定义,简洁直白,但有时繁琐
风险递归过深 → 栈溢出无栈溢出风险
适用分治、回溯、树形/嵌套结构线性、简单重复
转换递归一般可改迭代(用显式栈)迭代不一定能直接改递归

会考:判断题”递归一定比迭代慢 / 一定更占空间”(一般成立但不绝对——尾递归可被优化成循环);选择题问”哪些问题更适合递归 / 迭代”。

考点 14:递归的复杂度分析

  • 递归调用次数 = 递归树的结点数(决定时间);递归深度 = 递归树的高度(决定空间)。
  • 递推方程 用主定理求解;也可用递归树展开或猜解归纳。
  • 常见结果(必背):
递归算法递推关系时间复杂度空间(深度)
阶乘 / 线性递归
朴素斐波那契()
汉诺塔
二分查找
归并排序
快速排序(均摊/最坏)—— / /

会考:给一段递归代码,求其调用次数或时间/空间复杂度;比较朴素斐波那契 与记忆化后的 。

考点 15:尾递归与”递归转非递归”

尾递归:递归调用是函数体的最后一个动作,且其返回值不被后续计算使用。此时编译器可复用当前栈帧(尾调用优化),把空间降到 。注意:C 标准不保证尾调用优化,gcc -O2 通常会做,但考试中”能否依赖它”要谨慎。

// 普通递归:O(n) 空间
long fact(int n) { return n <= 1 ? 1 : n * fact(n - 1); }
// 尾递归写法:O(1) 空间(编译器优化后),可等价改写成 while 循环
long fact_iter(int n, long acc) {
    return n <= 1 ? acc : fact_iter(n - 1, n * acc);
}

递归转非递归的四种方法:

方法做法是否用栈
尾递归改循环直接把递归改写为 while否
显式栈模拟保存”待处理现场 / 返回点”是
记忆化 / DP自底向上填表,消除重复子问题否(用表)
队列层序展开把层序过程改成队列迭代(BFS)队列

会考:判断一段递归能否改写成循环(尾递归可以);填空”把二叉树先序遍历的递归改成非递归”(用栈);辨析”递归转非递归一定需要栈吗”(不一定,尾递归直接循环;分治/回溯通常需要栈)。

考点 16:带头结点 vs 不带头结点(链栈 / 单链表)

链栈可复用单链表的两种实现方式,差别集中在初始化、入栈(头插)、出栈(头删)与边界处理上:

对比项带头结点不带头结点
初始化分配头结点:head->next = NULL,返回 headtop = NULL
栈顶是谁head->next(头结点的后继)top 本身(指向首元结点)
判空head->next == NULLtop == NULL
入栈(头插)new->next = head->next; head->next = new;(改 head->next)new->next = top; top = new;(改 top)
出栈(头删)p = head->next; head->next = p->next; free(p);(head 不变)p = top; top = p->next; free(p);(top 被改)
是否需要二级指针不需要,传 SNode* 即可需要 SNode**(或返回新栈顶)
空栈处理统一,空栈也有头结点需特判 top == NULL
清空释放数据结点、保留头结点,head->next = NULL释放全部结点,top = NULL
销毁先释放数据结点、再释放头结点,head = NULL释放全部结点即可,top = NULL
空间开销多一个头结点无额外结点

核心结论:带头结点让”入栈/出栈”和普通头插/头删共用一套逻辑,不必修改头指针;代价是多一个不存数据的结点。链栈与单链表的这套区别完全一致(见 链表)。

考察内容:选择/填空比较两种实现;判断题考”带头结点链栈的栈顶到底是哪个结点""入栈是否修改头指针”。

考点 17:顺序栈 vs 链式栈

对比项顺序栈链式栈(链栈)
存储结构一段连续数组单链表结点,只在链头(栈顶)操作
栈顶标记top 下标(约定 A:-1 / 约定 B:0)top 指针(不带头)或头结点后继(带头)
初始化分配数组,top = -1(或 0)top = NULL(不带头)/ 创建头结点(带头)
判空top == -1(A)/ top == 0(B)top == NULL / head->next == NULL
判满需要:top == MaxSize-1(静态)或扩容(动态)无需判满,除非内存耗尽
入栈先判满再写,均摊 头插,
出栈先判空再取,头删,
扩容 / 溢出静态会上溢;动态 realloc 要搬移全部元素按需申请结点,天然可扩展,不会”上溢”(除非内存耗尽)
空间效率存储密度 = 1,但可能预留/浪费每结点多一个指针,存储密度 < 1
缓存行为连续、缓存友好,访问快指针追踪,缓存不友好
多栈共享两栈共享空间很自然(双端栈)需特殊设计,一般不共享
适用场景容量可预估、追求性能容量不可预估、插删频繁

选型口径:能预估上限且追求速度选顺序栈;上限未知、怕溢出选链栈。二者核心操作都是 ,差别在扩容、空间开销与缓存。

考察内容:结构选型选择/简答;比较判满条件、扩容代价、空间与缓存。

考点 18:清空 vs 销毁

对比项清空(Clear)销毁(Destroy)
目的删除所有数据元素,回到初始空状态释放结构占用的全部内存
结构是否可用仍可用,可继续入栈不可用(除非重新初始化)
顺序栈只把 top = -1(或 0),数组空间不释放(可循环覆写 0 防信息泄露)free(data); data = NULL; capacity = top = 0;
链栈(带头)释放数据结点,保留头结点,head->next = NULL先释放数据结点、再释放头结点,head = NULL
链栈(不带头)释放全部结点,top = NULL同清空(代码几乎相同),top = NULL
典型复杂度顺序 ;链式
误用风险安全(回到空态)悬空指针/双重释放——销毁后必须置空头指针

易错点:不带头结点的链栈里,“清空”和”销毁”的代码基本一样(都释放所有结点并置 top = NULL);只有带头结点时二者才明显不同——清空保留头结点、销毁连头结点一起释放。顺序栈的”清空”只改 top,不释放数组。

考察内容:概念选择/填空”清空后能否继续使用""销毁后头指针的值""带头结点清空保留什么""顺序栈清空做了哪件事”。


408 真题精选

这一节只放历年 408 统考真题,按年份排列。栈与队列、双端队列的题目互相穿插,队列相关的真题汇总在 F_队列_Queue > 408 真题精选,两处用交叉链接互相引用。

真题索引(栈与双端队列相关)

年份题号题目本题解位置
20101不允许连续三次退栈,不可能的出栈序列2010 第 1 题:不允许连续三次退栈
20132入栈 、 时 的取值个数2013 第 2 题:出栈序列中元素取值个数
20181操作数栈 + 运算符栈,调用 3 次 F()2018 第 1 题:双栈求表达式值
20202空栈 Push/Pop 操作序列的出栈序列2020 第 2 题:给定操作序列求输出

双端队列的真题(2010 第 2 题、2014 第 3 题、2021 第 2 题)与循环链队列应用题(2019 第 42 题)见 F_队列_Queue > 408 真题精选。

2010 第 1 题:不允许连续三次退栈

真题题干:

若元素 a, b, c, d, e, f 依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈操作,则不可能得到的出栈序列是( )。
A. d, c, e, b, f, a B. c, b, d, a, e, f C. b, c, a, e, f, d D. a, f, e, d, c, b

考察内容:把”连续退栈”翻译成”连续逆序子串”。连续退栈时弹出的元素必然按入栈顺序的逆序排列,因此只要出栈序列中出现长度 的连续逆序片段,就必然需要连续退栈至少 3 次。

解析:D 的尾部 f, e, d, c, b 是长度 5 的连续逆序,需要连续退栈 5 次,违反约束,故不可能。其余选项都能找到不含”连续 3 次退栈”的操作序列。

正确答案:D。

2013 第 2 题:出栈序列中元素取值个数

真题题干:

一个栈的入栈序列为 ,其出栈序列是 。若 ,则 可能取值的个数是( )。
A.  B.  C.  D. 无法确定

考察内容:在不写出完整序列的前提下,分析 能否取某值。

解析:

  • 由 可知只有两种开局:先弹出 2(,此时 1 还在栈中),或先弹出 1(,随后 2、3 入栈再弹出 3);
  • 若 ,栈中剩 1,后续元素 尚未入栈, 可取 ;
  • 若 ,栈中剩 2, 可取 ;
  • 合并后 可取除 3 以外的全部值,共 个。

正确答案:C()。

2018 第 1 题:双栈求表达式值

真题题干:

若栈 S1 中保存整数,栈 S2 中保存运算符,函数 F() 依次执行下述各步操作:① 从 S1 中依次弹出两个操作数 a 和 b;② 从 S2 中弹出一个运算符 op;③ 执行相应的运算 b op a;④ 将运算结果压入 S1。假定 S1 中的操作数依次是 5, 8, 3, 2(2 在栈顶),S2 中的运算符依次是 ×, −, +(+ 在栈顶)。调用 3 次 F() 后,S1 栈顶保存的值是( )。
A. −15 B. 15 C. −20 D. 20

考察内容:后缀表达式求值的过程,以及”弹出顺序反了会算错”这一易错点。注意题目明确 b op a,即先弹的 a 是右操作数。

解析:

次数S1(底→顶)S2(底→顶)a, bop计算 b op a结果入栈后 S1
15, 8, 3, 2×, −, +a=2, b=3+3+2=55, 8, 5
25, 8, 5×, −a=5, b=8−8−5=35, 3
35, 3×a=3, b=5×5×3=1515

正确答案:B(15)。

2020 第 2 题:给定操作序列求输出

真题题干:

对空栈 S 进行 Push 和 Pop 操作,入栈序列为 a, b, c, d, e,经过 Push, Push, Pop, Push, Pop, Push, Push, Pop 操作后得到的出栈序列是( )。
A. b,a,c B. b,a,e C. b,c,a D. b,c,e

考察内容:纯模拟,逐个操作手推栈状态。

解析:

操作栈内(底→顶)出栈元素
Pusha
Pusha b
Popab
Pusha c
Popac
Pusha d
Pusha d e
Popa de

出栈序列为 b, c, e。

正确答案:D。


扩展:更多栈模型与数学

这一节是”比较深入的地方”,不追求覆盖考纲;对栈的数学结构与工程变体感兴趣的读者可以读。

卡特兰数为什么是 个元素出栈序列的个数

用反射原理给出严格证明。把一次入栈记作向上的 、一次出栈记作向下的 ,则整个操作序列是一条从 到 、含 步上升与 步下降的路径;合法操作序列要求路径始终不低于横轴(任意时刻出栈数 ≤ 入栈数),即从不触及直线 。

  • 所有路径数为 ;
  • 由反射原理,触及 的非法路径与”从 到 、含 步上升、 步下降”的路径一一对应(把起点反射到 ),后者数为 。

于是合法数 。同一结构还出现在:括号匹配方案数、不同形态二叉树个数、凸多边形三角剖分数——它们都归约为”始终不低于横轴的格路”,属卡特兰数族。

栈排序与 312 模式

一个排列能否由”入栈 、出栈得到目标排列”产生,等价于它是否避免 312 模式:不存在下标 使 。Knuth 证明:排列是栈排序可达的当且仅当它避免 312 模式,其个数正是卡特兰数 ——与”出栈序列个数”殊途同归。

多轨道火车调度问题(Railroad / 列车编组)

问题:列车由输入轨道驶入,经过若干条旁轨(栈),要求按目标顺序驶出输出轨道,求最少需要几条旁轨。

  • 单旁轨(单栈):能得到的输出顺序正是”栈排序排列”(避免 312 模式);经典变体问”某输出顺序能否只用一条旁轨完成”。
  • 多旁轨(多栈):旁轨数对应栈的条数,问题升级为”用 个栈能否排序该排列”; 足够大时任何排列都可排。这与栈的容量/条数、递推计数有关,是栈在调度中的经典映射。
  • 工程对应:列车编组站、洗车流水线的”缓存轨道”,本质都是受限的栈/队列组合;生产-消费流水线也常用这种”输入序列 → 栈/队列 → 输出序列”的抽象。

表达式树与三种遍历

表达式除用栈求值外,还可建成表达式树:叶子是操作数,内部结点是运算符。

  • 中序遍历 → 中缀表达式(需补括号还原优先级);
  • 前序遍历 → 前缀(波兰)式;
  • 后序遍历 → 后缀(逆波兰)式。

这解释了”前缀/后缀不需要括号”:树的前/后序天然携带运算结构,而中序会丢失父子优先级信息。用栈构造表达式树再遍历求值,是编译器表达式处理的标准流程。

栈的工程变体

  • 带最小值的栈(MinStack):辅助栈或差值法(见正文);
  • 栈的池化:预分配大块内存,避免频繁 malloc(对应链栈的分配开销);
  • 调用栈的硬件化:x86 的返回栈缓冲器 RSB、影子栈(见 硬件级栈:x86-64 调用栈)。

各语言标准库对比

语言栈类型说明
C无(手写)标准库不提供容器
C++std::stack<T>适配器,默认底层 std::deque
JavaArrayDeque<T>推荐;Stack 是遗留类
Pythonlistappend() / pop()
RustVec<T>push() / pop()
Go无内置用 slice 模拟:stack = append(stack, x)

应用场景

  • 函数调用:x86-64 的硬件栈。每次函数调用(call 指令)自动 push 返回地址,返回时(ret)自动 pop。C++ 异常处理中的栈展开(stack unwinding)沿调用链逐帧 destroy 局部对象
  • 表达式求值:编译器将中缀表达式转后缀(RPN),用栈求值。计算器、SQL 查询引擎的表达式树求值均依赖此模型
  • 括号匹配:编译器/编辑器的语法验证。左括号 push,右括号时检查栈顶是否匹配。栈空但仍有右括号 = 多余右括号;结束时栈非空 = 多余左括号
  • DFS 非递归:手动用显式栈替代递归,避免系统调用栈的深度限制。详见 图的 DFS
  • 撤销(Undo):编辑器将每个编辑操作推入栈。Ctrl-Z = pop 栈顶操作并执行反向操作。Text Editor 的 Undo/Redo 用两个栈(undo stack + redo stack)
  • 浏览器的前进/后退:两个栈分别维护后退历史与前进历史。每次跳转将当前页面推入后退栈,清空前进栈

练习

LeetCode 题单

基础与括号类

题号题目难度知识点
20有效的括号简单栈匹配(见正文括号匹配节)
921使括号有效的最少添加中等计数器退化(呼应自测③)
1249移除无效的括号中等栈记录下标 + 标记删除
1021删除最外层的括号简单括号深度计数
856括号的分数中等栈 / 深度计数
32最长有效括号困难栈存下标 / DP
1190反转每对括号间的子串中等栈保存前缀
394字符串解码中等双栈(数字栈 + 字符栈)

表达式求值类

题号题目难度知识点
150逆波兰表达式求值中等后缀表达式
224基本计算器困难中缀求值 + 括号
227基本计算器 II中等优先级 + 栈
772基本计算器 III(会员)困难中缀转后缀完整版
682棒球比赛简单简单栈模拟

设计类(用栈)

题号题目难度知识点
155最小栈中等辅助栈(正文有差值法变体)
面试题 03.02栈的最小值简单同上
232用栈实现队列简单双栈摊还(与队列章成对)
225用队列实现栈简单队列模拟栈

出栈序列 / 栈模拟类(呼应考点 1–7)

题号题目难度知识点
946验证栈序列中等出栈序列合法性判定(考点 1/3)
1047删除字符串中的所有相邻重复项简单栈消消乐
1209删除字符串中的所有相邻重复项 II中等栈存 (字符, 计数)
71简化路径中等栈处理 ../.
1598文件夹操作日志搜集器简单路径栈

单调栈类

题号题目难度知识点
739每日温度中等下一个更大元素
496下一个更大元素 I简单单调栈 + 哈希
503下一个更大元素 II中等环形数组单调栈
42接雨水困难单调栈 / 双指针
84柱状图中最大的矩形困难单调栈经典
85最大矩形困难逐行转 84
316去除重复字母中等单调栈 + 贪心
402移掉 K 位数字中等单调栈 + 贪心

核心推演清单

练习题与上面的 LeetCode 互补——侧重手算推演,全部在正文中带完整答案:

自测位置内容
两栈共享 ×2 问双端栈节末top 推演、剩余容量、临界格判断
括号匹配 ×3 问括号匹配节三种失败情形识别、单括号计数器退化
中缀转后缀表达式求值节运算符栈逐步轨迹与三条弹栈规则
出栈序列合法性/计数高频考点 1、2模拟判定、卡特兰数
反推操作序列 / 求栈容量高频考点 3、4push/pop 序列、最大深度
连续退栈限制高频考点 6连续逆序子串判定
递归调用次数 / 复杂度高频考点 10、14递归树结点数、主定理、常见递归复杂度
递归 vs 迭代 / 尾递归高频考点 13、15空间差异、尾调用优化、递归转非递归
带头/不带头结点对比高频考点 16初始化、判空、入栈/出栈、清空/销毁差异
顺序栈 vs 链式栈高频考点 17判满、扩容、空间与缓存对比
清空 vs 销毁高频考点 18结构是否可用、头指针处理、复杂度

动手实验

编号题目说明
E1中缀→后缀→求值流水线手写中缀表达式 (3+4)*(5-2)/2,先后通过调度场算法转后缀和求值,验证结果。对比直接用 C 的运算符优先级计算,确认两者结果一致
E2递归深度 vs 手动栈实现深度优先遍历二叉树:(a) 递归方式,(b) 手动栈方式。对深度为 100000 的退化树(链)分别运行,记录递归的栈溢出阈值和手动栈的无限制特性
E3单调栈图形化验证随机生成长度 100 的数组 A,用单调递减栈计算每个位置的”右侧第一个更大元素”。打印 A 和结果数组,人工检查:对每个 i,A[result[i]] 确实是 i 右侧第一个 > A[i] 的元素