其实说到底，在js中栈更像是一种变种的数组，只是没有数组那么多的方法，也没有数组那么灵活。但是栈和队列这两种数据结构比数组更加的高效和可控。而在js中要想模拟栈，依据的主要形式也是数组。
从这篇文章开始，可能会接触到一些原型，原型链，类，构造函数等相关的js概念，但是这里并不会过多的介绍这些概念，必要的时候会进行一些简要的说明，推荐大家去看看汤姆大叔的深入理解Javascript系列，王福朋大神的深入理解Javascript原型和闭包系列。都是极为不错的深度好文，推荐大家可以深入学习。
要想实现一个数据结构，首先你要明白它的基本原理，那么栈是什么？又是如何工作的呢？
栈（stack）是一种遵循后进先出（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());//truestack.push(1);stack.print();stack.push(3);stack.print();console.log(stack.isEmpty());//falseconsole.log(stack.size());//2stack.push(10);stack.print();stack.pop();stack.print();stack.clear();console.log(stack.isEmpty());//true
我们发现我们的Stack类执行的还算不错。那么还有没有其他的方式可以实现Stack类呢？在ES6之前我可能会遗憾懵懂的对你Say No。但是现在我们可以一起来看看ES6带我们的一些新鲜玩意。
在开始改造我们的Stack类之前，需要先说一下ES6的几个概念。Class语法，Symbol基本类型和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); // 1console.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的各种方法。
到这里基本上就完成了我们的栈，下一篇文章会看看如何用我们写好的栈去做一些有趣事情。
最后，由于本人水平有限，能力与大神仍相差甚远，若有错误或不明之处，还望大家不吝赐教指正。非常感谢！
用js来实现那些数据结构（栈01）
原文地址：https://www.cnblogs.com/zaking/p/8799326.html