罗罗编程学习记录
本页内容 展开查看

02.3.2.1 栈基础与括号表达式求值

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.3 链表、栈与队列 / 02.3.2 栈与队列、单调栈

02.3.2.1-001 栈是什么结构?

一句话结论

栈是后进先出(LIFO)的线性结构,只在栈顶插入与删除;支持 push、pop、peek、isEmpty;数组或链表均可实现。

概念解释

  • LIFO:最后进的最先出。
  • 栈顶:唯一操作端。
  • 栈底:另一端不可直接访问。

原理流程

  1. 元素压入栈顶。
  2. 弹出取栈顶。
  3. 空栈不可弹。

代码 / 图示

栈顶 ← 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:下一个可写位置或栈顶下标,按实现约定。
  • 容量:数组长度。
  • 扩容:超容量复制。

原理流程

  1. 初始化数组与计数。
  2. push:写计数位置,计数加一。
  3. 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。
  • 操作端不同。

原理流程

  1. 看顺序需求:倒序还是顺序。
  2. 选栈或队列。
  3. 双栈可模拟队列(见队列章)。

代码 / 图示

栈: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) 空间。

概念解释

  • 栈存待匹配左括号。
  • 右括号找最近未匹配左括号。
  • 嵌套由栈处理。

原理流程

  1. 左括号 push。
  2. 右括号:栈空或类型不符返回 false;否则 pop 匹配。
  3. 结束栈空为合法。

代码 / 示例

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 括号匹配为什么用栈存字符?

一句话结论

嵌套结构要求最近未匹配的左括号先配对,栈顶正是最近左括号;后进先出与嵌套顺序一致;计数无法区分多种括号类型。

概念解释

  • 嵌套:内层先闭合。
  • 栈顶:最近左括号。
  • 类型:栈内保存左括号字符。

原理流程

  1. 左括号记录到栈。
  2. 右括号取最近记录。
  3. 类型校验。

代码 / 图示

( [ ] )
栈:( [ ;遇 ] 弹 [;遇 ) 弹 (

常见误区

  • 误区:存右括号;正解:存待匹配的左括号。
  • 误区:多括号用三个计数器;正解:交叉嵌套会误判,需类型栈。

追问

  • Q:括号顺序错乱例子? A:([)] 计数器可能过,栈判为非法。
  • Q:栈存索引可以吗? A:可以,需定位位置时存下标。

02.3.2.1-006 括号题有哪些边界用例?

一句话结论

空串、单字符、纯左括号、纯右括号、交错嵌套 ([)]、同类型嵌套、字符含其他符号;验证栈空判断与收尾检查。

概念解释

  • 空与最短。
  • 单侧括号。
  • 交叉错误。

原理流程

  1. 空串返回合法口径。
  2. 单侧走查栈残留/栈空。
  3. 交叉用例验证类型匹配。

代码 / 图示

"" / "(" / ")"
"([)]" 非法
"({[]})" 合法

常见误区

  • 误区:默认输入只含括号;正解:按题目确认其他字符处理。
  • 误区:左右数量相等就合法;正解:顺序与类型也要合法。

追问

  • Q:长度奇数? A:必不匹配,可提前返回。
  • Q:括号深度超限? A:按题目约束,栈空间随深度增长。

02.3.2.1-007 逆波兰表达式求值(LC 150)怎么做?

一句话结论

后缀表达式:数字入栈,遇运算符弹出两个操作数计算,结果压栈;注意减法/除法顺序:先弹为右操作数;O(n) 时间 O(n) 空间。

概念解释

  • 后缀:操作数在前,运算符在后。
  • 栈存操作数。
  • 二元运算取两栈顶。

原理流程

  1. 遍历 token。
  2. 数字压栈。
  3. 运算符弹 b、a,计算 a op b 压栈。
  4. 栈底为结果。

代码 / 示例

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 中缀表达式怎么转后缀?

一句话结论

运算符栈维护优先级:数字直接输出;遇运算符弹出栈顶优先级不低于当前的再入栈;左括号压栈,右括号弹到左括号;是栈在语法解析中的经典应用。

概念解释

  • 优先级:先乘除后加减。
  • 栈存待处理运算符。
  • 括号重置优先级。

原理流程

  1. 数字输出。
  2. 运算符按优先级弹出。
  3. 括号配对弹栈。

代码 / 图示

a + b * c
后缀:a b c * +

常见误区

  • 误区:同级运算符不弹出;正解:左结合同级先弹。
  • 误区:左括号也参与比较;正解:左括号在栈内优先级最低。

追问

  • Q:结合性影响什么? A:右结合需调整弹出条件。
  • Q:转后缀后求值? A:逆波兰求值法。

02.3.2.1-009 基本计算器(LC 224)思路是什么?

一句话结论

单栈或双栈处理括号与符号:数字按当前符号累加到结果,遇括号压栈保存当前结果与符号,括号内递归/弹栈恢复;处理加减与括号;O(n) 时间 O(n) 空间。

概念解释

  • 括号改变优先级。
  • 栈保存括号外状态。
  • 符号跟随数字。

原理流程

  1. 扫描字符,拼数字。
  2. 按符号更新当前结果。
  3. 遇括号压栈状态,开始子表达式。
  4. 闭括号弹栈合并。

代码 / 图示

栈内:外层结果、括号前符号
子表达式算完按符号合并回外层

常见误区

  • 误区:负数与前置符号处理遗漏;正解:记录当前 sign。
  • 误区:括号内结果未按括号前符号合并;正解:弹栈带符号。

追问

  • Q:含乘除的计算器? A:另需优先级处理,见后缀转换思路。
  • Q:递归写法? A:遇括号递归求值子表达式。

02.3.2.1-010 字符串解码(LC 394)怎么做?

一句话结论

双栈:数字栈存重复次数,字符串栈存当前前缀;遇数字解析倍数,遇字母拼接当前串,遇 [ 压栈保存,遇 ] 弹出次数与前缀拼接;O(n) 时间 O(n) 空间。

概念解释

  • 嵌套:[ 保存外层状态。
  • 数字:重复倍数。
  • 闭括号:展开当前段并接回前缀。

原理流程

  1. 数字累积 k。
  2. [:压当前串与 k,重置当前串。
  3. 字母拼接。
  4. ]:弹前缀,重复当前串接回。

代码 / 示例

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。

概念解释

  • 调用栈:编译器/运行时维护。
  • 栈帧:每层递归状态。
  • 手写栈:显式保存待处理状态。

原理流程

  1. 递归深入压栈。
  2. 返回时弹栈恢复。
  3. 迭代版用显式栈模拟。

代码 / 图示

递归 f(n) → f(n-1) → …
调用栈:栈顶为当前层

常见误区

  • 误区:递归不需要栈空间;正解:调用栈 O(深度)。
  • 误区:手写栈一定比递归快;正解:主要区别是可控栈与避免溢出。

追问

  • Q:递归深度过大怎么办? A:显式栈迭代或尾递归改造。
  • Q:栈帧存什么? A:参数、局部变量、返回地址。

02.3.2.1-012 怎么用栈实现 DFS?

一句话结论

显式栈保存待访问节点;弹出节点访问,未访问邻接点压栈;与递归 DFS 等价;注意标记访问时机,避免重复入栈;O(n) 时间 O(n) 栈空间。

概念解释

  • 栈:待访问节点。
  • 弹出处理。
  • 邻接点入栈。

原理流程

  1. 起点压栈并标记。
  2. 弹出处理。
  3. 邻接未访问点压栈标记。

代码 / 示例

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 栈存值与存索引分别用在什么题?

一句话结论

括号/表达式栈存字符或数值;单调栈、子数组统计存索引,便于按位置计算距离与宽度;按需要计算的量决定存什么。

概念解释

  • 存值:匹配类型、操作数。
  • 存索引:位置差、跨度。
  • 索引对应原数组位置。

原理流程

  1. 判断结果需要值还是位置。
  2. 选栈元素类型。
  3. 弹出时按类型计算。

代码 / 图示

括号:栈存 '(' '['
单调栈:栈存下标 i

常见误区

  • 误区:单调栈存值丢位置;正解:宽度计算必须索引。
  • 误区:表达式栈存索引;正解:求值需要数值。

追问

  • Q:索引栈怎么取值? A:arr[stack.peek()]。
  • Q:可以存索引附带值吗? A:可以,封装成对。

02.3.2.1-014 单调栈是什么,和普通栈什么关系?

一句话结论

单调栈是栈内元素保持单调递增或递减的用法:入栈前弹出破坏单调性的栈顶元素;用于求下一个更大/更小元素;是栈的典型应用模式。

概念解释

  • 单调性:递增或递减。
  • 弹栈:维护顺序。
  • 典型:右侧最近更大。

原理流程

  1. 元素入栈前比较栈顶。
  2. 破坏单调则弹出并结算。
  3. 当前元素入栈。

代码 / 图示

递减栈:栈顶 ≥ 栈内
新元素比栈顶大 → 弹栈结算

常见误区

  • 误区:单调栈入栈后再排序;正解:入栈过程中即时弹栈维护。
  • 误区:单调栈只能存值;正解:通常存索引。

追问

  • Q:详细题型在哪? A:见 02.3.2.2 单调栈与柱状图、接雨水。
  • Q:单调栈复杂度? A:每个元素入栈出栈各一次,O(n)。

02.3.2.1-015 栈的空间复杂度怎么算?

一句话结论

栈空间随同时存在的元素增长:括号/表达式 O(n) 最坏深度 n;DFS 最坏 O(n);均为压入元素数 × 单元素大小;递归栈同理。

概念解释

  • 同时在栈内:最大深度。
  • 单元素:字符/数值/节点引用。
  • 最坏口径。

原理流程

  1. 估算最大压栈深度。
  2. 单层常数空间。
  3. 深度 × 常数。

代码 / 图示

括号嵌套深 n:O(n)
DFS 链状:O(n)

常见误区

  • 误区:栈空间按总输入;正解:按最大同时在栈内。
  • 误区:递归不计栈空间;正解:调用栈占内存。

追问

  • Q:括号浅嵌套空间? A:O(深度),深度小则空间低。
  • Q:能否 O(1) 栈空间? A:单种括号计数可,多括号与嵌套表达式通常不行。

02.3.2.1-016 表达式求值中运算符优先级怎么处理?

一句话结论

后缀转换或双栈法:优先级高的运算符先结合;栈内优先级不低于当前则弹出计算;括号提升内部优先级;乘除高于加减。

概念解释

  • 优先级:乘除 > 加减。
  • 结合性:同级左结合。
  • 括号:子表达式先算。

原理流程

  1. 扫描操作数入数栈。
  2. 运算符按优先级比较栈内。
  3. 高优先级先弹算。

代码 / 图示

a + b * c:* 先算
(a + b) * c:括号内先算

常见误区

  • 误区:从左到右无脑算;正解:优先级与括号决定顺序。
  • 误区:同级右结合;正解:加减乘除左结合。

追问

  • Q:双栈结构? A:数栈 + 运算符栈。
  • Q:一元负号? A:需特殊标记符号位。

02.3.2.1-017 括号嵌套深度怎么求?

一句话结论

扫描遇左括号深度加一,遇右括号减一,记录过程最大值;栈大小即当前深度;O(n) 时间 O(1) 计数(单类括号)。

概念解释

  • 深度:当前未闭合左括号数。
  • 最大值:嵌套层数峰值。
  • 单类括号可用计数。

原理流程

  1. 深度 0,最大 0。
  2. 左括号加一并更新最大。
  3. 右括号减一。

代码 / 示例

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、单元素压弹、连续压栈扩容、表达式单操作数、括号空串与嵌套闭合;验证判空与扩容不越界。

概念解释

  • 空操作:栈空保护。
  • 最短栈:一元素。
  • 扩容边界:容量临界。

原理流程

  1. 空栈调用弹取。
  2. 单元素往返。
  3. 容量临界压入。

代码 / 图示

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。

原理流程

  1. 声明 Deque<E> st = new ArrayDeque<>()。
  2. push/pop/peek。
  3. 判空 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) 空间。

原理流程

  1. 统计扫描轮次。
  2. 标注最大栈深。
  3. 区分栈存类型。

代码 / 图示

括号匹配: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:改迭代或限制深度。