当前位置:网站首页>栈:如何实现有效括号的判断?
栈:如何实现有效括号的判断?
2022-07-04 18:46:00 【Wu_Candy】
作者 | 无量测试之道 编辑 | 小 晴
有效括号,刷过LeetCode的也许对这道题很熟悉。
1.开篇问题:有效的括号[1]
假如现在要你来解这道题,你会想到怎样的解法了?
这就要用到我们今天要讲的“栈”这种数据结构。带着这个问题,我们来学习今天的内容。
2.如何理解“栈”?
关于栈,有一个非常贴切的游戏--汉诺塔。玩这个游戏的时候,我们都是从下往上一个一个放;取的时候,我们也是从上往下一个一个地依次取,不能从中间任意抽出。后进者先出,先进者后出,这就是典型的“栈”结构。
从栈的操作特性上来看,栈是一种“操作受限”的线性表,只允许在一端插入和删除数据。 栈的定义[2]
: 栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
3.如何实现栈
从刚才栈的定义里,我们可以看出,栈主要包含两个操作,入栈和出栈,也就是在栈顶插入一个数据和从栈顶删除一个数据。理解了栈的定义之后,我们来看一看如何用代码实现一个栈。
【本文使用 swift
语言来编写代码,读者朋友们不要因为编程语言不同而有畏难情绪,重要的是思维和逻辑,语言只是表达方式。你可以用你自己熟悉的语言来表达你的逻辑,可以先试着写一写】
Talking is cheap,show you the code.
class Stack {
//初始化数组
var datas = [Int]()
//出栈操作
func pop() -> Int? {
return datas.popLast()
}
//入栈操作
func push(obj: Int) {
datas.append(obj)
}
//栈顶对象
func top() -> Int? {
return datas.last
}
}
4.栈在实际开发过程中的应用
- 栈在函数调用中的应用
func calculate() {
let a = 3
let b = 5
var result = 0
result = add(x: a, y: b)
print(result)
}
func add(x: Int, y: Int) -> Int {
var sum= 0
sum = x + y
return sum
}
从代码中我们可以看出,calculate() 函数调用了 add() 函数,传入临时变量a和b,获取计算结果,最后打印 result 的值。
为了让你清晰地看到这个过程对应的函数栈里出栈、入栈的操作,我画了一张图。图中显示的是,在执行到 add() 函数时,函数调用栈的情况。
- 递归
在算法中,经常会使用的一个思想就是递归思想。很著名的就是斐波那契数列[3]
F(0) =0,
F(1) =1,
F(n) = F(n-1)+F(n-2)(n≥2,n∈N*)
计算F(n)
时需要先计算F(n-1)
和F(n-2)
计算F(n-1)
时需要先计算F(n-2)
和F(n-3)
计算F(n-2)
时需要先计算F(n-2)
和F(n-3)
··· 最后的效果是,会有很多中间值压入栈中,这也是为什么,当n
很大的时候,会非常消耗内存。所以在实际的开发中,掌握这些底层的开发基础,会有助你选择合适的技术方案。
5.概念区分:数据结构堆栈 VS 内存中的堆栈
在学习计算机基础的时候,我们知道内存中有栈区和堆区。那它与数据结构中的堆栈有什么区别了,它们是同一个概念吗?
内存中的堆栈和数据结构堆栈不是一个概念,可以说内存中的堆栈是真实存在的物理区,数据结构中的堆栈是抽象的数据存储结构。
内存空间在逻辑上分为三部分:代码区、静态数据区和动态数据区,动态数据区又分为栈区和堆区。
代码区:存储方法体的二进制代码。高级调度(作业调度)、中级调度(内存调度)、低级调度(进程调度)控制代码区执行代码的切换。
静态数据区:存储全局变量、静态变量、常量,常量包括final修饰的常量和String常量。系统自动分配和回收。
栈区:存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。
堆区:new一个对象的引用或地址存储在栈区,指向该对象存储在堆区中的真实数据。
6.解答开篇
好了,我想现在你已经完全理解了栈的概念。我们再回来看看开篇的思考题,如何实现有效括号的判断?其实使用栈的思想就可以非常完美的解决这个问题。
我们开始分析:
- 1.如果开始就是右括号
)、]、}
,很明显不合法,直接返回false - 2.如果是左括号
(、[、{
,就压栈。如果是右括号)、]、}
,在stack有值的情况下与栈顶元素匹配,匹配通过则栈顶元素出栈,否则直接返回false。
下面是swift
解题的实现代码
class Solution {
func isValid(_ s: String) -> Bool {
if s.count == 0 { return false }
var stack = [String]()
let dict: [String:String] = ["(":")","[":"]","{":"}"]
for c in s {
if dict.keys.contains(c.description) {
stack.append(c.description) //如果是左括号就入栈
}else {
if stack.count > 0 && c.description == dict[stack.last!] { //如果是右括号,并且匹配就出栈
stack.removeLast()
}else {
return false
}
}
}
return stack.count == 0
}
}
在LeetCode上也有很多种语言的解法,这里分享一个python[4]
的解法
7.内容总结
我们来回顾一下今天讲的内容。栈是一种操作受限的数据结构,只支持入栈和出栈操作。后进先出是它最大的特点。我们还知道数据结构中的堆栈和内存中的堆栈不是同一个概念。我们也理解了栈在实际开发中的些应用,以及使用递归,当n
值很大地时候,会有大量的临时变量被压如栈中而消耗内存。以及最后通过栈的核心思想来解LeetCode中比较经典的算法题。
相信你也真正的掌握了栈这种数据结构了。那赶紧动手敲代码来实践吧!
参考资料:
- 1.有效的括号: https://leetcode-cn.com/problems/valid-parentheses
- 2.栈的定义: https://baike.baidu.com/item/%E6%A0%88/12808149?fr=aladdin
- 3.斐波那契数列: https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97/99145?fr=aladdin
- 4.python语言实现: https://leetcode-cn.com/problems/valid-parentheses/solution/valid-parentheses-fu-zhu-zhan-fa-by-jin407891080/
边栏推荐
- FS8B711S14电动红酒开瓶器单片机IC方案开发专用集成IC
- 软件客户端数字签名一定要申请代码签名证书吗?
- 泰山OFFICE技术讲座:关于背景(底纹和高亮)的顺序问题
- 做社交媒体营销应该注意些什么?Shopline卖家的成功秘笈在这里!
- Integretee integrates into Moonriver through xcm, bringing enterprise class privacy solutions to its ecosystem
- 多表操作-外连接查询
- Niuke Xiaobai month race 7 e applese's super ability
- New wizard effect used by BCG
- Employment prospects of neural network Internet of things application technology [welcome to add]
- Taishan Office Technology Lecture: about the order of background (shading and highlighting)
猜你喜欢
Siemens HMI download prompts lack of panel image solution
[ismb2022 tutorial] the picture shows the precision medicine of learning. Marinka zitnik, Harvard University, keynote speaker, with 87 ppt
Ziguang zhanrui completed the first 5g R17 IOT NTN satellite on the Internet of things in the world
C language - Introduction - Foundation - grammar - process control (VII)
MySQL中的日期时间类型与格式化方式
Creation of JVM family objects
Installation and use of VMware Tools and open VM tools: solve the problems of incomplete screen and unable to transfer files of virtual machines
Employment prospects of neural network Internet of things application technology [welcome to add]
FS4061A升压8.4V充电IC芯片和FS4061B升压12.6V充电IC芯片规格书datasheet
解密函数计算异步任务能力之「任务的状态及生命周期管理」
随机推荐
1009 product of polynomials (25 points) (PAT class a)
【历史上的今天】7 月 4 日:第一本电子书问世;磁条卡的发明者出生;掌上电脑先驱诞生
华为云云商店首页 Banner 资源位申请
Niuke Xiaobai month race 7 e applese's super ability
kotlin 继承
软件客户端数字签名一定要申请代码签名证书吗?
So this is the BGP agreement
Process of manually encrypt the mass-producing firmware and programming ESP devices
Informatics Olympiad 1336: [example 3-1] find roots and children
15million employees are easy to manage, and the cloud native database gaussdb makes HR office more efficient
Integretee integrates into Moonriver through xcm, bringing enterprise class privacy solutions to its ecosystem
Actual combat simulation │ JWT login authentication
Cbcgptabwnd control used by BCG (equivalent to MFC TabControl)
Why is the maximum speed the speed of light
九齐单片机NY8B062D单按键控制4种LED状态
Crystal optoelectronics: ar-hud products of Chang'an dark blue sl03 are supplied by the company
[ismb2022 tutorial] the picture shows the precision medicine of learning. Marinka zitnik, Harvard University, keynote speaker, with 87 ppt
Abc229 summary (connected component count of the longest continuous character graph in the interval)
Employment prospects and current situation of Internet of things application technology
Decryption function calculates "task state and lifecycle management" of asynchronous task capability