前言
前面两篇文章介绍了数据结构和算法的一些前置内容,这篇文章开始正式学习常见的数据结构,首先学习的就是栈(Stack)。
什么是栈?
栈全称为堆栈,是一种先进后出的的数据结构,栈中只有两种基本操作,也就是插入和删除,也就是入栈和出栈操作,栈只有一端可以进行入栈和出栈操作,我们将其称为栈顶,另一端称其为栈底;如下图展示了栈这个数据结构:
JavaScript中的栈
JavaScript并没有栈这个数据类型,但是可以通过数组进行模拟,而且数组中提供的push()
和pop()
选项,正好实现先入后出的的操作,
示例代码如下:
const stack = [] // 入栈 stack.push(1) stack.push(2) // 出栈 const v1 = stack.pop() // 2 const v2 = stack.pop() // 1
栈的应用场景
栈是算法和程序中最常用的辅助结构,其的应用十分广泛,凡是需要先进后出场景都有栈的身影,比如:
- 函数调用堆栈
- 判断字符串括号是否有效
接下来我们依次来看:
函数调用堆栈
JavaScript中的函数调用堆栈就是一个应用栈的一个典型例子,比如下面这段代码:
function f1() {} function f2() { f1() } function f3() { f2() } f3()
如下图:
执行过程如下:
- 调用函数
f3()
,将f3
压入堆栈; - 在
f3()
中调用了f2()
,将f2
压入堆栈; - 在
f2()
中又调用了f1()
,将f1
压入堆栈; - 只有
f1()
运行完成才能继续往下执行,所以f1()
先出栈,以此类推。
有效的括号
有效的括号是力扣中的一个关于栈的算法题目,题目大意就是判断给定字符串中的括号是否匹配,匹配返回true
,否则返回false
。
解题思路如下:
- 判断字符串的长度是否为偶数,不为偶数直接返回
false
,因为括号都是成对出现的; - 新建一个栈;
- 遍历字符串,遍历到每一项时如果时左括号,将其压入栈;如果是右括号,与栈顶对比,如果相匹配则出栈,不匹配则返回
false
。
实现代码如下:
/** * @param {string} s * @return {boolean} */ var isValid = function(s) { if (s.length % 2 !== 0) return false const stack = [] for(let i = 0; i<s.length; i++) { const c = s[i] // 记录当前项 if (c === '(' || c === '[' || c==='{') { stack.push(c) } else { const t = stack[stack.length - 1] // 获取栈顶元素 if ( (t === '(' && c === ')') || (t === '[' && c === ']') || (t === '{' && c === '}') ) { stack.pop() } else { return false } } } // 如果为0表示全部匹配,有剩余则表示不匹配 return stack.length === 0 };
肯有还有更优的写法,这里直接使用的暴力解法。
总结
到此这篇关于一文让你快速了解JavaScript栈的文章就介绍到这了,更多相关JS 栈内容请搜索阿兔在线工具以前的文章或继续浏览下面的相关文章希望大家以后多多支持阿兔在线工具!