读【数据结构与算法】之栈
栈是一种特殊的列表，栈内元素只能通过栈的一端访问，这个端就叫栈顶。栈被称为一种后入先出的数据结构。
栈有三个主要的方法：push， pop和peek。
实现一个栈，首先想到的存储数据是利用一个数组。
下边是简单实现：
/**
* Class Stack
* 栈 Stack
*/
function Stack() {
this.top = 0;
this._list = []; // 用于存储数据的数组
}
Stack.prototype = {
constructor: Stack,
/**
* 栈内元素个数
* @return {Number} 长度值
*/
length: function length() {
return this.top;
},
/**
* 清空栈
* @return {Undefined} undefined
*/
clear: function clear() {
this.top = 0;
},
/**
* 向栈中压入一个新元素
* @param {Any} element 新元素
* @return {Undefined} undefined
*/
push: function push(element) {
this._list[this.top++] = element;
},
/**
* 取出栈顶元素
* @return {Any} 栈顶元素
*/
pop: function pop() {
return this._list[--this.top];
},
/**
* 返回栈顶元素
* @return {Any} 栈顶元素
*/
peek: function peek() {
return this._list[this.top - 1];
}
};
一个有趣的例子就是利用栈来模拟计算阶乘的递归算法，递归写法很容易：
function fact(n) {
if (n === 0) {
return 1;
} else {
return n * fact(n - 1);
}
}
那用栈来做呢，也就是将每一个数字压入栈，然后一个一个的取出栈，相乘，结果就是：
function fact(n) {
var s = new Stack();
while (n > 1) {
s.push(n--);
}
var nn = 1;
while (s.length > 0) {
nn *= s.pop();
}
return nn;
}
具体运行例子请看demojs实现栈Stack