1, 栈基本知识
栈是一种特殊的列表, 栈的元素只能通过列表的一端访问, 这一端成为栈顶, 栈具有先进后出的特点, 要想访问栈底的元素, 就必须将上边的元素先拿出来. 对栈的操作主要是入栈和出栈, 通过 push()和 pop()实现. 通过 pop()还能预览栈顶元素, 但是返回元素时, 会将该元素从栈中删除, 所以需要引入 peek()方法, 返回栈顶元素, 而不会将其删除.
2,JS 中栈的实现
从栈的基本知识可以想到, 要实现一个栈, 需要有一个数据的存储空间 (这里使用数组),push() 方法, pop()方法, peek()方法, 使用 top 变量记录栈顶元素, 以便 peek()访问.
实现栈构造函数
- function Stack() {
- this.stack = []
- this.top = 0
- this.pop = pop
- this.push = push
- this.peek = peek
- this.length = length // 用于返回栈元素数量
- this.clear = clear // 用于清空栈
- }
- push()
- function push(param) {
- this.stack[this.top++] = param
- }
栈被压进新元素后, top++, 指向下一个空位置.
- pop()
- function pop() {
- return this.stack[--this.top]
- }
这里为什么是 --this.top 而不是 this.top-- 呢, 因为 top 初始是 0, 一个元素压进栈后, top 变成了 1, 而 stack[1]对应的是第二个元素, 此时只有一个元素, 所以应该减 1, 以访问栈顶元素(逻辑为先减后访问).
- peek()
- function peek() {
- return this.stack[this.top - 1]
- }
此方法用于返回栈顶元素.
- length()
- function length() {
- return this.top
- }
用于返回栈的元素个数.
- clear()
- function clear() {
- this.top = 0
- }
此方法用于清空栈元素
测试实现的栈
测试用例
- var stack = new Stack()
- stack.push('JavaScript')
- stack.push('TypeScript')
- stack.push('ActionScript')
- stack.push('CoffeeScript')
- console.log('栈的元素数量为:' + stack.length())
- console.log('栈顶元素为:' + stack.peek())
- console.log('进行一次出栈操作, 出栈的元素为:' + stack.pop())
- console.log('出栈后栈的元素数量为:' + stack.length())
- console.log('此时栈顶元素为:' + stack.peek())
测试结果
打开命令行工具, 使用 node 执行该 js 文件, 本人为: node stack.js
运行结果为:
3, 栈应用举例
3.1, 回文问题
之前我们探讨过回文问题的解决办法, 关于回文, 不太清楚含义的可以先移步本人另这篇文章, 简单点说就是一个字符串反转过来仍然是原来的字符顺序, 比如:"A man, a plan, a canal: Panama", 忽略大小写, 忽略标点符号. 使用数据结合正则表达式的话, 很容易解决. 使用我们上边建立的栈, 应该如何实现呢?
- function isPalindrome(str) {
- // 新建一个栈
- var stack = new Stack()
- // 使用正则表达式取出句子中的字母
- str = str.replace(/\W/g, '').toLowerCase();
- // 将所有字母入栈
- for (var i = 0; i <str.length; i++) {
- stack.push(str[i])
- }
- // 出栈操作, 拼接每次出栈的字母
- var reverse = ''
- while (stack.length()> 0) {
- reverse += stack.pop()
- }
- // 如果入栈顺序和出栈顺序一致, 则为回文结构
- if (str === reverse) {
- return true
- } else {
- return false
- }
- }
原理: 栈为先进后出, 进栈顺序和出栈顺序一致的话, 两个字符串必定相等, 也就是正反顺序相等, 所以是回文结构, 是不是有种恍然大悟的感觉, 哈哈.
测试一下:
- // test
- var str = 'Hello, JavaScript'
- if (isPalindrome(str)) {
- console.log(str + '是回文结构')
- } else {
- console.log(str + '不是回文结构')
- }
- var str1 = 'A man, a plan, a canal: Panama'
- if (isPalindrome(str1)) {
- console.log(str1 + '是回文结构')
- } else {
- console.log(str1 + '不是回文结构')
- }
node stack.js 得到以下结果, 证明革命成功:
3.2, 模拟递归
假设有个需求是求一个数字的阶乘, 可能大家很快就能想到以下方法:
- // 递归问题
- function factorial(num) {
- if (num === 0) {
- return 1
- } else {
- return num * factorial(num - 1)
- }
- }
- console.log(factorial(6))
使用栈的话, 我们能模拟实现吗?
5 的阶乘为 5x4x3x2x1, 那么我们把 54321 都推进栈里, 然后在出栈时计算阶乘应该就可以了吧? 试试:
- function stackFactorial(num) {
- var s = new Stack()
- while (num> 1) {
- s.push(num--)
- }
- var result = 1
- while (s.length()> 0) {
- result *= s.pop()
- }
- return result
- }
- console.log('stack result:' + stackFactorial(6))
node stack.js 得到以下结果:
更多 JS 实现版数据结构与算法请留意本人后续博客, 有错误欢迎指出 O(_)O~
来源: https://blog.csdn.net/fabulous1111/article/details/79835603