数据结构与算法

数据结构与算法知识详解
帅旋
关注
充电
IT宅站长,技术博主,架构师,全网id:arthinking。

栈数据结构

发布于 2020-04-28 | 更新于 2024-05-16

5、栈

堆栈是一种单端线性数据结构,它通过执行两个主要操作(即推入push和弹出pop)来对现实世界的堆栈进行建模。

image-20200412093126737

5.1、使用场景

  • 文本编辑器中的撤消机制;
  • 用于编译器语法检查中是否匹配括号和花括号;
  • 建模一堆书或一叠盘子;
  • 在后台使用,通过跟踪以前的函数调用来支持递归;
  • 可用于在图上进行深度优先搜索(DFS)。

5.2、编程实战

5.2.1、语法校验

给定一个由以下括号组成的字符串:()[] {},确定括号是否正确匹配。

例如:({}{}) 匹配,{()(]} 不匹配。

思路:

凡是遇到( { [ 都进行push入栈操作,遇到 ) } ] 则pop栈中的元素,看看是否与当前处理的元素匹配:

image-20200412093528871

匹配完成之后,栈必须是空的。

5.3、复杂度

操作 时间复杂度
push O(1)
pop O(1)
peek O(1)
search O(n)
size O(1)

5.4、编程实践

本文作者: 帅旋

本文链接: https://www.itzhai.com/columns/dsa/stack.html

版权声明: 版权归作者所有,未经许可不得转载,侵权必究!联系作者请加公众号。

×
IT宅

关注公众号及时获取网站内容更新。

请帅旋喝一杯咖啡

咖啡=电量,给帅旋充杯咖啡,他会满电写代码!

IT宅

关注公众号及时获取网站内容更新。