5、栈
堆栈是一种单端线性数据结构，它通过执行两个主要操作（即推入push和弹出pop）来对现实世界的堆栈进行建模。
5.1、使用场景
- 文本编辑器中的撤消机制；
- 用于编译器语法检查中是否匹配括号和花括号；
- 建模一堆书或一叠盘子；
- 在后台使用，通过跟踪以前的函数调用来支持递归；
- 可用于在图上进行深度优先搜索（DFS）。
5.2、编程实战
5.2.1、语法校验
给定一个由以下括号组成的字符串：()[] {}，确定括号是否正确匹配。
例如：({}{}) 匹配，{()(]} 不匹配。
思路：
凡是遇到( { [ 都进行push入栈操作，遇到 ) } ] 则pop栈中的元素，看看是否与当前处理的元素匹配：
匹配完成之后，栈必须是空的。
5.3、复杂度
| 操作 | 时间复杂度 |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek | O(1) |
| search | O(n) |
| size | O(1) |