资料结构基础栈简介（使用ES6）
开篇
资料结构这词大家都不陌生吧，这可是计算机专业人员的必修专业课之一，如果想成为专业的开发人员，必须深入理解这门课程，在这系列文章里，笔者将使用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 true
stack.push(5);
stack.push(8);
console.log('stack after push 5 and 8 => ', stack.toString());
console.log('stack.peek() => ', stack.peek()); // outputs 8
stack.push(11);
console.log('stack.size() after push 11 => ', stack.size()); // outputs 3
console.log('stack.isEmpty() => ', stack.isEmpty()); // outputs false
stack.push(15);
stack.pop();
stack.pop();
console.log('stack.size() after push 15 and pop twice => ', stack.size()); // outputs 2
我们可以新建一个stackdemo.html，引入stackdemo.js()，开启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 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); // 1
console.log(objectSymbols); // [Symbol()]
console.log(objectSymbols[0]); // Symbol()
stack[objectSymbols[0]].push(1);
stack.print(); // 5, 8, 1
04 实际应用举例
堆叠在实际的问题中有着各种各样的运用，比如我们会经常使用各种软件的撤销操作功能，尤其是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)); // 11101001
console.log(decimalToBinary(10)); // 1010
console.log(decimalToBinary(1000)); // 1111101000
05 练习题
刚才我们实践了十进位制转二进位制，为了让其更有通用性，因为在实际应用中，不仅仅有二进位制的转换需求，比如还有8进位制、16进位制等，现在笔者要给大家留作业了，实现函式baseConverter(decNumber, base)，第一引数是要转换的10进位制数，第二个引数是需要转换的进位制，让其具备10进位制数任意转换成2~36进位制的需求，欢迎大家在留言区贴程式码。
本篇文章，我们了解了什么是资料结构，并深入学习了堆叠这个资料结构，以及如何用JS程式码实现堆叠，并讲解了不同的实现方式，同时了解栈在计算机领域的应用，并一起实践了一个十进位制数转二进位制的练习，接下来本系列文章，笔者将带着大家一起深入学习和堆叠类似的伫列结构，唯一不同的就是先进先出（FIFO），敬请期待。
