1、棧（Stack）是限定僅在表尾進(jìn)行插入或刪除操作的線性表。
2、表尾為棧頂（top），表頭為棧底（bottom），不含元素的空表為空棧。
3、棧又稱為后進(jìn)先出（last in first out）的線性表。
棧的順序存儲結(jié)構(gòu)
結(jié)構(gòu)
1、用數(shù)組下標(biāo)為0的一端作為棧底比較好，因?yàn)槭自囟即嬖跅５?，變化最小?br>
2、定義一個top變量來指示棧頂元素在數(shù)組中的位置。
3、若存儲棧的長度為 StackSize，則棧頂位置 top 必須小于 StackSize。
4、當(dāng)棧存在一個元素時，top 等于0。因此空棧的判定條件定為 top 等于 -1。
function Stack() {
this.dataStore = []; /* 用于儲存棧元素的數(shù)組 */
this.top = -1; /* 用于棧頂指針 */
}
操作
Stack.prototype = {
constructor: Stack,
push : function (data) { /* 入棧方法 */
},
pop : function () { /* 出棧方法 */
},
peek: function () { /* 返回頂部的棧元素 */
},
clear: function () { /* 清除棧元素 */
},
length: function () { /* 返回棧元素個數(shù) */
}
};
push方法實(shí)現(xiàn)
棧中向top位置插入元素后，top值更新，元素個數(shù)+1。
function push (data) {
this.dataStore[++this.top] = data;
}
pop方法實(shí)現(xiàn)
元素出棧，top值減1，指向當(dāng)前棧頂元素下標(biāo)位置，刪除該元素作為出棧操作。
function pop() {
if(this.length() === 0){
return undefined;
}
var topvalue = this.dataStore[this.top];
delete this.dataStore[this.top--];
return topvalue;
}
peek方法實(shí)現(xiàn)
peek方法返回頂部的棧元素，即取dataStore的最后一個位置的值，也就是 dataStore 下標(biāo)為 top-1 的值。
function peek() {
return this.dataStore[this.top];
}
clear方法實(shí)現(xiàn)
1、clear 方法清除棧內(nèi)元素，把棧的長度重置為0。
2、另外還要把dataStore數(shù)組置空，因?yàn)閿?shù)組中的元素始終被dataStore引用，導(dǎo)致垃圾回收器無法將其回收，從而造成內(nèi)存浪費(fèi)。
function clear () {
this.top = -1;
//下面兩句任選其一清除數(shù)組dataStore里的數(shù)據(jù)
// this.dataStore = [];
this.dataStore.length = 0;
}
length 方法實(shí)現(xiàn)
length 方法獲取棧中的元素個數(shù)。
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 */
棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)
結(jié)構(gòu)
1、由于單鏈表有頭指針，所以最好的辦法就是把棧頂放在單鏈表的頭部。
2、由于有棧頂在頭部，單鏈表的頭結(jié)點(diǎn)失去了意義，所以對于鏈棧來說，不需要頭結(jié)點(diǎn)。
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 () { /* 返回棧元素個數(shù) */
}
};
push方法實(shí)現(xiàn)
棧中向top棧頂插入元素后，top值更新，元素個數(shù)+1。
function push (data) {
var node = {
data: data,
next: null
};
node.next = this.top;
this.top = node;
this.size++;
}
pop方法實(shí)現(xiàn)
元素出棧，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方法實(shí)現(xiàn)
peek方法返回頂部的棧元素。
function peek() {
return this.top === null ?
null :
this.top.data;
}
clear方法實(shí)現(xiàn)
clear 方法清除棧內(nèi)元素，把棧的長度重置為0。
function clear () {
this.top = null;
this.size = 0;
}
length 方法實(shí)現(xiàn)
length 方法獲取棧中的元素個數(shù)。
function length() {
return this.size;
}
測試代碼
/* 給鏈棧增加一個展示函數(shù) */
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 */
棧的應(yīng)用
四則運(yùn)算表達(dá)式求值
后綴（逆波蘭）表示法
1、不需要括號的后綴表示，所有的符號在運(yùn)算數(shù)字的后面出現(xiàn)。
2、規(guī)則：從左到右遍歷表達(dá)式的每個數(shù)字和符號：
- 遇到是數(shù)字就進(jìn)棧；
- 遇到是符號，就將處于棧頂?shù)膬蓚€數(shù)字出棧，進(jìn)行運(yùn)算，運(yùn)算結(jié)果進(jìn)棧，一直到最終獲得結(jié)果。
中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式
1、中綴表達(dá)式：平時所用的標(biāo)準(zhǔn)四則運(yùn)算表達(dá)式。
2、規(guī)則：從左到右遍歷中綴表達(dá)式的每個數(shù)字和符號：
- 若是數(shù)字就輸出，即成為后綴表達(dá)式的一部分；
- 若是符號，則判斷其與棧頂符號的優(yōu)先級，是右括號或優(yōu)先級不高于棧頂符號（乘除優(yōu)先加減）則棧頂元素一次出棧并輸出，并將當(dāng)前符號進(jìn)棧，一直到最終輸出后綴表達(dá)式為止。
因此，要讓計(jì)算機(jī)處理中綴表達(dá)式，最重要的就是兩步：
- 將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式（棧用來進(jìn)出運(yùn)算的符號）。
- 將后綴表達(dá)式進(jìn)行運(yùn)算得出結(jié)果（棧用來進(jìn)出運(yùn)算的數(shù)字）。
/**
* 優(yōu)先級函數(shù)
* @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 : /* 若為數(shù)字 */
return 0;
break;
}
}
/**
* 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式函數(shù)：infix2Suffix()
* @param infix 中綴表達(dá)式字符串
* @returns {string} 后綴表達(dá)式字符串
*/
function infix2Suffix(infix) {
var out = ''; /* 保存輸出的后綴表達(dá)式 */
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])) { /* 棧頂運(yùn)算符的優(yōu)先級不大于當(dāng)前運(yùn)算符，則直接進(jìn)棧 */
stack.push(infix[i]);
} else if (priority(peek) > priority(infix[i])) {
/* 棧頂運(yùn)算符的優(yōu)先級大于當(dāng)前運(yùn)算符，則棧頂元素一次出棧并輸出，并將當(dāng)前符號進(jìn)棧 */
var tmp = stack.pop();
while (priority(tmp) >= priority(infix[i]) || stack.length() != 0) {
if (priority(tmp) == 3) { /* 左括號優(yōu)先級比‘+ - * /’高，但左括號只有遇到右括號才出棧 */
stack.push(tmp);
break;
}
out += tmp;
tmp = stack.pop()
}
stack.push(infix[i]);
}
}
}
while (stack.length() != 0) { /* 中綴表達(dá)式遍歷完后，棧中運(yùn)算符要全部出棧 */
var tmp = stack.pop();
if (tmp != '(') {
out += tmp;
}
}
return out;
}
/**
* 后綴表達(dá)式計(jì)算
* @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;
}
