JS数据结构学习:栈
栏目: JavaScript · 发布时间: 5年前
内容简介:什么是栈?栈是一种遵循后进先出原则的有序集合,新添加的或者待删除的元素都保存在栈的同一端,称为栈顶,另一端称为栈底,在栈里,新元素靠近栈顶,旧元素靠近栈底,用个图来看大概这样式的:用一个更形象的例子来说明:上网的时候,每点击一个超链接,浏览器都会打开一个新的页面,并且压入到一个访问历史栈中,你可以不断的点击打开新的页面,但总是可以通过回退重新访问以前的页面,从浏览器的访问历史栈中弹出历史网页地址,从栈顶弹出,总是最新的最先弹出
栈的定义
什么是栈?栈是一种遵循后进先出原则的有序集合,新添加的或者待删除的元素都保存在栈的同一端,称为栈顶,另一端称为栈底,在栈里,新元素靠近栈顶,旧元素靠近栈底,用个图来看大概这样式的:
用一个更形象的例子来说明:上网的时候,每点击一个超链接,浏览器都会打开一个新的页面,并且压入到一个访问历史栈中,你可以不断的点击打开新的页面,但总是可以通过回退重新访问以前的页面,从浏览器的访问历史栈中弹出历史网页地址,从栈顶弹出,总是最新的最先弹出
栈的创建
首先创建一个类用来表示栈,接着声明一个数组用来保存栈里的元素:
function Stack() { let items = [] // 方法声明 }
创建好栈之后,需要为栈声明一些方法,栈一般会包含以下几个方法:
- push(): 添加新元素到栈顶
- pop(): 移除栈顶的元素,同时返回被移除的元素
- peek(): 返回栈顶的元素,不对栈做任何修改
- isEmpty(): 如果栈里没有任何元素就返回true,否则返回false
- clear(): 移除栈里的所有元素
- size(): 返回栈里的元素个数
具体实现:
function Stack() { let items = [] // 添加元素到栈顶,也就是栈的末尾 this.push = function (element) { items.push(element) } // 栈的后进先出原则,从栈顶出栈 this.pop = function () { return items.pop() } // 查看栈顶的元素,访问数组最后一个元素 this.peek = function () { return items[items.length - 1] } // 检查栈是否为空 this.isEmpty = function () { return items.length == 0 } // 返回栈的长度,栈的长度就是数组的长度 this.size = function () { return items.length } // 清空栈 this.clear = function () { items = [] } // 打印栈元素 this.print = function () { console.log(items.toString()) } }
栈的使用
现在我们来看如何使用栈:
let stack = new Stack() stack.push(1) stack.push(2) stack.push(3) console.log(stack.peek()) // 3 console.log(stack.isEmpty()) // false console.log(stack.size()) // 3
先向栈中加入三个元素1,2,3,接下来用一张图来看一下入栈的过程:
入栈过程都是在栈顶依次入栈,接着调用peek方法返回栈顶元素3,isEmpty返回false,size返回栈的长度3,然后在继续调用pop来看看出栈的过程:
stack.pop() stack.print() // 1,2
出栈也是和入栈相同,都是从栈顶开始出栈,保证栈的后入先出原则
es6声明Stack类
上面创建了一个Stack函数来充当类,并且在里面声明了一个私有变量,但是在es6里面是有类的语法的,可以直接用es6新语法来声明,代码大概是这样事的:
class Stack { constructor () { this.items = [] } push (element) { this.items.push(element) } pop () { return this.items.pop() } peek () { return this.items[items.length - 1] } isEmpty () { return this.items.length == 0 } size () { return this.items.length } clear () { this.items = [] } print () { console.log(this.items.toString()) } } let stack = new Stack() stack.push(1) console.log(stack.isEmpty()) stack.print()
看起来似乎不错,比之前要简单,关键是看起来更加合理,使用的是类的语法,调用也没有什么问题,但是如果这么执行呢?
console.log(stack.items)
会发现一个问题,在stack类外面可以直接访问类里面的属性,按照设计items应该是Stack类的私有属性才对,就像之前Stack函数里面的私有变量,是不能在外部访问的,如何才能将items变成私有属性呢?应该会有和我一样想法的人,使用闭包,在闭包里面里面定义私有属性,然后再将stack类返回回来,代码实现大概是这样的:
let Stack = (function () { let items = new WeakMap() class Stack { constructor () { items.set(this, []) } push (element) { let s = items.get(this) s.push(element) } pop () { let s = items.get(this) return s.pop() } peek () { let s = items.get(this) return s[s.length - 1] } isEmpty () { let s = items.get(this) return s.length == 0 } size () { let s = items.get(this) return s.length } clear () { let s = items.get(this) s = [] } print () { let s = items.get(this) console.log(s.toString()) } } return Stack })()
可能有人会问为什么这里要把items定义成一个WeakMap对象,先简单介绍一下WeakMap对象的用法,WeakMap对象是一对键/值对的集合,其键必须是对象,值可以是任意的,定义成WeakMap就是为了将items属性变成私有属性,在外部调用Stack对象的时候无法访问到items属性。
栈的应用
前面介绍了那么多栈相关的知识,最后也是介绍栈的应用场景的时候了,栈的实际应用非常广泛,例如用来存储访问过的任务或路径、撤销的操作。为了有一个更直观的应用了解,下面会介绍如何用来解决计算机中的进制转换问题,将10进制转换为其他进制数,可能不少人已经忘了如何进行进制转换了,下面先来看一个简单的10进制转2进制的过程:
上面的图中展示将一个10进制8转化为2进制数的过程,接下来看看用栈是如何实现的:
function conver(num, radix) { let stack = new Stack() let binaryString = '' let digits = '0123456789ABCDEF' while (num > 0) { stack.push(num % radix) num = parseInt(num / radix) } while (!stack.isEmpty()) { binaryString += digits[stack.pop()] } console.log(binaryString) } conver(8, 2) // 1000
总结
这篇文章主要对栈做了简单介绍,动手实践了栈的实现,以及用栈实现了一个简单进制转换的功能。如果有错误或不严谨的地方,欢迎批评指正,如果喜欢,欢迎点赞。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 数据结构 – 用于构建文件系统的数据结构?
- 荐 用Python解决数据结构与算法问题(三):线性数据结构之栈
- 数据结构和算法面试题系列-C指针、数组和结构体
- 请问二叉树等数据结构的物理存储结构是怎样的?
- 数据结构——单链表
- 常用数据结构
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Servlet和JSP学习指南
Budi Kurniawan / 崔毅、俞哲皆、俞黎敏 / 机械工业出版社华章公司 / 2013-4-14 / 59.00元
本书是系统学习Servlet和JSP的必读之作。由全球知名的Java技术专家(《How Tomcat Works》作者)亲自执笔,不仅全面解读Servlet 和JSP 的最新技术,重点阐述Java Web开发的重要编程概念和设计模型,而且包含大量可操作性极强的案例。 本书共18章:第1章介绍Servlet API和几个简单的Servlet;第2章讨论Session追踪,以及保持状态的4种技术......一起来看看 《Servlet和JSP学习指南》 这本书的介绍吧!