什么是棧
棧就是和列表類似的一種數(shù)據(jù)結(jié)構(gòu)，它可用來解決計算機世界里的很多問題找蜜。棧是一種高 效的數(shù)據(jù)結(jié)構(gòu)，因為數(shù)據(jù)只能在棧頂添加或刪除稳析，所以這樣的操作很快洗做，而且容易實現(xiàn)。 棧的使用遍布程序語言實現(xiàn)的方方面面彰居，從表達式求值到處理函數(shù)調(diào)用诚纸。
棧是一種特殊的列表，棧內(nèi)的元素只能通過列表的一端訪問陈惰，這一端稱為棧頂畦徘。
棧被稱為一種后入先出(LIFO，last-in-first-out)的數(shù)據(jù)結(jié)構(gòu)抬闯。
棧的實現(xiàn)
在JavaScript中井辆，我們可以用如下函數(shù)實現(xiàn)棧：
function Stack(){
this.dataStore = []; //使用數(shù)組保存棧內(nèi)元素
this.top=0; //記錄棧頂位置，初始化為0
this.push = push; // 向棧中壓入一個新元素
this.pop = pop; // 從棧頂推出一個元素
this.peek = peek; // 返回棧頂元素
this.clear=clear; //清除棧
this.length=length;//返回棧的元素個數(shù)
}
//當向棧中壓入一個新元素時画髓，需要將其保存在數(shù)組中變量 top 所對 應的位置掘剪，
//然后將 top 值加 1，讓其指向數(shù)組中下一個空位置奈虾。
function push(element){
this.dataStore[this.top++]=element;
}
//它返回棧頂元素，同時將變量 top 的值減 1
function pop(){
return this.dataStore[--this.top];
}
//返回數(shù)組的第 top-1 個位置的元素，即棧頂元素:
function peek(){
return this.dataStore[this.top-1];
}
//通過返回變量 top 值的方式返回棧 內(nèi)的元素個數(shù)
function length(){
return this.top;
}
//清空一個棧
function clear(){
this.top = 0;
}
以下所有算法題目肉微，都是依據(jù)Stack函數(shù)的匾鸥。
實戰(zhàn)練習
習題一
利用棧將一個數(shù)字從一種數(shù)制轉(zhuǎn)換成另一種數(shù)制。假設想將數(shù)字 n 轉(zhuǎn)換為以 b 為基數(shù)
的數(shù)字碉纳，實現(xiàn)轉(zhuǎn)換的算法如下勿负。
(1) 最高位為 n % b，將此位壓入棧劳曹。
(2) 使用 n/b 代替 n奴愉。
(3) 重復步驟 1 和 2，直到 n 等于 0铁孵，且沒有余數(shù)锭硼。
(4) 持續(xù)將棧內(nèi)元素彈出，直到棧為空蜕劝，依次將這些元素排列檀头，就得到轉(zhuǎn)換后數(shù)字的字符
串形式。
此算法只針對基數(shù)為2～9的情況
代碼如下：
function mulBase(num, base) {
var s = new Stack();
do {
s.push(num % base);
num = Math.floor(num / base);
} while (num > 0)
var converted = "";
while (s.length() > 0) {
converted += s.pop();
}
return converted;
}
console.log(mulBase(32, 2)); // 100000
習題二
判斷給定字符串是否是回文
思路：
從左往右把字符串的每一個字符岖沛，依次放入棧中暑始，最后從棧的頂部往底部看去，就是一個反過來的字符串婴削。我們只要依次將字符串彈出廊镜，組成一個新的字符串，與原來的字符串進行比較即可唉俗。相等的話嗤朴，就是回文，反之互躬，不是回文播赁。
代碼如下：
function isPalindrome(word){
var s = new Stack();
for(var i=0;i<word.length;++i){
s.push(word[i]);
}
var newWord = '';
while(s.length()>0){
newWord += s.pop();
}
if(newWord === word){
return true;
}else{
return false;
}
}
console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("hello")); // false
習題三
使用棧來實現(xiàn)階乘函數(shù)
思路：
首先將數(shù)字從 num 到 1 壓入棧，然后使用一個循環(huán)吼渡，將數(shù)字挨
個彈出連乘容为，就得到了正確的答案
代碼如下：
function factorial(num){
var s = new Stack();
while(num>1){
s.push(num--);
}
var product = 1;
while(s.length()>0){
product *= s.pop();
}
return product;
}
console.log(factorial(5)); //120
習題三
用棧來判斷一個表達式中的括號（僅有一種括號,小、中或大括號）是否配對.編寫并實現(xiàn)它的算法.
思路:
function isMatch(str){
var s = new Stack;
var bracket = '';
for(var i=0;i<str.length;i++){
bracket = str[i];
if(bracket === "(" || bracket === "[" || bracket === "{"){
s.push(bracket)
}else if(bracket === ")" || bracket === "]" || bracket === "}") {
if(s.length()>0){
s.pop()
}else {
return '括號不匹配';
}
}
}
if(s.length()>0){
return '括號不匹配'
}
return '匹配';
}
console.log(isMatch('1+2*(2+1')); // 括號不匹配
console.log(isMatch('1+2*(2+1)')); // 匹配
console.log(isMatch('1+2*(2+1)+(2*2+1')); // 括號不匹配
console.log(isMatch('1+2*(2+1)+(2*2+1)')); // 匹配
習題四
現(xiàn)實生活中棧的一個例子是佩茲糖果盒寺酪。想象一下你有一盒佩茲糖果坎背，里面塞滿了紅 色、黃色和白色的糖果寄雀，但是你不喜歡黃色的糖果得滤。使用棧(有可能用到多個棧)寫一 段程序，在不改變盒內(nèi)其他糖果疊放順序的基礎上盒犹，將黃色糖果移出懂更。
思路
除了糖果盒眨业，還需要倆個棧。一個用來存放黃色糖果沮协，一個用來存放其他糖果龄捡。首先將糖果盒中的糖一個個彈出，壓入目標棧中慷暂。當糖果盒中的糖全都彈出后聘殖，把存放其他糖果的棧中的糖一個個彈出，壓入糖果盒中行瑞，這樣就得到想要的結(jié)果了奸腺。
代碼如下：
// 假設盒子中放著這些糖果
var sweetBox = new Stack();
sweetBox.push('yellow');
sweetBox.push('white');
sweetBox.push('yellow');
sweetBox.push('white');
sweetBox.push('red');
sweetBox.push('red');
sweetBox.push('yellow');
sweetBox.push('red');
sweetBox.push('yellow');
sweetBox.push('white');
console.log(sweetBox.dataStore);
function selectYellow(){
var yellow = new Stack(); //放置黃色糖果
var other = new Stack(); //放置其他糖果
var one = '';
while(sweetBox.length()>0){
var one = sweetBox.pop();
if(one === 'yellow'){
yellow.push(one);
}else{
other.push(one);
}
}
while(other.length()>0){
sweetBox.push(other.pop());
}
return sweetBox;
}
console.log(selectYellow().dataStore);
