用js模拟数据结构 栈 结构
栈是一种遵从后进先出(LIFO)原则的有序集合。
新添加或待删除的元素都保存在栈的同一端,称作栈顶,另一端就叫栈底。
在栈里,新元素都靠近栈顶,旧元素都接近栈底。
栈是一种遵从后进先出(LIFO)原则的有序集合。新添加或待删除的元素都保存在栈的同一端,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。
我们将创建一个类来表示栈。简单地从创建一个stack-array.js文件并声明Stack类开始。
我们需要一种数据结构来保存栈里的元素。可以选择数组。
数组允许我们在任何位置添加或删除元素。
由于栈遵循LIFO原则,需要对元素的插入和删除功能进行限制。
接下来,要为栈声明一些方法。
-
push(element(s)):添加一个(或几个)新元素到栈顶。
-
pop():移除栈顶的元素,同时返回被移除的元素。
-
peek():返回栈顶的元素,不对栈做任何修改(该方法不会移除栈顶的元素,仅仅返回它)。
-
isEmpty():如果栈里没有任何元素就返回true,否则返回false。
-
clear():移除栈里的所有元素。
-
size():返回栈里的元素个数。
class Stocck{
construct(){
this.count = 0;
this.list = [];
}
//向栈中插入元素
push(element) {
this.items[this.count] = element;
this.count++;
}
//从栈中弹出元素
pop() {
if (this.isEmpty()) { // {1}
return undefined;
}
this.count--; // {2}
const result = this.items[this.count]; // {3}
delete this.items[this.count]; // {4}
return result; // {5}
}
//查看栈顶的值
peek() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.count -1];
}
//验证一个栈是否为空
isEmpty(){
return this.count === 0;
}
//清空栈
clear() {
this.items = {};
this.count = 0;
}
//验证一个栈的大小
size() {
return this.count;
}
}
但是在javascript尽管基于原型的类能节省内存空间并在扩展方面优于基于函数的类,
但这种方式不能保护私有属性(变量)或方法
const stack = new Stack();
console.log(Object.keys(stock));//['count', 'list']
console.log(Object.getOwnPropertyNames(stock));//['count', 'list']
console.log(stock.count)//0
有一种数据类型可以确保属性是私有的,这就是WeakMap
WeakMap可以存储键值对,其中键是对象,值可以是任意数据类型
const items = new WeakMap();
class Stack {
constructor () {
items.set(this, []);
}
push(element){
const s = items.get(this);
s.push(element);
}
pop(){
const s = items.get(this);
const r = s.pop();
return r;
}
}
但是这个方法同样存在一些缺陷,就是在拓展该类的时候,无法继承私有属性