1、栈（Stack）是限定仅在表尾进行插入或删除操作的线性表。
2、表尾为栈顶（top），表头为栈底（bottom），不含元素的空表为空栈。
3、栈又称为后进先出（last in first out）的线性表。
栈的顺序存储结构
结构
1、用数组下标为0的一端作为栈底比较好，因为首元素都存在栈底，变化最小。
2、定义一个top变量来指示栈顶元素在数组中的位置。
3、若存储栈的长度为 StackSize，则栈顶位置 top 必须小于 StackSize。
4、当栈存在一个元素时，top 等于0。因此空栈的判定条件定为 top 等于 -1。
function Stack() {
this.dataStore = []; /* 用于储存栈元素的数组 */
this.top = -1; /* 用于栈顶指针 */
}
操作
Stack.prototype = {
constructor: Stack,
push : function (data) { /* 入栈方法 */
},
pop : function () { /* 出栈方法 */
},
peek: function () { /* 返回顶部的栈元素 */
},
clear: function () { /* 清除栈元素 */
},
length: function () { /* 返回栈元素个数 */
}
};
push方法实现
栈中向top位置插入元素后，top值更新，元素个数+1。
function push (data) {
this.dataStore[++this.top] = data;
}
pop方法实现
元素出栈，top值减1，指向当前栈顶元素下标位置，删除该元素作为出栈操作。
function pop() {
if(this.length() === 0){
return undefined;
}
var topvalue = this.dataStore[this.top];
delete this.dataStore[this.top--];
return topvalue;
}
peek方法实现
peek方法返回顶部的栈元素，即取dataStore的最后一个位置的值，也就是 dataStore 下标为 top-1 的值。
function peek() {
return this.dataStore[this.top];
}
clear方法实现
1、clear 方法清除栈内元素，把栈的长度重置为0。
2、另外还要把dataStore数组置空，因为数组中的元素始终被dataStore引用，导致垃圾回收器无法将其回收，从而造成内存浪费。
function clear () {
this.top = -1;
//下面两句任选其一清除数组dataStore里的数据
// this.dataStore = [];
this.dataStore.length = 0;
}
length 方法实现
length 方法获取栈中的元素个数。
function length() {
return 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, 栈的长度为：2 */
a.clear();
console.log("清除栈后dataStore为：" + a.dataStore + " 栈的长度为：" + a.length());
/* 输出：清除栈后dataStore为： 栈的长度为：0 */
栈的链式存储结构
结构
1、由于单链表有头指针，所以最好的办法就是把栈顶放在单链表的头部。
2、由于有栈顶在头部，单链表的头结点失去了意义，所以对于链栈来说，不需要头结点。
3、对于空栈的判定条件为 top = null 。
function Stack() {
this.top = null; /* 用于栈顶指针 */
this.length = 0; /* 用于表示栈的长度 */
}
操作
Stack.prototype = {
constructor: Stack,
push : function (element) { /* 入栈方法 */
},
pop : function () { /* 出栈方法 */
},
peek: function () { /* 返回顶部的栈元素 */
},
clear: function () { /* 清除栈元素 */
},
length: function () { /* 返回栈元素个数 */
}
};
push方法实现
栈中向top栈顶插入元素后，top值更新，元素个数+1。
function push (data) {
var node = {
data: data,
next: null
};
node.next = this.top;
this.top = node;
this.size++;
}
pop方法实现
元素出栈，size值减1，存储要删除的栈顶元素，将栈顶指针下移一位。
function pop() {
if (this.top === null)
return null;
var out = this.top;
this.top = this.top.next;
if (this.size > 0)
this.size--;
return out.data;
},
peek方法实现
peek方法返回顶部的栈元素。
function peek() {
return this.top === null ?
null :
this.top.data;
}
clear方法实现
clear 方法清除栈内元素，把栈的长度重置为0。
function clear () {
this.top = null;
this.size = 0;
}
length 方法实现
length 方法获取栈中的元素个数。
function length() {
return 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,2,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、规则：从左到右遍历中缀表达式的每个数字和符号：
- 若是数字就输出，即成为后缀表达式的一部分；
- 若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号（乘除优先加减）则栈顶元素一次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。
因此，要让计算机处理中缀表达式，最重要的就是两步：
- 将中缀表达式转化为后缀表达式（栈用来进出运算的符号）。
- 将后缀表达式进行运算得出结果（栈用来进出运算的数字）。
/**
* 优先级函数
* @param str
* @returns {number}
*/
function priority(str) {
switch (str) {
case '+' :
case '-' :
return 1;
break;
case '*' :
case '/':
return 2;
break;
case '(':
return 3;
break;
case ')':
return 4;
break;
default : /* 若为数字 */
return 0;
break;
}
}
/**
* 中缀表达式转后缀表达式函数：infix2Suffix()
* @param infix 中缀表达式字符串
* @returns {string} 后缀表达式字符串
*/
function infix2Suffix(infix) {
var out = ''; /* 保存输出的后缀表达式 */
var stack = new Stack();
for (var i = 0; i < infix.length; i++) {
if (priority(infix[i]) == 0) {
out += infix[i];
} else {
var peek = stack.peek();
if (!peek) { /* 栈为空 */
stack.push(infix[i]);
} else if (priority(infix[i]) == 4) { /* 遇到右括号 */
var tmp = stack.pop();
while (tmp != '(') {
out += tmp;
tmp = stack.pop();
}
} else if (priority(peek) <= priority(infix[i])) { /* 栈顶运算符的优先级不大于当前运算符，则直接进栈 */
stack.push(infix[i]);
} else if (priority(peek) > priority(infix[i])) {
/* 栈顶运算符的优先级大于当前运算符，则栈顶元素一次出栈并输出，并将当前符号进栈 */
var tmp = stack.pop();
while (priority(tmp) >= priority(infix[i]) || stack.length() != 0) {
if (priority(tmp) == 3) { /* 左括号优先级比‘+ - * /’高，但左括号只有遇到右括号才出栈 */
stack.push(tmp);
break;
}
out += tmp;
tmp = stack.pop()
}
stack.push(infix[i]);
}
}
}
while (stack.length() != 0) { /* 中缀表达式遍历完后，栈中运算符要全部出栈 */
var tmp = stack.pop();
if (tmp != '(') {
out += tmp;
}
}
return out;
}
/**
* 后缀表达式计算
* @param suffix
* @returns {number}
*/
function caculateSuffix(suffix) {
var result = 0;
var stack = new Stack();
for (var i = 0; i < suffix.length; i++) {
if (suffix[i].match(/\d/)) {
stack.push(suffix[i]);
} else {
var after = stack.pop(),
before = stack.pop();
switch (suffix[i]) {
case '+':
result = before * 1 + after * 1;
stack.push(result);
break;
case '-':
result = before * 1 - after * 1;
stack.push(result);
break;
case '*':
result = before * 1 * after * 1;
stack.push(result);
break;
case '/':
result = before * 1 / after * 1;
stack.push(result);
break;
}
}
}
result = stack.pop();
return result;
}
网友评论