JavaScript描述数据结构与算法
栈是一种特殊的列表，一种后进先出的数据结构。任何不在栈顶的元素都无法访问。为了得到栈底的元素，必须拿先拿掉上面的元素。所以就有了入栈和出栈。
此例，利用了数组来充当数据仓库，入栈使用push()方法，出栈使用pop()方法。
* 使用var stack=new Stack() 创建一个栈实例 * 实例属性 * this.dataStore 初始化空数组，数据仓库 * this.top 记录栈顶的位置 * 实例方法 * push(ele) 栈顶添加一个元素 * pop() 弹出栈顶元素 * peek() 返回当前栈顶元素（top值不会修改，仅查看） * length() 返回当前元素个数 * clear() 清空栈具体实现方法
function Stack() { this.dataStore=[]; //初始化空数组保存 this.top=0; //记录栈顶位置 }; /* *push()栈顶添加一个数据 *param{ele} 添加的元素 */ Stack.prototype.push=function(ele) { this.dataStore[this.top++]=ele; }; //移除栈顶元素top值会修改 Stack.prototype.pop=function() { let _pop=this.dataStore.pop(); this.top--; return _pop }; //返回栈顶元素但是top值不做修改 Stack.prototype.peek=function() { return this.dataStore[this.top - 1] }; //返回当前栈存储的元素个数 Stack.prototype.length=function() { return this.top } //清空栈 Stack.prototype.clear=function() { this.dataStore=[]; this.top=0; }要计算一个阶乘5！
function fact(n) { if(n===0){ return 1; } else { return n * fact(n-1) }}利用栈的方式，将数字推入栈，然后一个一个取出
function fact(n) { var stack=new Stack(); while (n > 1) { stack.push(n--) } var product=1; while (stack.length() > 0) { product *=stack.pop(); } return product;}开篇
数据结构这词大家都不陌生吧，这可是计算机专业人员的必修专业课之一，如果想成为专业的开发人员，必须深入理解这门课程，在这系列文章里，笔者将使用ES6，让大家熟悉数据结构这门专业课的内容。
到底什么是数据结构？数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关（来源百度百科）。更多关于数据结构的介绍，大家可以先看看笔者的这篇文章《JavaScript 数据结构：什么是数据结构？》。
本篇文章笔者将从数据结构最基础的结构开始介绍——stack（栈），笔者将从以下几个方面进行介绍：
什么是栈？如何用JS简单的实现栈？创建更高效的基于对象Stack类实际应用举例练习题本篇文章阅读时间预计10分钟。
01 什么是栈?
栈是一种高效的数据结构（后进先出（LIFO）原则的有序集合），因为数据只能在栈顶添加或删除，所以这样的操作很快，而且容易实现。栈的使用遍布程序语言实现的方方面面。编程语言中的编译器也会使用到堆栈，计算机内存也会使用堆栈来存储变量和方法调用，浏览器的后退功能。除了计算机方面有诸多栈的应用，现实中也有实际例子，比如我们从一摞书中拿一本书，吃自助餐从一摞盘子里拿最上面的盘子，等等：
02 如何用JS简单的实现栈？
我们如何使用JS模拟一个简单的栈呢，首先我们创建一个stack-array.js文件，声明一个StackArray类，代码如下：
class StackArray { constructor() { this.items=[]; }}接下来该怎么做？我们需要一个能够存储堆栈元素的数据结构，我们可以使用数组结构来完成，同时还需要我们在堆栈中添加和移除数据元素，由于堆栈后进先出的原则，我们的添加和删除方法稍微特别些，Stack这个类的实现包含以下几个方法：
push(element(s)): 此方法将新添加的元素添加至堆栈的顶部pop():此方法删除栈顶的元素，同时返回已删除的元素peek(): 返回堆栈的顶部元素isEmpty(): 判断堆栈是否为空，如果为空，返回True, 否则返回False。clear(): 清空堆栈所有的元素。size(): 此方法返回堆栈元素的数量，类似数组的长度。toArray(): 以数组的形式返回堆栈的元素。toString()：以字符串的形式输出堆栈内容。push()
此方法负责向堆栈添加新元素，其中最重要的特点就是：只能将新元素添加到栈顶，即堆栈的末尾，我们可以使用数组的push方法正好符合这个需求，代码如下：
push(element) { this.items.push(element);} pop()
接下来我们来实现pop()方法，此方法实现删除栈顶的元素，由于遵循LIFO原则，删除的是最后的元素，我们可以使用数组自带的pop方法，代码如下：
pop() { return this.items.pop();} peek()、isEmpty()、size()、clear()
核心的添加和删除已经完成，现在我们来实现相关的辅助方法， peek()方法让我们获取堆栈最后的一个元素，实现代码如下：
peek() { return this.items[this.items.length - 1];} isEmpty()的方法也十分简单，判断堆栈数组的长度是否为0即可，代码如下：
isEmpty() { return this.items.length===0;} size()方法更简单，使用数组的length方法即可，代码如下:
size() { return this.items.length;} 最后实现最简单的清空方法clear()，将堆栈变量重新置空赋值即可:
clear() { this.items=[];}最终完成的stack-array.js代码如下：
export default class StackArray { 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=[]; } toArray() { return this.items; } toString() { return this.items.toString(); }}接下来我们创建一个stackdemo.js的文件，引入我们的stack-array.js文件，我们一起来实践下如何使用我们创建好的StackArray类，代码如下：
import StackArray from 'stack-array.js';const stack=new StackArray();console.log('stack.isEmpty()=> ', stack.isEmpty()); // outputs truestack.push(5);stack.push(8);console.log('stack after push 5 and 8=> ', stack.toString());console.log('stack.peek()=> ', stack.peek()); // outputs 8stack.push(11);console.log('stack.size() after push 11=> ', stack.size()); // outputs 3console.log('stack.isEmpty()=> ', stack.isEmpty()); // outputs falsestack.push(15);stack.pop();stack.pop();console.log('stack.size() after push 15 and pop twice=> ', stack.size()); // outputs 2我们可以新建一个stackdemo.html，引入stackdemo.js(<script type="module" src="stackdemo.js"></script>)，打开stackdemo.html即可，堆栈的运行示意如下图所示：
执行完push后的堆栈
执行完pop后的堆栈
03 创建更高效的基于对象Stack类
上一小节我们基于数组快速实现了栈，我们清楚数组是有序数组，如果存储大数据，内容过多的话，长度过大的话，会消耗更多的计算机内存，算法的复杂度就会增加（O(n)，后面的文章将会介绍），为了解决这个问题，我们使用更原始的方法进行实现。首先我们在stack.js文件里声明stack类，代码如下：
class Stack { constructor() { this.count=0; this.items={}; } // methods} push()
在JS中，对象是一组键值对，我们可以将使用count变量作为items对象的键，元素是其值，添完新元素后，count变量加1，代码实现如下：
push(element) { this.items[this.count]=element; this.count++;}比如我们可以向空的栈里添加新元素5和8，代码如下：
const stack=new Stack();stack.push(5);stack.push(8);
如果输出Stack对象的items和count，效果如下：
items={ 0: 5, 1: 8};count=2;isEmpty()
判断栈是否空，我们只需要判断count变量是否为0即可，代码如下：
isEmpty() { return this.count===0;}pop()
改写这个方法，我们首先需要验证堆栈是否为空，如果未空返回undefined，如果不为空，我们将变量count的值减1，同时删除对应的属性，代码如下：
pop() { if (this.isEmpty()) { return undefined; } this.count--; const result=this.items[this.count]; delete this.items[this.count]; return result;}接下来我们改写其他的方法，完整代码如下：
export default class Stack { constructor() { this.count=0; this.items={}; } push(element) { this.items[this.count]=element; this.count++; } pop() { if (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]; } isEmpty() { return this.count===0; } size() { return this.count; } clear() { /* while (!this.isEmpty()) { this.pop(); } */ this.items={}; this.count=0; } toString() { if (this.isEmpty()) { return ''; } let objString=`${this.items[0]}`; for (let i=1; i < this.count; i++) { objString=`${objString},${this.items[i]}`; } return objString; }}虽然我们类完成了，大家是不是觉得有点问题，由于我们创建的类的属性对于任何开发人员都是公开的，我们希望只能在栈顶添加元素，不希望在其他位置添加元素，但是我们在Stack类中声明的items和count属性不受保护，这是JS的规则问题，难道我们没有办法改变了吗？答案是可以，我们可以ES6加入的新类型Symbol数据类型作为对象的属性具有私有性的特点（关于Symbol数据类型，笔者的这篇文章有过介绍《【ES6基础】Symbol介绍：独一无二的值》），改写基于stack-array.js版本的代码，代码如下：
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(); }}const stack=new Stack();const objectSymbols=Object.getOwnPropertySymbols(stack);console.log(objectSymbols.length); // 1console.log(objectSymbols); // [Symbol()]console.log(objectSymbols[0]); // Symbol()stack[objectSymbols[0]].push(1);stack.print(); // 5, 8, 104 实际应用举例
堆栈在实际的问题中有着各种各样的运用，比如我们会经常使用各种软件的撤销操作功能，尤其是Java和C#编程语言使用堆栈来变量存储和方法调用，并且可以抛出堆栈溢出异常，尤其是在使用递归算法时。接下来，我们亲自动手实现个10进制转2进制的功能。
我们已经熟悉十进制。 然而，二进制表示在计算机科学中非常重要，因为计算机中的所有内容都由二进制数字（0和1）表示。 如果没有在十进制和二进制数之间来回转换的能力，与计算机进行通信将会十分困难。要将10进制转换成2进制，我们需要将要转换数字除以2，再将结果除以2，如此循环直到结果为0为止，具体示意如图所示：
2进制转换逻辑示意图
基于上图逻辑释义，完成的功能代码如下：
function decimalToBinary(decNumber) { const remStack=new Stack(); let number=decNumber; let rem; let binaryString=''; while (number > 0) { rem=Math.floor(number % 2); remStack.push(rem); number=Math.floor(number / 2); } while (!remStack.isEmpty()) { binaryString +=remStack.pop().toString(); } return binaryString;}从上述代码我们定义了一个堆栈，使用循环处理待处理的数字，将取模的余数推入堆栈，然后逐个弹出，拼接成字符串进行输出。接着我们测试下，十进制转二进制是否符合预期，如下段测试代码：
console.log(decimalToBinary(233)); // 11101001console.log(decimalToBinary(10)); // 1010console.log(decimalToBinary(1000)); // 1111101000
05 练习题
刚才我们实践了十进制转二进制，为了让其更有通用性，因为在实际应用中，不仅仅有二进制的转换需求，比如还有8进制、16进制等，现在笔者要给大家留作业了，实现函数baseConverter(decNumber, base)，第一参数是要转换的10进制数，第二个参数是需要转换的进制，让其具备10进制数任意转换成2~36进制的需求，欢迎大家在留言区贴代码。
本篇文章，我们了解了什么是数据结构，并深入学习了堆栈这个数据结构，以及如何用JS代码实现堆栈，并讲解了不同的实现方式，同时了解栈在计算机领域的应用，并一起实践了一个十进制数转二进制的练习，接下来本系列文章，笔者将带着大家一起深入学习和堆栈类似的队列结构，唯一不同的就是先进先出（FIFO），敬请期待。
发表评论