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) |