1、栈（Stack）是限定仅在表尾进行插入或删除操作的线性表。
2、表尾为栈顶（top），表头为栈底（bottom），不含元素的空表为空栈。
3、栈又称为后进先出（last in first out）的线性表。
栈的顺序存储结构
结构
1、用数组下标为0的一端作为栈底比较好，因为首元素都存在栈底，变化最小。
2、定义一个top变量来指示栈顶元素在数组中的位置。
3、若存储栈的长度为 StackSize，则栈顶位置 top 必须小于 StackSize。
4、当栈存在一个元素时，top 等于0。因此空栈的判定条件定为 top 等于 -1。
@H_301_16@function Stack() {
@H_301_16@this.dataStore = []; /* 用于储存栈元素的数组 */
@H_301_16@this.top = -1; /* 用于栈顶指针 */
}
操作
Stack.prototype = {
constructor: Stack,push : @H_301_16@function (data) { /* 入栈方法 */
},pop : @H_301_16@function () { /* 出栈方法 */
},peek: @H_301_16@function () { /* 返回顶部的栈元素 */
},clear: @H_301_16@function () { /* 清除栈元素 */
},length: @H_301_16@function () { /* 返回栈元素个数 */
}
};
push方法实现
栈中向top位置插入元素后，top值更新，元素个数+1。
@H_301_16@function push (data) {
@H_301_16@this.dataStore[++@H_301_16@this.top] = data;
}
pop方法实现
元素出栈，top值减1，指向当前栈顶元素下标位置，删除该元素作为出栈操作。
@H_301_16@function pop() {
@H_301_16@var topvalue = @H_301_16@this.dataStore[@H_301_16@this.top];
@H_301_16@delete @H_301_16@this.dataStore[@H_301_16@this.top--];
@H_301_16@return topvalue;
}
peek方法实现
peek方法返回顶部的栈元素，即取dataStore的最后一个位置的值，也就是 dataStore 下标为 top-1 的值。
@H_301_16@function peek() {
@H_301_16@return @H_301_16@this.dataStore[@H_301_16@this.top];
}
clear方法实现
1、clear 方法清除栈内元素，把栈的长度重置为0。
2、另外还要把dataStore数组置空，因为数组中的元素始终被dataStore引用，导致垃圾回收器无法将其回收，从而造成内存浪费。
@H_301_16@function clear () {
@H_301_16@this.top = -1;
//下面两句任选其一清除数组dataStore里的数据
// this.dataStore = [];
@H_301_16@this.dataStore.length = 0;
}
length 方法实现
@H_301_16@function length() {
@H_301_16@return @H_301_16@this.top+1;
}
测试代码
var a = new Stack();
a.push(1);
a.push(2);
a.push(3);
console.log("开始的dataStore为：" + a.dataStore + " 栈的长度为：" + a.length());
/* 输出：开始的dataStore为：1,2,3 栈的长度为：3 */
a.pop();
console.log("出栈一个值后dataStore为：" + a.dataStore + " 栈的长度为：" + a.length());
/* 输出：出栈一个值后dataStore为：1,栈的长度为：2 */
a.clear();
console.log("清除栈后dataStore为：" + a.dataStore + " 栈的长度为：" + a.length());
/* 输出：清除栈后dataStore为： 栈的长度为：0 */
栈的链式存储结构
结构
1、由于单链表有头指针，所以最好的办法就是把栈顶放在单链表的头部。
2、由于有栈顶在头部，单链表的头结点失去了意义，所以对于链栈来说，不需要头结点。
3、对于空栈的判定条件为 top = null 。
@H_301_16@function Stack() {
@H_301_16@this.top = null; /* 用于栈顶指针 */
@H_301_16@this.length = 0; /* 用于表示栈的长度 */
}
操作
Stack.prototype = {
constructor: Stack,push : @H_301_16@function (element) { /* 入栈方法 */
},length: @H_301_16@function () { /* 返回栈元素个数 */
}
};
push方法实现
栈中向top栈顶插入元素后，top值更新，元素个数+1。
@H_301_16@function push (data) {
@H_301_16@var node = {
data: data,next: null
};
node.next = @H_301_16@this.top;
@H_301_16@this.top = node;
@H_301_16@this.size++;
}
pop方法实现
元素出栈，size值减1，存储要删除的栈顶元素，将栈顶指针下移一位。
@H_301_16@function pop() {
@H_301_16@if (@H_301_16@this.top === null)
@H_301_16@return null;
@H_301_16@var out = @H_301_16@this.top;
@H_301_16@this.top = @H_301_16@this.top.next;
@H_301_16@if (@H_301_16@this.size > 0)
@H_301_16@this.size--;
@H_301_16@return out.data;
},
peek方法实现
@H_301_16@function peek() {
@H_301_16@return @H_301_16@this.top === null ?
null :
@H_301_16@this.top.data;
}
clear方法实现
clear 方法清除栈内元素，把栈的长度重置为0。
@H_301_16@function clear () {
@H_301_16@this.top = null;
@H_301_16@this.size = 0;
}
length 方法实现
@H_301_16@function length() {
@H_301_16@return @H_301_16@this.size;
}
测试代码
/* 给链栈增加一个展示函数 */
function displayAll(){
if (this.top === null)
return null;
var arr = [];
var current = this.top;
for (var i = 0,len = this.size; i < len; i++) {
arr[i] = current.data;
current = current.next;
}
return arr;
}
var a = new Stack();
a.push(1);
a.push(2);
a.push(3);
console.log("开始的dataStore为：" + a.displayAll()+ " 栈的长度为：" + a.length());
/* 输出：开始的栈为：3,1 栈的长度为：3 */
a.pop();
console.log("出栈一个值后dataStore为：" + a.displayAll()+ " 栈的长度为：" + a.length());
/* 输出：出栈一个值后栈为：2,1 栈的长度为：2 */
a.clear();
console.log("清除栈后dataStore为：" + a.displayAll()+ " 栈的长度为：" + a.length());
/* 输出：清除栈后栈为： 栈的长度为：0 */
栈的应用
四则运算表达式求值
后缀（逆波兰）表示法
1、不需要括号的后缀表示，所有的符号在运算数字的后面出现。
2、规则：从左到右遍历表达式的每个数字和符号：
- 遇到是数字就进栈；
- 遇到是符号，就将处于栈顶的两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。
中缀表达式转后缀表达式
1、中缀表达式：平时所用的标准四则运算表达式。
2、规则：从左到右遍历中缀表达式的每个数字和符号：
- 若是数字就输出，即成为后缀表达式的一部分；
- 若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号（乘除优先加减）则栈顶元素一次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。
因此，要让计算机处理中缀表达式，最重要的就是两步：
- 将中缀表达式转化为后缀表达式（栈用来进出运算的符号）。
- 将后缀表达式进行运算得出结果（栈用来进出运算的数字）。
