1. 栈是什么?
栈是一种遵从后进先出 (LIFO) 的有序集合. 新添加的或删除的元素都保存在栈的末尾, 称为栈顶, 另一端就叫栈底. 在栈里, 新元素都靠近栈顶, 旧元素都接近栈底.
2. 通俗一点理解
你可以把栈看做一摞书.
我们把书一本本摞起来, 最先放的书在最下面, 而最后放的书在最上面. 我们拿书或者放书都在书堆的最顶部. 最顶部的那本书就是栈顶, 最底部的那本书就是栈底.
3. 栈有那些属性或者方法呢?
push(element): 把一个元素添加到栈顶
pop () : 移除栈顶元素, 同时返回栈顶元素
peek () : 返回栈顶的元素
isEmpty(): 判断栈是否为空, 如果是返回 true, 否则返回 false
clear(): 清空栈
size: 返回栈里元素的个数
4. 如何用 JS 去实现一个栈呢?
1. 先初始化一个空栈
我们基于 JS 里面的数组来初始化一个没有方法的栈
- class Stack {
- constructor () {
- this.data = [] // 存储数据的数组
- this.bottom = null // 栈底
- this.top = null // 栈顶
- }
- }
2. 我们尝试去实现栈的 push 方法
- class Stack {
- constructor () {
- this.data = [] // 存储数据的数组
- this.bottom = null // 栈底
- this.top = null // 栈顶
- }
- push (element) {
- this.top = element // 新加入的元素就是栈顶
- this.data.push(element)
- if (!this.bottom) { // 如果新加入的元素是第一个的话, 那么它就是栈底
- this.bottom = element
- }
- }
- }
我们创建一个新的栈, 并且调用一下 push 方法:
- let stack = new Stack()
- stack.push('head')
- stack.push('jack')
- stack.push('say')
- console.log(stack)
并把该 JS 文件引入 html 文件里面,
打印结果如下:
我们可以看见栈它的栈底 bottom 是'head', 也就是第一个添加的元素, 栈顶是'say', 也就是最后一个添加的元素. 这样 push 方法我们就实现了.
3. 我们尝试去实现一下 pop()方法
- class Stack {
- constructor () {
- this.data = []
- this.bottom = null // 栈底
- this.top = null // 栈顶
- }
- // 其它方法省略
- pop () {
- let topData = this.data.pop() // 获取栈顶的元素
- let len = this.data.length
- this.top = this.data[len - 1] // 重新设置栈顶
- if (len === 0) { // 如果栈里面没有元素了, 那么重置
- this.top = null
- this.bottom = null
- }
- return topData
- }
- }
接着打印下结果:
- let stack = new Stack()
- stack.push('head')
- stack.push('jack')
- stack.push('say')
- let topData = stack.pop()
- console.log(topData)
- console.log(stack)
结果如下:
我们可以看见, 返回的 topData 就是我们最后添加的元素, 执行 pop()方法之后, 栈的栈顶也发生了相应的变化
4. 大家一起动手尝试一下
大家感兴趣的话, 可以接着把后面的几个方法实现一下.
thank you for your view~
来源: http://www.qdfuns.com/article/50934/cbc01c779651bc279a3362ee04faed47.html