定场诗
金山竹影几千秋,云索高飞水自流;
万里长江飘玉带,一轮银月滚金球。
远自湖北三千里,近到江南十六州;
美景一时观不透,天缘有分画中游。
前言
本章是重读《学习java script数据结构与算法-第三版》的系列文章,本章为各位小伙伴分享数据结构-栈
的故事,请让胡哥带你走进栈
的世界
栈
何为栈?栈是一种遵从后进先出(LIFO)原则的有序集合。
新添加或待删除的元素都保存在栈的同一端,称作栈顶;另一端就叫栈底。
在栈里,新元素都靠近栈顶,旧元素都接近栈底。
基于数组的栈
我们将创建一个基于数组的栈,了解栈的结构、运行规则
/**
* 基于数组array的栈Stack
* @author huxiaoshuai
*/
class Stack {
// 初始化
constructor () {
this.items = []
}
}
使用数组保存栈里的元素
数组允许我们在任何位置添加和删除元素,那基于栈遵循LIFO原则,我们对元素的插入和删除功能进行封装
方法 | 描述 |
---|---|
push(element(s)) | 添加一个(或多个)新元素到栈顶 |
pop() | 移除栈顶元素,同时返回被移除的元素 |
peek() | 返回栈顶的元素,不对栈做任何修改 |
isEmpty() | 判断栈是否为空,为空则返回true,否则返回false |
clear() | 移除栈的所有元素 |
size() | 返回栈的元素个数 |
代码实现
class Stack {
// 初始化
constructor () {
this.items = []
}
/**
* push() 添加元素到栈顶
*/
push (element) {
this.items.push(element)
}
/**
* pop() 移除栈顶元素并返回
*/
pop () {
return this.items.pop()
}
/**
* peek() 返回栈顶部元素
*/
peek () {
return this.items[this.items.length - 1]
}
/***
* isEmpty() 检测栈是否为空
*/
isEmpty () {
return this.items.length === 0
}
/**
* size() 返回栈的长度
*/
size () {
return this.items.length
}
/**
* clear() 清空栈元素
*/
clear () {
this.items = []
}
}
使用Stack类
const stack = new Stack()
console.log(stack.isEmpty()) // true
// 添加元素
stack.push(5)
stack.push(8)
// 输出元素
console.log(stack.peek()) // 8
stack.push(11)
console.log(stack.size()) // 3
console.log(stack.isEmpty()) // false
stack.push(15)
基于以上栈操作的示意图
stack.pop()
stack.pop()
console.log(stack.size()) // 2
基于以上栈操作的示意图
基于对象的栈
创建一个Stack类最简单的方式是使用一个数组来存储元素。在处理大量数据的时候,我们同样需要评估如何操作数据是最高效的。
使用数组时,大部分方法的时间复杂度是O(n)。简单理解:O(n)的意思为我们需要迭代整个数组直到找到要找的那个元素,在最坏的情况下需要迭代数组的所有位置,其中的n代表数组的长度。数组越长,所需时间会更长。另外,数组是元素的一个有序集合,为保证元素的有序排列,会占用更多的内存空间。
使用java script对象来存储所有的栈元素,以实现可以直接获取元素,同时占用较少的内存空间,同时保证所有的元素按照我们的需要进行排列,遵循后进先出(LIFO)原则。
代码实现
/**
* 基于对象的Stack类
* @author huxiaoshai
*/
class Stack {
// 初始化
constructor () {
this.items = {}
this.count = 0
}
/**
* push() 向栈中添加元素
*/
push (element) {
this.items[this.count] = element
this.count++
}
/**
* isEmpty() 判断是否为空
*/
isEmpty () {
return this.count === 0
}
/**
* size() 返回栈的长度
*/
size () {
return this.count
}
/**
* pop() 栈顶移除元素并返回
*/
pop () {
if (this.isEmpty()) {
return undefined
}
this.count--
let result = this.items[this.count]
delete this.items[this.count]
return result
}
/**
* peek() 返回栈顶元素,如果为空则返回undefined
*/
peek () {
if (this.isEmpty()) {
return undefined
}
return this.items[this.count - 1]
}
/**
* clear() 清空栈数据
*/
clear () {
this.items = {}
this.count = 0
}
/**
* toString() 实现类似于数组结构打印栈内容
*/
toString () {
if (this.isEmpty()) {
return ''
}
let objStr = `${this.items[0]}`
for (let i = 1; i < this.count; i++) {
objStr = `${objStr},${this.items[i]}`
}
return objStr
}
}
保护数据结构内部元素
私有属性
有时候我们需要创建供其他开发者使用的数据结构和对象时,我们希望保存内部元素,只有使用允许的方法才能修改内部结构。很不幸,目前JS是没有办法直接声明私有属性的,目前业内主要使用一下几种方式实现私有属性。
下划线命名约定
class Stack { constructor () { this._items = {} this._count = 0 } }
这只是约定,一种规范,并不能实际保护数据
基于ES6的限定作用域Symbol实现类
const _items = Symbol('stackItems') class Stack { constructor () { this[_items] = [] } }
假的私有属性,ES6新增的Object.getOwnPropertySymbols方法能够获取类里面声明的所有Symbols属性
基于ES6的WeakMap实现类
/** * 使用WeekMap实现类的私有属性 */ const items = new WeakMap() console.log(items) // WeakMap { [items unknown] } class Stack { constructor () { items.set(this, []) }