力扣总结 数据结构（五）：栈和队列

栈是一个后入先出的数据结构，插入和删除都在末尾进行。python 中一般直接用 list 表示。

队列是一个先入先出的数据结构，插入在末尾，删除在开头。python 中一般直接用内置库 deque 表示。

额外地，dfs 常借助栈实现，bfs 常借助队列实现，这里先不涉及。

1 基础

1.1 设计

• 0225 用队列实现栈
• 0232 用栈实现队列
• 0622 设计循环队列
• 0641 设计循环双端队列

1.2 应用

• 0071 简化路径
• 0150 逆波兰表达式求值
• 0682 棒球比赛
• 0946 验证栈序列
• 1441 用栈操作构建数组

2 进阶

2.1 设计

• 0155 最小栈
• 0341 扁平化嵌套列表迭代器
• 0895 最大频率栈
• 1381 设计一个支持增量操作的栈

2.2 应用

• 0385 迷你语法分析器
• 0394 字符串解码
• 0636 函数的独占时间
• 0735 行星碰撞
• 0880 索引处的解码字符串

3 挑战

• 0224 基本计算器
• 0227 基本计算器 II
• 0726 原子的数量
• 0770 基本计算器 IV

*4 括号系列

4.1 基础

• 0020 有效的括号
• 1021 删除最外层的括号
• 1249 移除无效的括号
• 0921 使括号有效的最少添加
• 1614 括号的最大嵌套深度

4.2 进阶

• 0032 最长有效括号
• 0301 删除无效的括号
• 0856 括号的分数
• 1111 有效括号的嵌套深度
• 1190 反转每对括号间的子串

4.3 挑战

• 0678 有效的括号字符串
• 1541 平衡括号字符串的最少插入次数