【真题算法·第十六期】栈

📖 知识点详解

01 什么是栈？

栈（Stack）是一种只允许在一端（栈顶）进行插入和删除的线性表，核心特性是先进后出（LIFO, Last In First Out）——最后压入的元素最先弹出。

像一摞盘子，只能从最上面取放；因此"先入栈的元素一定后出栈"是判断任何出栈序列是否合法的根本依据。

核心思想：所有操作都发生在栈顶一端，先进后出（LIFO）

02 栈的核心操作 / 代码模板

栈的基本操作只有四个：入栈（push）、出栈（pop）、取栈顶（top）、判空。

Python 中用列表模拟栈有两种写法：

# 写法一：直接用列表（append / pop 隐式栈顶）

stk = []

stk.append(x) # 入栈 push

x = stk.pop() # 出栈 pop（同时返回栈顶元素）

top = stk[-1] # 取栈顶（不出栈）

if not stk: # 判空

...

# 写法二：列表 + top 指针（定长，真题常用）

stk = [0] * N

top = -1 # 栈空时 top = -1

# 入栈

top += 1; stk[top] = x

# 出栈

x = stk[top]; top -= 1

# 判空 / 判满

if top == -1: ... # 空

if top == N - 1: ... # 满

⚠️注意："写法二"中列表stk本身只是一块“预留好的空间”，里面不一定全是栈里的元素。真正属于栈的，是下标0到top这一段，top 就像一个“游标”或“指针”，它标记了当前栈顶的位置。入栈时，我们把游标后移，把值写到游标的位置；出栈时，游标前移，原来的值还在列表里，但我们已经“看不见”它了。

两种写法的核心差异

第一种：栈和容器是一体的，容器大小随操作动态变化，元素真实存在或消失。底层其实是动态数组（也是一种数据结构）。

第二种：栈是“容器中的一段区间”，由指针划定边界，容器本身固定不变，指针之内的才是栈，指针之外的空间只是“荒地”或“遗迹”。第二种写法更接近“抽象”的本质。

栈在“逻辑层面”是一种抽象数据类型（ADT），它定义了后进先出的规则；在“物理实现层面”，我们可以选用数组或链表等具体的数据结构去构建它。

因此，数据结构的学习，理解和区分逻辑结构和存储结构是关键，逻辑结构是“不变的核心”，存储结构是“多变的实现”。其他数据结构学习也是同样。

03 常见模式 / 变式

模式一：出入栈合法性判断（容量受限）

考查概念和理解：给定入栈顺序和栈的最大容量，判断哪些出栈序列可能出现。关键是：栈中"同时存在的元素个数（栈深）"不能超过容量上限，否则该序列不可能。（见 202306-Q09）

# 思路：模拟出入栈，任一时刻栈深 = 已入栈数 - 已出栈数，须 ≤ 容量

模式二：栈模拟过程

考查概念和理解：1.程序按随机或条件决定入栈/出栈，需要推理哪些最终结果不可能出现。根本依据仍是"先入栈的元素后出栈"：若某元素已出栈，则它之前入栈且还在栈中的元素必在其之前出栈。（见 202301-Q12）。2.出栈序列计数：固定入栈顺序、要求栈最终为空时，统计以某元素结尾的合法出栈序列个数，本质是"全排列 + 栈约束筛选"（卡特兰数思想），不要漏排或多算。（见 202406-Q09）

模式三：栈的经典应用——后缀表达式求值（逆波兰式）

考查应用：从左向右扫描，遇数字入栈；遇运算符则弹出两个元素计算、结果入栈。注意：先弹出的是右操作数，后弹出的是左操作数，运算应保持"左数运算符右数"的顺序。（见 202501-Q08）

模式四：栈与队列综合考查栈和队列应用：栈与队列配合：如"出栈后入队（U）""出队后再入队（H）"，需分别按栈 LIFO、队列 FIFO 跟踪元素流向。（见 202401-Q08）

04 栈 vs 队列

真题 🧪 真题举例

【2023年01月·第12题】

来源：[[202301-Q12-栈-数组操作-循环分支]]

有如下Python程序段：

import random

a= ['A', 'B', '#', '#', 'C', 'D', '#']

stk = [0] * len(a); top = -1

for i in range(len(a)) :

op = random.randint(0, 1) #随机生成0或1

if op == 1 and a[i] != '#' :

top += 1; stk[top] = a[i]

a[i] = '#'

elif op == 0 and top != -1 and a[i] == '#' :

a[i] = stk[top]; top -= 1

执行该程序段后,a的值不可能的是( )A. ['A','B','#','#','C','D','#'] B. ['#','#','#','#','#','#','#']C. ['#','B','#','#','C','D','A'] D. ['#','#','A','B','C','D','#']

解析 📝 解析

本题考查栈的运用。列表a：本题对a中的元素进行遍历操作。列表stk：用于模拟栈。变量top：栈顶指针。变量op：是随机的0或1，出栈/入栈的条件之一。①当op为1且a[i]值不为“#”时（为字母），将##a[i]##中字母入栈并将其值变为“#”；②op为0且栈不为空且a[i]值为“#”时，出栈并将值赋给##a[i]##。##选项A正确：当op的值每次都是0时即可实现；选项B正确：当op的值每次都是1时即可实现；选项C正确：当op的值依次时1、0、1、1、0、0、0时即可实现。选项D错误：##a[0]##、##a[1]##值是“#”，表明“A”、“B”均已入栈，则出栈顺序一定是“B”、“A”，故选项中a[2]、a[3]值为“A”、“B”不可能。

【2023年06月·第09题】

来源：[[202306-Q09-栈]]

栈s最大长度为3，初始为空，经过一系列入栈、出栈操作，若元素入栈的顺序是a，b，c，d，e，f，则可能的出栈序列为A. f，e，d，c，b，a B. c，b，a，f，e，d

C. c，a，b，d，e，f D. c，e，d，b，a，f

解析 📝 解析

本题考查栈的基本操作。栈是先进后出，题干中限定条件栈s的最大长度为3，初始为空。选项A错误：f最先出栈，说明a，b，c，d，e，f需要全部入栈后，f才能出栈，但这种情况下栈长度需要为6，不符合题意。选项B正确：c最先出栈，此时a，b，c入栈，接着c，b，a依次出栈，此时栈s内为空，接下来f出栈，说明d，e，f需要入栈，接着f，e，d出栈，过程中栈内长度符合题意。选项C错误：c最先出栈，此时a，b，c入栈，接着c出栈，此时栈内a，b，由于b是栈顶元素，所以接下来出栈元素不可能是a。选项D错误：c最先出栈，此时a，b，c入栈，接着c出栈，此时栈内a，b，接下来e出栈，需要d，e入栈，此时栈内a，b，d，e，栈长度为4，不符合题意。

【2024年01月·第08题】

来源：[[202401-Q08-栈-队列]]

S从栈底到栈顶的元素依次为1，2，3，队列Q初始为空。约定: U 操作是指元素出栈后入队，H操作是指元素出队后再入队。经过UUHU系列操作后，队列中队首到队尾的元素依次为A. 2,1,3 B. 3,1,2 C. 1,3,2 D. 2,3,1

解析 📝 解析

本题考查队列的入队、出队操作及栈的出栈操作。模拟可得，队列内元素为：2,3,1。故答案选D。

【2024年06月·第09题】

来源：[[202406-Q09-栈]]

栈初始为空，经过一系列入栈、出栈操作后，栈又为空。若元素入栈的顺序为“生”“旦”“净”“末”“丑”，则所有可能的出栈序列中，以“旦”结尾的序列个数为

A. 3 B. 4 C. 5 D. 6

解析 📝 解析

本题考查数据结构栈的操作。根据栈的操作（先进后出）的特点，要以“旦”结尾，“生”一定是第一个出栈。那么所有可能的出栈序列中，一头一尾的元素就已经确定了，剩下三个元素的全排列数是6，写出所有的出栈序列如下：第一种出栈情况：生、净、末、丑、旦第二种出栈情况：生、末、丑、净、旦第三种出栈情况：生、丑、末、净、旦第四种出栈情况：生、末、净、丑、旦第五种出栈情况：生、净、丑、末、旦第六种出栈情况：生、丑、净、末、旦根据栈的特点，其中第六种出栈情况“生、丑、净、末、旦”是不可能的，所以一共有五种可能，选C。

【2025年01月·第08题】

来源：[[202501-Q08-栈]]

有后缀表达式“1 3 + 2 * 3 +2 *”，现利用栈计算该表达式：从左向右扫描，遇到数字时，数字入栈；遇到运算符时，两个元素出栈，用运算符计算，所得结果入栈，如此反复操作，直到扫描结束，栈顶元素是

A. 21 B. 22 C. 23 D. 24