网站建设对工厂意义,石家庄哪家公司做网站好,重庆做网站的程序员待遇,婚庆网站建设策划案费用预算前言js里#xff0c;是没有栈这种原生的数据结构。但是我们可以通过自定义创建栈类#xff0c;来实现对添加/删除元素时更多的控制。创建栈类// 初始化一个基于数组的栈类
class Stack {constructor() {this.items [];}
}为什么我们要选择数组作为栈类的存储数据类型#x…前言js里是没有栈这种原生的数据结构。但是我们可以通过自定义创建栈类来实现对添加/删除元素时更多的控制。创建栈类// 初始化一个基于数组的栈类
class Stack {constructor() {this.items [];}
}为什么我们要选择数组作为栈类的存储数据类型因为栈是一种遵从后进先出LIFO原则的有序集合。新添加或待删除的元素都保存在栈的同一端称为栈顶另外一端为栈底。在栈里新元素越靠近栈顶旧元素越靠近栈底。栈的用途很广。被用于编程语言的编译器和内存中保存变量、方法调用等。也用于浏览器历史记录浏览器的前进后退对栈的设想由于栈遵循LIFO原则不像数组可以随意对数组内的元素进行操作。所以需要对元素的插入和删除等功能做限制。接下来我们为栈类设想一些方法。添加一个或几个新元素到栈顶push(ele) {this.items.push(ele)
}移除栈顶的元素同时返回被移除的元素pop() {return this.items.pop();
}返回栈顶的元素不对栈做任何修改peek() {return this.items[this.items.length-1]
}如果栈为空则返回true 否则返回falseisEmpty() {return this.items.length 0;
}移除栈内所有元素clear() {this.items [];
}返回栈里的元素个数size() {return this.items.length
}实例化Stack类const stack new Stack();
stack.isEmpty(); // true
stack.push(5);
stack.push(6);
stack.peek(); // 6创建一个基于JS对象的Stack类作用我们上面创建的Stack类是使用一个数组来存储数据。那么我们现在为什么要用JS对象来替换Stack类的存储方式?因为在使用数组时大部分方法的时间复杂度为O(n)。n代表数组长度。即在最坏的情况下我们需要迭代整个数组直到找到我们要找的那个元素。另外数组是元素的一个有序集合为了保证元素排列有序它需要占用更多的内存空间。在大多数编程语言里能够直接获取元素占用较少的内存空间的存储方式无非是键值表了。所以我们要使用一个JS对象来存储所有的栈元素并保证他们的顺序并且遵循LFO原则。声明一个Stack类class Stack {constructor() {// count是预先索引可以代表长度但是不存在索引为count的元素this.count 0;this.items {};}
}为什么要定义count属性为了记录栈的大小并帮助我们添加或删除元素。向栈中插入元素要向栈中添加元素我们将使用count变量作为items对象的键名插入的元素则是它的值。在往栈插入元素后我们递增count变量。push(ele) {this.items[this.count] ele;this.count ;
}实例化栈const stack new Stack();
stack.push(5)
stack.push(8)
stack; // {count: 2,items:{0:5,1:8} }判断是否空栈和它的大小size() {return this.count}
isEmpty() {return this.count 0}从栈中弹出元素从弹夹弹出最顶上的一颗子弹pop() {// 空栈弹出undefinedif (this.isEmpty()) {return undefined;}this.count --;const result this.items[this.count]delete this.items[this.count]return result
}查看栈顶的值peek(){if (this.isEmpty()) {return undefined}return this.items[this.count - 1]
}清空栈方法①一键还原clear() {this.count 0;this.items {};
}方法②LIFO原则循环出栈clear() {while (!this.isEmpty()) {this.pop();}
}toString当我们使用数组作为数据结构的时候不需要关心toString的实现、而对象需要我们自己去定义。var a [a,b,5]
a.toString() // a,b,5toString() {if (this.isEmpty()) {return };let objString ;for (let i 0;ithis.count;i) {objString([键名:${i}键值:${this.items[i]}])}return objString
}时间复杂度除了toString方法我们创建的其他方法的复杂度均为O(1);代表我们可以直接找到目标元素并对其操作.保护JS栈类内部的数据结构在栈设计中我们希望保护内部的元素。只有我们暴露出的方法才能修改内部结构。比如在栈中我们要确保元素只能被添加到栈顶。而不是任意位置。也就是说我们需要保护Stack类中声明的items和count属性。上面的例子中无论是以数组或者对象作为存储的数据类型。items和count都是Stack类暴露出来的公开属性。破坏Stack类为了方便理解我们以数组作为Stack类的存储数据类型。const stack new Stack();
stack.push(5);
console.log(Object.getOwnPropertyNames(stack)); // [items]
// 或者
console.log(Object.keys(stack)) // [items]
// 直接破坏数据属性
stack[items] [1,2,3];我们上面创建栈类是使用了ES6语法是基于原型的类创建。这样做的好处在于能够节省内存空间并在扩展方面优于基于函数的类。但是这种方式不能声明私有属性的方法直到ES11!保护内部属性-下划线命名约定一部分开发者喜欢在js中使用下划线命名来约定这个属性为私有属性class Stack {constructor() {this._items {};this._count 0;}
}
但这只是为了规范开发时对类属性的保护实际上并没有用处。保护内部属性 - ES6的限定作用域Symbol出发的思路点就是为了躲避Object.getOwnPropertyNames和Object.keys对stack实例的属性扫描。Symbol是ES6新增的一种基本数据类型。它是不可变的。可以用作对象属性。const _ItemKey Symbol(dataStack)
class Stack {constructor() {this[_ItemKey] []}
}
var stack1 new Stack()
Object.keys(stack1) // []
Object.getOwnPropertyNames(stack1) // []是不是找不到内部的_ItemKey属性了当你以为这样就可以成功躲避对象的属性扫描那你就too young to simple啦ES6新增的Object.getOwnProperty-Symbols方法能够拿到类里面声明的所有Symbols属性Object.getOwnPropertySymbols(stack1) // [Symbol(stack01_item)]
stack1[Object.getOwnPropertySymbols(stack1)[0]] [1,2,3]保护内部属性 - ES6的WeakMap有一种数据类型可以确保属性是私有的这就是WeakMap。WeakMap以键值对存储数据。const db new WeakMap()
class Stack {constructor() {db.set(this,[])}push(t) {const items db.get(this);items.push(t)}pop() {const items db.get(this);return items.pop()}
}
const stack2 new Stack()
stack2.push(5)
stack2.push(10)
stack2 // {}
stack2.pop() // 10
Object.keys(stack2) // []
Object.getOwnPropertyNames(stack2) // []this是吧Stack类自己的引用作为键存入WeakMap数据表里。这样子确实是无懈可击了Stack类里终于有了自己的私有属性。但是采用这种方法会让代码变得难以理解并且在继承扩展类时无法继承私有属性所以不推荐保护内部属性 - ES11的#变量ES11ES2020在类中新增私有变量控制符#在内部变量或者函数前添加一个hash符号#可以将它们设置为私有属性只能在类的内部可以使用。class Stack {#items {};#count 0push(t) {this.#items[this.#count] tthis.#count ;}
}
const stack3 new Stack()
stack3.push(ddd)
stack3.items; // undefined
stack3.#items // Uncaught SyntaxError: Private field #items must be declared in an enclosing class
Object.keys(stack3) // []用栈解决问题栈可以解决很多计算机科学问题。从十进制到二进制在日常生活中我们主要使用十进制在计算机科学中二进制非常重要。因为计算机的所有内容都是用二进制数字表示的0和1我们要利用栈来强化JS把十进制转换成二进制的能力。规则要把十进制转成二进制。我们可以用十进制数除以2二进制是满二进一并对商取整。直到结果是0为止。我们现在把10转成二进制数字const decimalToBinary (decNumber) {const remStack new Stack();let binaryString ;// 避免方法改变传入的十进制值let cloneDecNumber decNumber;while (cloneDecNumber 0) {// 把余数存进去remStack.push(cloneDecNumber % 2);cloneDecNumber Math.floor(cloneDecNumber /2);}// 取值while (!remStack.isEmpty()) {binaryString remStack.pop().toString();}return binaryString
}decimalToBinary(233) // 11101001
decimalToBinary(10) // 1010
decimalToBinary(1000) // 1111101000
decimalToBinary(100) // 1100100进制转换算法我们修改之前的算法。使它能够把十进制转换成基数为2-6的任意进制。const baseConverter (decNumber,base) {const remStack new Stack();let number decNumber;let rem;let baseString ;if (base 2 || base36) {return }while (number 0) {remStack.push(Math.floor(number % base))number Math.floor(number / base)}// digits是参照表const digits 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZwhile (!remStack.isEmpty()) {baseString digits[remStack.pop()];}return baseString
}
十进制转二进制余数是0或1十进制转为八进制余数是0-7十进制转十六进制时余数是0-1516-1但是计算机语言里没有所谓的15而是用A、B、C、D、E、F分别对应10、11、12、13、14、15因此我们需要对栈中的数字做转化从十一进制起字母表中的每个字母代表对应的基数。baseConverter (100345,2)
//11000011111111001
baseConverter (100345,8)
//303771
baseConverter (100345,35)
//2BW0
baseConverter (100345,16)
//187F9
