前言
做前端已有几年的时间，各种前端技术学了一堆，换着技术开发网站，感觉自己很牛逼的样子。这段时间总感觉到达了瓶颈，怎么也突破不了，冷静想了下。功能的实现、封装什么都没问题，但是就是算法差强人意。把大学的数据结构拿出来翻了下，这阶段再去看算法，比大学期间清楚太多了，很多原来知道有那回事儿，现在能明白用途在什么地方。我想我找到了突破瓶颈的方式了。从这篇文章开始，我会陆续的把数据结构中的算法用原生js实现。
栈
栈是一种数据结构，栈只有一个入口和一个出口，它的特点是LIFO(后入先出)，即比如我们吃的罐装薯片，只有从顶部一片一片的拿出来，才能拿到底部。因为栈的LIFO的特点，所有任何不在栈顶元素都无法访问到，为了得到栈底元素，必须把上面的元素都拿走，才能访问。而栈是一种列表，在js中，可以通过数据的方式来存储。
到这儿便有思路了，首先需要一个data存储数据，data是一个数组，因栈只能访问栈顶元素，需要一个变量top存储栈顶元素的位置，当入栈时top + 1,当出栈时，top - 1，那么入栈需要一个方法s_push,出栈需要一个方法s_pop，还需返回栈顶元素的方法s_peek。
有时，需要清空栈、获取栈的长度或判断元素是否在栈内，以上方法是不够的，还需创建方法，s_clear(清空栈内元素)、s_length(获取栈的长度）。
1. 首先，需要创建一个Stack类的构造函数，如下：
function Stack () {
this.s_top = 0; //初始化栈顶位置为0
this.s_data = []; //初始化空栈
this.s_push = s_push; //入栈方法
this.s_pop = s_pop; //出栈
this.s_peek = s_peek; //获取栈顶元素
this.s_length = s_length; //栈的长度
this.s_clear = s_clear; //清空栈
}
2. 入栈，实现s_push方法，当向栈中压入新元素时，需要改变s_top对应栈的位置加1，然后指向数组下一个空位置。如下：
function s_push (element) {
this.s_data[this.s_top++] = element;
}
3. 出栈，s_pop方法和入栈相仿，每次取出元素后，将s_top - 1，然后返回当前删除的值，如下：
function s_pop () {
--this.s_top;
return this.s_data.pop();
}
4. 获取栈顶元素，s_peek方法，栈顶的位置为s_top,只需要数组中取最后一个元素即可，如下：
function s_peek () {
return this.s_data[this.s_top - 1];
}
5. 清空栈，s_clear方法，设置栈顶指向为0，清空存储数据，代码如下：
function s_clear () {
this.s_top = 0;
this.s_data = [];
}
6. 获取栈的长度，s_length, 即s_top的值，如下：
function s_length () {
return this.s_top;
}
实例
1. 使用栈模拟递归
如需要封装一个阶乘的函数，用递归的思想，如下：
function factorial (num) {
if (typeof num !== 'number') return num;
if (num <= 1) {
return 1;
} else {
return num * arguments.callee(num - 1);
}
}
那么如果用栈的方式如何处理呢？只需将给定的数递减到1入栈，然后每次s_pop的时候会返回栈顶元素，循环栈，然后将s_pop的值相乘即可，如下：
function factorial (num) {
if (typeof num !== 'number') return num;
let s = new Stack(),
facNum = 1;
//入栈
while (num > 0) {
s.s_push(num--);
}
//出栈
while (s.s_length() > 0) {
facNum *= s.s_pop();
}
return facNum;
}
2. 判断回文
先说下什么是回文，把相同的字符串或句子颠倒过来，产生首尾循环的句子，意思就是正序和倒叙的结果一样。如何使用栈的思想实现回文呢？
栈的方法有一个pop操作，每次pop返回栈顶元素。那么可以将字符串先push进栈，然后pop即可得到一个逆序的字符串，比较是否相等即可，如下：
function isPalindrome (str) {
const s = new Stack();
let reverseStr = '';
for (let i = 0; i < str.length; i++) {
s.s_push(str[i]);
}
while (s.s_length() > 0) {
reverseStr += s.s_pop();
}
return reverseStr === str;
}
总结
使用栈的思想可以很方便的实现很多功能，比如判断表达式是否括号匹配等？不过说实话，在前端页面的开发中，用不到这些。有兴趣可以玩下，可以提升思维逻辑。
