02.3.2.1 栈基础与括号表达式求值
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.3 链表、栈与队列 / 02.3.2 栈与队列、单调栈
02.3.2.1-001 栈是什么结构?
一句话结论
栈是后进先出(LIFO)的线性结构,只在栈顶插入与删除;支持 push、pop、peek、isEmpty;数组或链表均可实现。
概念解释
- LIFO:最后进的最先出。
- 栈顶:唯一操作端。
- 栈底:另一端不可直接访问。
原理流程
- 元素压入栈顶。
- 弹出取栈顶。
- 空栈不可弹。
代码 / 图示
栈顶 ← 3
2
1 ← 栈底
push(4) → 栈顶 4
pop → 4
常见误区
- 误区:栈可以访问中间元素;正解:只暴露栈顶。
- 误区:栈是队列反向;正解:栈 LIFO,队列 FIFO。
追问
- Q:栈用数组还是链表实现? A:都可,数组扩容均摊 O(1),链表节点开销大。
- Q:栈满怎么办? A:动态数组扩容,或题目规定容量时报错。
02.3.2.1-002 栈的数组实现怎么做?
一句话结论
数组 + top 指针(下标或计数);push 写 top 位置后移,pop 前移返回;扩容时整体拷贝;均摊 O(1) 增删。
概念解释
- top:下一个可写位置或栈顶下标,按实现约定。
- 容量:数组长度。
- 扩容:超容量复制。
原理流程
- 初始化数组与计数。
- push:写计数位置,计数加一。
- pop:计数减一返回值。
代码 / 示例
class ArrayStack {
private int[] data = new int[8];
private int top = 0; // 元素个数
public void push(int v) {
if (top == data.length) data = Arrays.copyOf(data, data.length * 2);
data[top++] = v;
}
public int pop() { return data[--top]; }
public int peek() { return data[top - 1]; }
public boolean isEmpty() { return top == 0; }
}
常见误区
- 误区:top 语义混用;正解:明确是元素个数还是栈顶下标。
- 误区:空栈 pop;正解:先判空。
追问
- Q:扩容均摊复杂度? A:均摊 O(1),单次扩容 O(n)。
- Q:缩容时机? A:可在使用率过低时缩容,避免空间浪费。
02.3.2.1-003 栈与队列有什么区别?
一句话结论
栈 LIFO,只操作栈顶;队列 FIFO,队尾入队头出;两者分别适配回溯型与顺序型场景。
概念解释
- 栈:后入先出,回溯、嵌套。
- 队列:先入先出,排队、BFS。
- 操作端不同。
原理流程
- 看顺序需求:倒序还是顺序。
- 选栈或队列。
- 双栈可模拟队列(见队列章)。
代码 / 图示
栈:a b c → c b a 出
队列:a b c → a b c 出
常见误区
- 误区:栈和队列都能遍历;正解:受限结构,遍历需导出或内部数组。
- 误区:递归底层是队列;正解:递归调用栈是栈。
追问
- Q:两个栈实现队列? A:入队栈 + 出队栈,见 02.3.2.3。
- Q:两个队列实现栈? A:一个队列转存,弹出最后元素。
02.3.2.1-004 有效括号(LC 20)怎么判断?
一句话结论
左括号压栈,右括号弹出栈顶匹配;栈空遇右括号、类型不匹配即非法;遍历完栈必须为空;O(n) 时间 O(n) 空间。
概念解释
- 栈存待匹配左括号。
- 右括号找最近未匹配左括号。
- 嵌套由栈处理。
原理流程
- 左括号 push。
- 右括号:栈空或类型不符返回 false;否则 pop 匹配。
- 结束栈空为合法。
代码 / 示例
public boolean isValid(String s) {
Deque<Character> st = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') st.push(c);
else {
if (st.isEmpty()) return false;
char t = st.pop();
if (c == ')' && t != '(') return false;
if (c == ']' && t != '[') return false;
if (c == '}' && t != '{') return false;
}
}
return st.isEmpty();
}
常见误区
- 误区:右括号栈空仍继续;正解:直接非法。
- 误区:遍历完未检查栈空;正解:残留左括号非法。
追问
- Q:只用计数行不行? A:单种括号可行,多种括号必须栈匹配类型。
- Q:空串合法吗? A:按题目通常合法。
02.3.2.1-005 括号匹配为什么用栈存字符?
一句话结论
嵌套结构要求最近未匹配的左括号先配对,栈顶正是最近左括号;后进先出与嵌套顺序一致;计数无法区分多种括号类型。
概念解释
- 嵌套:内层先闭合。
- 栈顶:最近左括号。
- 类型:栈内保存左括号字符。
原理流程
- 左括号记录到栈。
- 右括号取最近记录。
- 类型校验。
代码 / 图示
( [ ] )
栈:( [ ;遇 ] 弹 [;遇 ) 弹 (
常见误区
- 误区:存右括号;正解:存待匹配的左括号。
- 误区:多括号用三个计数器;正解:交叉嵌套会误判,需类型栈。
追问
- Q:括号顺序错乱例子? A:
([)]计数器可能过,栈判为非法。 - Q:栈存索引可以吗? A:可以,需定位位置时存下标。
02.3.2.1-006 括号题有哪些边界用例?
一句话结论
空串、单字符、纯左括号、纯右括号、交错嵌套 ([)]、同类型嵌套、字符含其他符号;验证栈空判断与收尾检查。
概念解释
- 空与最短。
- 单侧括号。
- 交叉错误。
原理流程
- 空串返回合法口径。
- 单侧走查栈残留/栈空。
- 交叉用例验证类型匹配。
代码 / 图示
"" / "(" / ")"
"([)]" 非法
"({[]})" 合法
常见误区
- 误区:默认输入只含括号;正解:按题目确认其他字符处理。
- 误区:左右数量相等就合法;正解:顺序与类型也要合法。
追问
- Q:长度奇数? A:必不匹配,可提前返回。
- Q:括号深度超限? A:按题目约束,栈空间随深度增长。
02.3.2.1-007 逆波兰表达式求值(LC 150)怎么做?
一句话结论
后缀表达式:数字入栈,遇运算符弹出两个操作数计算,结果压栈;注意减法/除法顺序:先弹为右操作数;O(n) 时间 O(n) 空间。
概念解释
- 后缀:操作数在前,运算符在后。
- 栈存操作数。
- 二元运算取两栈顶。
原理流程
- 遍历 token。
- 数字压栈。
- 运算符弹 b、a,计算 a op b 压栈。
- 栈底为结果。
代码 / 示例
public int evalRPN(String[] tokens) {
Deque<Integer> st = new ArrayDeque<>();
for (String t : tokens) {
if (t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/")) {
int b = st.pop(), a = st.pop();
switch (t) {
case "+": st.push(a + b); break;
case "-": st.push(a - b); break;
case "*": st.push(a * b); break;
default: st.push(a / b);
}
} else {
st.push(Integer.parseInt(t));
}
}
return st.pop();
}
常见误区
- 误区:减法除法顺序颠倒;正解:先弹是右操作数 b。
- 误区:单目运算符处理;正解:题目通常二元运算。
追问
- Q:除法向哪取整? A:按题目口径,Java 整数除法向零截断。
- Q:非法表达式? A:按题目保证合法,否则需校验栈大小。
02.3.2.1-008 中缀表达式怎么转后缀?
一句话结论
运算符栈维护优先级:数字直接输出;遇运算符弹出栈顶优先级不低于当前的再入栈;左括号压栈,右括号弹到左括号;是栈在语法解析中的经典应用。
概念解释
- 优先级:先乘除后加减。
- 栈存待处理运算符。
- 括号重置优先级。
原理流程
- 数字输出。
- 运算符按优先级弹出。
- 括号配对弹栈。
代码 / 图示
a + b * c
后缀:a b c * +
常见误区
- 误区:同级运算符不弹出;正解:左结合同级先弹。
- 误区:左括号也参与比较;正解:左括号在栈内优先级最低。
追问
- Q:结合性影响什么? A:右结合需调整弹出条件。
- Q:转后缀后求值? A:逆波兰求值法。
02.3.2.1-009 基本计算器(LC 224)思路是什么?
一句话结论
单栈或双栈处理括号与符号:数字按当前符号累加到结果,遇括号压栈保存当前结果与符号,括号内递归/弹栈恢复;处理加减与括号;O(n) 时间 O(n) 空间。
概念解释
- 括号改变优先级。
- 栈保存括号外状态。
- 符号跟随数字。
原理流程
- 扫描字符,拼数字。
- 按符号更新当前结果。
- 遇括号压栈状态,开始子表达式。
- 闭括号弹栈合并。
代码 / 图示
栈内:外层结果、括号前符号
子表达式算完按符号合并回外层
常见误区
- 误区:负数与前置符号处理遗漏;正解:记录当前 sign。
- 误区:括号内结果未按括号前符号合并;正解:弹栈带符号。
追问
- Q:含乘除的计算器? A:另需优先级处理,见后缀转换思路。
- Q:递归写法? A:遇括号递归求值子表达式。
02.3.2.1-010 字符串解码(LC 394)怎么做?
一句话结论
双栈:数字栈存重复次数,字符串栈存当前前缀;遇数字解析倍数,遇字母拼接当前串,遇 [ 压栈保存,遇 ] 弹出次数与前缀拼接;O(n) 时间 O(n) 空间。
概念解释
- 嵌套:
[保存外层状态。 - 数字:重复倍数。
- 闭括号:展开当前段并接回前缀。
原理流程
- 数字累积 k。
[:压当前串与 k,重置当前串。- 字母拼接。
]:弹前缀,重复当前串接回。
代码 / 示例
public String decodeString(String s) {
Deque<Integer> numStack = new ArrayDeque<>();
Deque<String> strStack = new ArrayDeque<>();
StringBuilder cur = new StringBuilder();
int k = 0;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) k = k * 10 + c - '0';
else if (c == '[') {
numStack.push(k); strStack.push(cur.toString());
k = 0; cur = new StringBuilder();
} else if (c == ']') {
int times = numStack.pop();
StringBuilder prev = new StringBuilder(strStack.pop());
for (int i = 0; i < times; i++) prev.append(cur);
cur = prev;
} else cur.append(c);
}
return cur.toString();
}
常见误区
- 误区:多位数按单字符处理;正解:逐位累积 k。
- 误区:闭括号未拼回外层前缀;正解:弹栈恢复前缀再接重复段。
追问
- Q:嵌套层数深? A:栈空间 O(嵌套深度)。
- Q:重复次数为 0? A:按题目口径,通常正整数。
02.3.2.1-011 递归调用栈和数据结构栈是什么关系?
一句话结论
函数递归时系统用调用栈保存栈帧(返回地址、局部变量);手写栈可以把递归改写成迭代,栈内容对应递归状态;两者都是 LIFO。
概念解释
- 调用栈:编译器/运行时维护。
- 栈帧:每层递归状态。
- 手写栈:显式保存待处理状态。
原理流程
- 递归深入压栈。
- 返回时弹栈恢复。
- 迭代版用显式栈模拟。
代码 / 图示
递归 f(n) → f(n-1) → …
调用栈:栈顶为当前层
常见误区
- 误区:递归不需要栈空间;正解:调用栈 O(深度)。
- 误区:手写栈一定比递归快;正解:主要区别是可控栈与避免溢出。
追问
- Q:递归深度过大怎么办? A:显式栈迭代或尾递归改造。
- Q:栈帧存什么? A:参数、局部变量、返回地址。
02.3.2.1-012 怎么用栈实现 DFS?
一句话结论
显式栈保存待访问节点;弹出节点访问,未访问邻接点压栈;与递归 DFS 等价;注意标记访问时机,避免重复入栈;O(n) 时间 O(n) 栈空间。
概念解释
- 栈:待访问节点。
- 弹出处理。
- 邻接点入栈。
原理流程
- 起点压栈并标记。
- 弹出处理。
- 邻接未访问点压栈标记。
代码 / 示例
Deque<Node> st = new ArrayDeque<>();
st.push(start);
Set<Node> visited = new HashSet<>();
visited.add(start);
while (!st.isEmpty()) {
Node cur = st.pop();
for (Node next : cur.neighbors()) {
if (visited.add(next)) st.push(next);
}
}
常见误区
- 误区:弹出时才标记;正解:入栈即标记,避免重复入栈。
- 误区:栈 DFS 与递归顺序一致;正解:邻接压栈顺序影响访问顺序。
追问
- Q:BFS 用什么? A:队列。
- Q:DFS 栈空间最坏多少? A:O(n),链状结构。
02.3.2.1-013 栈存值与存索引分别用在什么题?
一句话结论
括号/表达式栈存字符或数值;单调栈、子数组统计存索引,便于按位置计算距离与宽度;按需要计算的量决定存什么。
概念解释
- 存值:匹配类型、操作数。
- 存索引:位置差、跨度。
- 索引对应原数组位置。
原理流程
- 判断结果需要值还是位置。
- 选栈元素类型。
- 弹出时按类型计算。
代码 / 图示
括号:栈存 '(' '['
单调栈:栈存下标 i
常见误区
- 误区:单调栈存值丢位置;正解:宽度计算必须索引。
- 误区:表达式栈存索引;正解:求值需要数值。
追问
- Q:索引栈怎么取值? A:arr[stack.peek()]。
- Q:可以存索引附带值吗? A:可以,封装成对。
02.3.2.1-014 单调栈是什么,和普通栈什么关系?
一句话结论
单调栈是栈内元素保持单调递增或递减的用法:入栈前弹出破坏单调性的栈顶元素;用于求下一个更大/更小元素;是栈的典型应用模式。
概念解释
- 单调性:递增或递减。
- 弹栈:维护顺序。
- 典型:右侧最近更大。
原理流程
- 元素入栈前比较栈顶。
- 破坏单调则弹出并结算。
- 当前元素入栈。
代码 / 图示
递减栈:栈顶 ≥ 栈内
新元素比栈顶大 → 弹栈结算
常见误区
- 误区:单调栈入栈后再排序;正解:入栈过程中即时弹栈维护。
- 误区:单调栈只能存值;正解:通常存索引。
追问
- Q:详细题型在哪? A:见 02.3.2.2 单调栈与柱状图、接雨水。
- Q:单调栈复杂度? A:每个元素入栈出栈各一次,O(n)。
02.3.2.1-015 栈的空间复杂度怎么算?
一句话结论
栈空间随同时存在的元素增长:括号/表达式 O(n) 最坏深度 n;DFS 最坏 O(n);均为压入元素数 × 单元素大小;递归栈同理。
概念解释
- 同时在栈内:最大深度。
- 单元素:字符/数值/节点引用。
- 最坏口径。
原理流程
- 估算最大压栈深度。
- 单层常数空间。
- 深度 × 常数。
代码 / 图示
括号嵌套深 n:O(n)
DFS 链状:O(n)
常见误区
- 误区:栈空间按总输入;正解:按最大同时在栈内。
- 误区:递归不计栈空间;正解:调用栈占内存。
追问
- Q:括号浅嵌套空间? A:O(深度),深度小则空间低。
- Q:能否 O(1) 栈空间? A:单种括号计数可,多括号与嵌套表达式通常不行。
02.3.2.1-016 表达式求值中运算符优先级怎么处理?
一句话结论
后缀转换或双栈法:优先级高的运算符先结合;栈内优先级不低于当前则弹出计算;括号提升内部优先级;乘除高于加减。
概念解释
- 优先级:乘除 > 加减。
- 结合性:同级左结合。
- 括号:子表达式先算。
原理流程
- 扫描操作数入数栈。
- 运算符按优先级比较栈内。
- 高优先级先弹算。
代码 / 图示
a + b * c:* 先算
(a + b) * c:括号内先算
常见误区
- 误区:从左到右无脑算;正解:优先级与括号决定顺序。
- 误区:同级右结合;正解:加减乘除左结合。
追问
- Q:双栈结构? A:数栈 + 运算符栈。
- Q:一元负号? A:需特殊标记符号位。
02.3.2.1-017 括号嵌套深度怎么求?
一句话结论
扫描遇左括号深度加一,遇右括号减一,记录过程最大值;栈大小即当前深度;O(n) 时间 O(1) 计数(单类括号)。
概念解释
- 深度:当前未闭合左括号数。
- 最大值:嵌套层数峰值。
- 单类括号可用计数。
原理流程
- 深度 0,最大 0。
- 左括号加一并更新最大。
- 右括号减一。
代码 / 示例
int maxDepth = 0, cur = 0;
for (char c : s.toCharArray()) {
if (c == '(') { cur++; maxDepth = Math.max(maxDepth, cur); }
else if (c == ')') cur--;
}
常见误区
- 误区:右括号不减少;正解:闭合后深度回退。
- 误区:多类括号混用计数;正解:类型交叉需栈。
追问
- Q:非法括号能求深度吗? A:先判合法再求,负深度需处理。
- Q:深度对应什么? A:递归层级或栈最大规模。
02.3.2.1-018 栈操作有哪些边界用例?
一句话结论
空栈 pop/peek、单元素压弹、连续压栈扩容、表达式单操作数、括号空串与嵌套闭合;验证判空与扩容不越界。
概念解释
- 空操作:栈空保护。
- 最短栈:一元素。
- 扩容边界:容量临界。
原理流程
- 空栈调用弹取。
- 单元素往返。
- 容量临界压入。
代码 / 图示
pop 空栈
push 到容量上限
表达式:单数字
括号:空 / 一对
常见误区
- 误区:空栈 pop 抛异常未处理;正解:实现先判空。
- 误区:扩容后旧引用丢失;正解:复制到新数组再赋引用。
追问
- Q:peek 空栈返回什么? A:按实现抛异常或返回空。
- Q:容量固定栈满怎么办? A:拒绝压入或扩容,按设计口径。
02.3.2.1-019 Java 中栈用什么类实现?
一句话结论
推荐 Deque(如 ArrayDeque)作为栈:push/pop/peek 语义明确;java.util.Stack 继承 Vector,历史遗留,不推荐新代码使用。
概念解释
- Deque:双端队列,可作栈。
- Stack:老式类,线程安全但冗余。
- 选型:接口 Deque。
原理流程
- 声明
Deque<E> st = new ArrayDeque<>()。 - push/pop/peek。
- 判空 isEmpty。
代码 / 示例
Deque<Character> st = new ArrayDeque<>();
st.push('(');
st.pop();
st.peek();
常见误区
- 误区:用
Stack就是标准做法;正解:Deque 更现代。 - 误区:Deque 当栈用 add/get;正解:用 push/pop/peek 栈语义。
追问
- Q:ArrayDeque 支持 null 吗? A:不允许存入 null,按实现口径。
- Q:线程安全栈? A:需外部加锁或使用同步包装。
02.3.2.1-020 栈类题复杂度怎么汇报?
一句话结论
括号/表达式/解码线性扫描 O(n),栈空间 O(n)(最坏深度 n);每个字符入栈出栈各一次;递归 DFS O(n) 时间 O(n) 栈;单类括号深度统计可 O(1) 空间。
概念解释
- 线性扫描:每字符常数处理。
- 栈深:最坏嵌套深度。
- 计数特例:O(1) 空间。
原理流程
- 统计扫描轮次。
- 标注最大栈深。
- 区分栈存类型。
代码 / 图示
括号匹配:O(n) / O(n)
逆波兰:O(n) / O(n)
深度统计:O(n) / O(1)
DFS:O(n) / O(n)
常见误区
- 误区:表达式求值 O(n²);正解:每运算符常数次弹栈,线性。
- 误区:解码结果串长不计空间;正解:输出本身占空间,辅助栈按嵌套深度。
追问
- Q:什么题栈空间能降到 O(1)? A:单类括号计数、部分消消乐式配对。
- Q:嵌套极深栈溢出怎么办? A:改迭代或限制深度。