其实说到底, 在 js 中栈更像是一种变种的数组, 只是没有数组那么多的方法, 也没有数组那么灵活. 但是栈和队列这两种数据结构比数组更加的高效和可控. 而在 js 中要想模拟栈, 依据的主要形式也是数组.
从这篇文章开始, 可能会接触到一些原型, 原型链, 类, 构造函数等相关的 js 概念, 但是这里并不会过多的介绍这些概念, 必要的时候会进行一些简要的说明, 推荐大家去看看汤姆大叔的深入理解 Javascript 系列, 王福朋大神的深入理解 Javascript 原型和闭包系列. 都是极为不错的深度好文, 推荐大家可以深入学习.
要想实现一个数据结构, 首先你要明白它的基本原理, 那么栈是什么? 又是如何工作的呢?
栈 (stack) https://baike.baidu.com/item/栈/12808149?fr=aladdin 是一种遵循后进先出(Last In First Out) 原则的有序集合. 新添加的元素和待删除的元素都保存在栈的同一端, 称为栈顶, 另一端就叫做栈底. 在栈里, 新元素都接近栈顶, 旧元素都靠近栈底. 其实可以把栈简单理解成往一个木桶里堆叠的放入物品, 最后放进去的在桶的顶端, 也是可以最先拿出来的, 而最先放进去的却在桶的底部, 只有把所有上面的物品拿出来之后才可以拿走底部的物品.
对于数组来说, 可以添加元素, 删除元素, 获取数组的长度以及返回对应下标得到值, 那么在开始构造一个栈之前, 我们需要了解一下栈都有哪些基本操作.
1, 压栈, 也称之为入栈, 也就是把元素加入栈中. 就像是数组中的 push 一样.
2, 出栈, 移除栈顶的元素. 就像是数组中的 pop 一样.
3, 获取栈顶的元素, 不对栈做任何其他操作. 就像是在数组中通过下标获取对应的值一样.
4, 判断栈是否为空. 就像是判断数组的长度是否为 0 一样.
5, 清空栈, 也就是移除栈里的所有元素. 就像是把数组的长度设置为 0 一样.
6, 获取栈里的元素个数. 就像是数组的 length 属性一样.
那么, 我相信我大家已经对栈有了一个基本的了解, 那么我们接下来就看看如何通过构造函数来实现一个自己的 js 栈.
- function Stack () {
- var items = [];
- // 首先, 我们来实现一个入栈的方法, 这个方法负责往栈里加入元素, 要注意的是, 该方法只能添加元素到栈顶, 也就是栈的尾部.
- this.push = function (ele) {
- items.push(ele)
- }
- }
- var stack = new Stack();
我们声明一个构造函数, 并且在构造函数中生命一个私有变量 items, 作为我们 Stack 类储存栈元素的基本支持. 然后, 加入一个 push 方法, 通过 this 来使其指向调用该方法的实例. 下面我们还会通过这样的方式依次添加其他的方法.
- function Stack () {
- var items = [];
- // 首先, 我们来实现一个入栈的方法, 这个方法负责往栈里加入元素, 要注意的是, 该方法只能添加元素到栈顶, 也就是栈的尾部.
- this.push = function (ele) {
- items.push(ele);
- }
- // 然后我们再添加一个出栈的方法, 同样的, 我们只能移除栈顶的元素.
- this.pop = function (ele) {
- return items.pop();
- }
- // 查看栈顶, 也就是栈的尾部元素是什么
- this.peek = function () {
- return items[items.length - 1];
- }
- // 检查栈是否为空
- this.isEmpty = function () {
- return items.length == 0;
- }
- // 检查栈的长度
- this.size = function () {
- return items.length;
- }
- // 清空栈
- this.clear = function () {
- items = [];
- }
- // 打印栈内元素
- this.print = function () {
- console.log(items.toString())
- }
- }
这样我们就通过构造函数完整的创建了一个栈. 我们可以通过 new 命令实例化一个 Stack 对象来测试一下我们的栈好不好用.
- var stack = new Stack();
- console.log(stack.isEmpty()); //true
- stack.push(1);
- stack.print();
- stack.push(3);
- stack.print();
- console.log(stack.isEmpty()); //false
- console.log(stack.size()); //2
- stack.push(10);
- stack.print();
- stack.pop();
- stack.print();
- stack.clear();
- console.log(stack.isEmpty()); //true
我们发现我们的 Stack 类执行的还算不错. 那么还有没有其他的方式可以实现 Stack 类呢? 在 ES6 之前我可能会遗憾懵懂的对你 Say No. 但是现在我们可以一起来看看 ES6 带我们的一些新鲜玩意.
在开始改造我们的 Stack 类之前, 需要先说一下 ES6 的几个概念. Class 语法 http://es6.ruanyifeng.com/#docs/class#constructor-方法 ,Symbol 基本类型 http://es6.ruanyifeng.com/#docs/symbol 和 http://es6.ruanyifeng.com/#docs/set-map#WeakMap . 简单解释一下, 以对后面的改造不会一脸懵逼, 而大家想要更深入的了解 ES6 新增的各种语法, 可以去自行查阅.
Class 语法简单来说就是一个语法糖, 它的功能 ES5 也是完全可以实现的, 只是这样看写起来更加清晰可读, 更像是面向对象的语法.
Symbol 是 ES6 新增的一个基本类型, 前面几篇文章说过, ES5 只有 6 中数据类型, 但是在 ES6 中又新增一种数据类型 Symbol, 它表示独一无二的值.
WeakMap, 简单来说就是用于生成键值对的集合, 就像是对象 ({}) 一样, WeakMap 的一个重要用处就是部署私有属性.
当然, 上面的简单介绍可不仅仅是这样的, 真正的内容要比这些多得多.
那么在大家知道了它们的一些基本意义. 咱们开始改造一下 Stack 类
- class Stack {
- constructor() {
- this.items = [];
- }
- push(element) {
- this.items.push(element);
- }
- pop() {
- return this.items.pop();
- }
- peek() {
- return this.items[this.items.length - 1];
- }
- isEmpty() {
- return this.items.length === 0;
- }
- size() {
- return this.items.length;
- }
- clear() {
- this.items = [];
- }
- toString() {
- return this.items.toString();
- }
- print() {
- console.log(this.items.toString())
- }
- }
这是用 class 来实现的 Stack 类, 其实我们可以看一下, 除了使用了 constructor 构造方法以外, 其实并没有什么本质上的区别.
那么我们还可以使用 Symbol 数据类型来实现, 简单改造一下:
- const _items = Symbol('stackItems');
- class Stack {
- constructor() {
- this[_items] = [];
- }
- push(element) {
- this[_items].push(element);
- }
- pop() {
- return this[_items].pop();
- }
- peek() {
- return this[_items][this[_items].length - 1];
- }
- isEmpty() {
- return this[_items].length === 0;
- }
- size() {
- return this[_items].length;
- }
- clear() {
- this[_items] = [];
- }
- print() {
- console.log(this.toString());
- }
- toString() {
- return this[_items].toString();
- }
- }
使用 Symbol 也没有大的变化, 只是声明了一个独一无二的_items 来代替构造方法中的数组.
但是这样的实现方式有一个弊端, 那就是 ES6 新增的 Object.getOwnPropertySymbols 方法可以读取到类里面声明的所有 Symbols 属性.
- const stack = new Stack();
- const objectSymbols = Object.getOwnPropertySymbols(stack);
- stack.push(1);
- stack.push(3);
- console.log(objectSymbols.length); // 1
- console.log(objectSymbols); // [Symbol()]
- console.log(objectSymbols[0]); // Symbol()
- stack[objectSymbols[0]].push(1);
- stack.print(); // 1, 3, 1
不知道大家注意没有, 我们定义的 Symbol 是在构造函数之外的, 因此谁都可以改动它. 所以这样的方式还不是很完善的. 那么我们还可以使用 ES6 的 WeakMap, 然后用闭包实现私有属性.
- // 通过闭包把声明的变量变成私有属性
- let Stack = (function() {
- // 声明栈的基本依赖
- const _items = new WeakMap();
- // 声明计数器
- const _count = new WeakMap();
- class Stack {
- constructor() {
- // 初始化 stack 和计数器的值, 这里的 set 是 WeakMap 的自身方法, 通过 set 和 get 来设置值和取值, 这里用 this 作为设置值的键名, 那 this 又指向啥呢? 自行 console!
- _count.set(this, 0);
- _items.set(this, {});
- }
- push(element) {
- // 在入栈之前先获取长度和栈本身
- const items = _items.get(this);
- const count = _count.get(this);
- // 这里要注意_count 可是从 0 开始的噢
- items[count] = element;
- _count.set(this, count + 1);
- }
- pop() {
- // 如果为空, 那么则无法出栈
- if (this.isEmpty()) {
- return undefined;
- }
- // 获取 items 和 count, 使长度减少 1
- const items = _items.get(this);
- let count = _count.get(this);
- count--;
- // 重新为_count 赋值
- _count.set(this, count);
- // 删除出栈的元素, 并返回该元素
- const result = items[count];
- delete items[count];
- return result;
- }
- peek() {
- if (this.isEmpty()) {
- return undefined;
- }
- const items = _items.get(this);
- const count = _count.get(this);
- // 返回栈顶元素
- return items[count - 1];
- }
- isEmpty() {
- return _count.get(this) === 0;
- }
- size() {
- return _count.get(this);
- }
- clear() {
- /* while (!this.isEmpty()) {
- this.pop();
- } */
- _count.set(this, 0);
- _items.set(this, {});
- }
- toString() {
- if (this.isEmpty()) {
- return '';
- }
- const items = _items.get(this);
- const count = _count.get(this);
- let objString = `$ {
- items[0]
- }`;
- for (let i = 1; i < count; i++) {
- objString = `$ {
- objString
- },
- $ {
- items[i]
- }`;
- }
- return objString;
- }
- print() {
- console.log(this.toString());
- }
- }
- return Stack;
- })() const stack = new Stack();
- stack.push(1);
- stack.push(3);
- stack.print(); // 1, 3, 1
这是最终比较完善的版本了. 那么不知道大家注没注意到一个小细节, 前面我们只是声明一个变量, 先不管他是不是私有的, 就是数组, 整个 Stack 构造函数都是基于 items 数组来进行各种方法的.
但是这里通过 WeakMap 作为基本, 我们却多用了一个_count, 前面说了_count 是计数器, 那么为啥要用计数器? 因为 WeakMap 是键值对的 "对象类型", 本身是没有像数组这样的长度之说的, 所以需要一个计数器来代替数组的下标, 以实现基于 Stack 的各种方法.
到这里基本上就完成了我们的栈, 下一篇文章会看看如何用我们写好的栈去做一些有趣事情.
最后, 由于本人水平有限, 能力与大神仍相差甚远, 若有错误或不明之处, 还望大家不吝赐教指正. 非常感谢!
来源: https://www.cnblogs.com/zaking/p/8799326.html