数据结构–栈—JS实现一个栈结构
前言:数据结构和算法是脱离语言的,比如pop,push在js中可以使用,但是其他的语言也有吗? 不一定,但是都可以通过数据结构和算法写出其功能
(1)栈是一种后进先出(LIFO)last in first out原则的有序集合;只能从后边添加元素和从开头删除元素
(2)新添加或待删除的元素都保存在栈的同一端,为栈顶(push( 数组中末位置添加元素)数组中的pop(删除数组中最后边的元素也就是先添加进去的))
(3)在栈里新元素都靠近栈顶,旧元素都接近栈底
实现一个栈结构/符合LIFO的原则,需要对插入的数据和删除的数据功能进行限制
实现以下的方法
push(eles):添加一个或者多个元素到栈顶
pop: 移除栈顶的元素,同时返回被移除的元素
peek:返回栈顶的元素,不对栈本身做任何修改
isEmpty:判断栈顶的元素,不对栈本身做任何修改
size:返回栈里面的元素个数,和数组的length属性类似
clear:移除栈元素里边的所有元素
toString:将栈里边的内容通过逗号字符串进行拼接成一个字符串
forEach:讲栈里边的内容进行遍历参数是一个回调函数callback
for of 接口:实现栈皆否的迭代器接口(数组有for of的接口,但是items是一个对象本身没有for of)
直接上代码
/*
数据结构和算法是脱离语言的,比如pop,push在js中可以使用,但是其他的语言也有吗?
不一定,但是都可以通过数据结构和算法写出其功能
实现一个栈结构/符合LIFO的原则,需要对插入的数据和删除的数据功能进行限制
实现以下的方法
push(eles):添加一个或者多个元素到栈顶
pop: 移除栈顶的元素,同时返回被移除的元素
peek:返回栈顶的元素,不对栈本身做任何修改
isEmpty:判断栈顶的元素,不对栈本身做任何修改
size:返回栈里面的元素个数,和数组的length属性类似
clear:移除栈元素里边的所有元素
toString:将栈里边的内容通过逗号字符串进行拼接成一个字符串
forEach:讲栈里边的内容进行遍历参数是一个回调函数callback
for of 接口:实现栈皆否的迭代器接口(数组有for of的接口,但是items是一个对象本身没有for of)
*/
class Stack {
constructor() {
this.count = 0; // 栈的计数器
this.items = {}; // 栈的数据仓库
}
push(...eles) { // 解构一下,可能是一个或者多个
for (let i = 0, len = eles.length; i < len; i++) {
//采用计数器的当前值(自然数)为key,存储实际的数据
this.items[this.count] = eles[i]
this.count++; //每当push一个数据,计数器自增一个1
}
}
size() {
return this.count;
}
isEmpty() {
return !this.count; //取反转成布尔值
}
pop() {
if (this.isEmpty()) {
// 判断栈是否为空,返回undefined
return undefined;
}
this.count--; //计数器自减一个1,得到的就是未删除前最后一个栈顶值的key
let result = this.items[this.count] // 返回一个栈顶的值
delete this.items[this.count] //删除栈顶的值
return result
}
peek() {
if (this.isEmpty()) {
// 判断栈是否为空,返回undefined
return undefined;
}
return this.items[--this.count] //返回一个栈顶的值这里不能用this.count--,可以用this.count-1
}
clear() {
while (!this.isEmpty()) {
this.pop()
}
}
toString() {
if (this.isEmpty()) {
return ""
}
let resultString = ""
for (let i = 0; i < this.count; i++) {
result = `${resultString},${this.items[i]}` // 会多一个逗号
}
return resultString.slice(1) //跳过第一逗号返回
// 如果上边用+=,那么逗号,就在后边,也要删掉最后一个逗号,都可以
}
forEach(cb) {
for (let i = 0; i < this.count; i++) {
// 索引,每一项,arr本身(此时如果是this.item的话就不能调用里边的方法了,所以是this,item知识存放数据的对象)
cb(i, this.items[i], this)
}
}
// 迭代器,也可以增加拦截,在return中进行判断或者增加内容,遍历的时候就起到了作用(底层内容,会改变整个js的判断条件)
[Symbol.iterator]() {
let self = this;
let index = 0;
return {
next() {
if (index < self.count) {
return {
value: self.items[index++],
done: false // 表示是否可以继续往下遍历,如果为false继续
}
} else {
return {
value: undefined,
done: true // 表示迭代结束
}
}
}
}
}
}
// 我们可以用这个来做一个基本实现
let arr = new Stack();
console.log(arr) //打印看一下结构
// 其他方法就可以使用了
arr.push("hello")
arr.push("world")
arr.forEach(function (index, item, arr) {
console.log({
index,
item
})
})