数据结构与算法 （栈实现篇）
在数据结构与算法中，栈(stack)又名堆栈，栈是一种受限的线性储存结构，只允许在一端加入元素和删除元素。这一端称为栈顶，加入元素称作入栈、压栈、进栈；删除元素又称作出栈、退栈。被删除元素的相邻元素会重新称为栈顶元素。栈遵循先进后出（FILO）的规则。
栈结构示意图
stack.png
栈结构使用
在编程语言中很多时候使用到栈的数据结构。例如函数栈结构。A函数调用B函数，B函数调用了C函数。语言执行先会把A函数、B函数、C函数依次进栈；待C函数执行完成出栈，B函数出栈，最后A函数完成出栈。
function.png
生活中具有比较多的类似于栈的结构，比如叠罗汉、子弹夹、文件叠在一起等等。理解栈结构原理对我们编程具有很大的帮助。下面会使用 JavaScript实现我们的栈结构。
实现栈结构的功能
- push(element)：push是进栈操作，其中element是需要进栈的元素，返回操作成功与否布尔值。
- pop()：pop移除栈顶元素操作，返回移除的栈顶元素。
- size()：获取栈中的栈元素数量，返回一个数字。
- isEmpty()：判断栈是否为空，返回一个布尔值。
- peek()：返回栈顶元素，但不移除栈顶元素。
- bottom()：返回栈底元素。
- clear()：清除所有栈元素，返回操作成功与否布尔值。
进栈与出栈流程
flow.png
ES6 栈结构代码
class Stack{
constructor(){
this.lists = [];
}
size(){
return this.lists.length;
}
isEmpty(){
return this.lists.length === 0;
}
peek(){
const topIndex = this.size() -1;
return this.lists[topIndex];
}
bottom(){
return this.list[0];
}
push(element){
this.lists.push(element);
return true;
}
pop(){
return this.lists.pop();
}
clear(){
this.lists = [];
return true;
}
toString(){
let result = "";
this.lists.forEach(value=>{
result = result + ""+value;
});
return result;
}
}
ES5 栈结构代码
通过ES5把功能函数可以绑定在对象的实例上，也可以把功能函数加在函数的原型链上
function Stack(){
this.lists = [];
}
Stack.prototype.push = function(element){
this.lists.push(element);
return true;
}
Stack.prototype.pop = function(){
return this.lists.pop();
}
Stack.prototype.clear = function(){
this.lists = [];
return true;
}
Stack.prototype.peek = function(){
var topIndex = this.size() -1;
return this.lists[topIndex];
}
Stack.prototype.size = function(){
return this.lists.length;
}
Stack.prototype.isEmpty = function(){
return this.lists.length === 0;
}
Stack.prototype.bottom = function(){
return this.lists[0];
}
Stack.prototype.toString = function(){
var result = "";
for(var i=0;i<this.lists.length;i++){
result = result + '' +this.lists[i];
}
return result;
}
ES5和ES6实现栈结构已经通过了测试可运行。上面是通过数组实现的栈结构，其实链表也可以实现栈结构。下面数据结构链表篇会使用链表实现栈的数据结构
