棧（stack）是一種遵循后進(jìn)先出（Last In First Out, LIFO）的有序集合所構(gòu)成的數(shù)據(jù)結(jié)構(gòu)琅坡。
- 新添加或待刪除的元素保存在棧的末尾（棧頂），另一端叫做棧底亭螟。
- 在棧里挡鞍，新元素都靠近棧頂，就元素都接近棧底预烙。
棧
棧是和列表類似的一種高效的數(shù)據(jù)結(jié)構(gòu)匕累，由于數(shù)據(jù)只能在棧頂添加和刪除，所以增刪操作很快默伍。
- 棧是一種特殊的列表，棧內(nèi)的元素只能通過列表的一端訪問衰琐，此端稱為棧頂也糊。
入棧
后進(jìn)先出的棧中，任何不在棧頂?shù)脑囟紵o法訪問羡宙。為了得到棧底元素必須先拿掉上面的元素狸剃。
對(duì)棧的操作是將元素壓入棧（push）和彈出棧（pop）。
入棧和出棧
- 若要預(yù)覽棧頂元素狗热，pop方法雖然訪問棧頂元素钞馁，但調(diào)用后棧頂元素也從棧中被永久性地被刪除了。peek方法則只返回棧頂元素而不刪除它匿刮。
出棧
- 為了記錄棧頂元素的位置僧凰，同時(shí)也為了標(biāo)記哪里可以加入新元素，使用變量top熟丸，當(dāng)向棧內(nèi)壓入元素時(shí)训措，該變量變大；當(dāng)從棧內(nèi)彈出元素時(shí)光羞，該變量變小绩鸣。
top變量記錄棧頂元素的位置
棧的實(shí)現(xiàn)1
/*棧類*/
function Stack(){
this.data = [];//保存棧內(nèi)元素
this.top = 0;//記錄棧頂位置
this.push = push;
this.pop = pop;
this.peek = peek;
/*輔助方法*/
this.size = size;
this.clear = clear;
}
/*向棧中壓入新元素*/
function push(element){
this.data[this.top++] = element;
}
/*從棧中彈出棧頂元素*/
function pop(){
return this.data[--this.top];
}
/*預(yù)覽棧頂元素，空棧返回undefined*/
function peek(){
return this.data[this.top - 1];
}
/*獲取棧內(nèi)存儲(chǔ)的元素?cái)?shù)量*/
function size(){
return this.top;
}
/*清空棧*/
function clear(){
this.top = 0;
}
/*test*/
var stack = new Stack();
stack.push('David');
stack.push('Raymond');
stack.push('Bryan');
print(stack.size());//3
var poped = stack.pop();
print(poped, stack.peek());//Bryan Raymond
stack.clear();
print(stack.size());//0
數(shù)制間的相互轉(zhuǎn)換
將數(shù)字n轉(zhuǎn)換為b為基數(shù)的數(shù)字
- 最高位為n%b將此位壓入棧
- 使用n/b替換n
- 重復(fù)以上操作知道n等于0且沒有余數(shù)
- 持續(xù)將棧內(nèi)元素彈出知道棧為空纱兑，依次排列元素呀闻。
// 將數(shù)字轉(zhuǎn)化為二至九進(jìn)制的數(shù)字
function mulBase(number,base){
var stack = new Stack();
do{
stack.push(number % base);
number = Math.floor(number /= base);
}while(number>0);
var converted = '';
while(stack.size() > 0){
converted += stack.pop();
};
return converted;
}
print(mulBase(125,2), mulBase(124,8));//1111101 174
回文
回文是指這樣一種現(xiàn)象：一個(gè)單詞、短語或數(shù)字潜慎，從前往后寫和從后向前寫都是一樣的捡多。
- dad蓖康、racecar
- A man, a plan, a canal: Panama
- 1001
使用棧判斷一個(gè)字符串是否是回文，將字符串每個(gè)字符按從左到右的順序壓入棧局服。當(dāng)字符串中的字符都入棧后钓瞭，棧內(nèi)就保存了一個(gè)反轉(zhuǎn)后的字符串，最后的字符在棧頂淫奔，第一個(gè)字符在棧底山涡。
使用棧判斷一個(gè)單詞是否是回文
字符串完整壓入棧內(nèi)后，通過持續(xù)彈出棧中的每個(gè)字母就可以得到一個(gè)新的字符串唆迁，該字符串與原來的字符串順序相反鸭丛。最后僅需比較兩個(gè)字符串即可，若相等就是一個(gè)回文唐责。
function isPalindrom(word){
var stack = new Stack();
for(var i=0; i<word.length; ++i){
stack.push(word[i]);
}
var rword = "";
while(stack.size() > 0){
rword += stack.pop();
}
return word == rword;
}
print(isPalindrom("hello"), isPalindrom("racecar"));//false true
遞歸
棧通常用來實(shí)現(xiàn)編程語言鳞溉，使用棧實(shí)現(xiàn)遞歸即是一例。使用棧來模擬遞歸過程鼠哥，考慮求階乘函數(shù)的遞歸定義熟菲。
function factorial(n){
if(n === 0){
return 1;
}else{
return n*factorial(n-1);
}
}
function fact(n){
var stack = new Stack();
while(n>1){
stack.push(n--);
}
var product = 1;
while(stack.size()>0){
product *= stack.pop();
}
return product;
}
print(factorial(5), fact(5));//120 120
棧的實(shí)現(xiàn)2
function Stack(){
var items = [];//保存棧內(nèi)元素
/*添加一個(gè)或多個(gè)元素到棧頂*/
this.push = function(element){
items.push(element);
};
/*移除棧頂元素同時(shí)返回被移除的元素*/
this.pop = function(){
return items.pop();
};
/*預(yù)覽棧頂元素*/
this.peek = function(){
return items[items.length-1];
};
/*判斷棧中是否空棧，true為空棧無元素朴恳，false為有元素抄罕。*/
this.isEmpty = function(){
return items.length===0;
};
/*返回棧內(nèi)的元素個(gè)數(shù)*/
this.size = function(){
return items.length;
};
/*移除棧內(nèi)的所有元素*/
this.clear = function(){
items = [];
};
/*將棧內(nèi)元素輸出到控制臺(tái)*/
this.print = function(){
console.log(items.toString());
};
}
/*test*/
var stack = new Stack();
print(stack.isEmpty());//true
stack.push(5);
stack.push(8);
print(stack.peek());//8
stack.push(11);
print(stack.size(), stack.isEmpty());//3 false
stack.push(15);
入棧
stack.pop();
stack.pop();
print(stack.size());//2
stack.print();//5 8
出棧
十進(jìn)制轉(zhuǎn)二進(jìn)制
要把十進(jìn)制轉(zhuǎn)換成二進(jìn)制，可以將該十進(jìn)制數(shù)字和2整除（二進(jìn)制是逢二進(jìn)一）于颖，知道結(jié)果為0為止呆贿。
十進(jìn)制轉(zhuǎn)二進(jìn)制
function divideBy2(decnum){
var stack = new Stack();
var rem;
while(decnum > 0){
rem = Math.floor(decnum%2);//求模取余
stack.push(rem);
decnum = Math.floor(decnum/2);//商
}
var binary = '';
while(!stack.isEmpty()){
binary += stack.pop().toString();
}
return binary;
}
print(divideBy2(10));//1010
十進(jìn)制轉(zhuǎn)換成任何進(jìn)制
function baseConvert(decnum, base){
var stack = new Stack();
var rem;
while(decnum>0){
rem = Math.floor(decnum%base);
stack.push(rem);
decnum = Math.floor(decnum/base);
}
var basestr = "";
var digits = "0123456789ABCDEF";
while(!stack.isEmpty()){
basestr += digits[stack.pop()];
}
return basestr;
}
print(baseConvert(100345,2),baseConvert(100345,8),baseConvert(100345,16));//11000011111111001 303771 187F9
