本文實例講述了JS中的算法與數據結構之棧(Stack)。分享給大家供大家參考，具體如下：
棧(Stack)
上一篇我們說到了列表，它是一種最自然的數據組織方式，如果對數據的存儲順序要求不重要，那么列表就是一種非常適合的數據結構，但對于計算機其他的一些應用（比如后綴表達式），那么列表就顯得有些無能為力， 所以，我們需要一種和列表功能相似但更復雜的數據結構。
棧，又叫堆棧，是和列表類似的一種數據結構，但是卻更高效，因為棧內的元素只能通過列表的一端訪問，稱為棧頂，數據只能在棧頂添加或刪除，遵循 先入后出(LIFO，last-in-first-out) 的原則，普遍運用于計算機的方方面面。
對棧的操作主要有兩種，一是將一個元素壓入棧，push方法，另一個就是將棧頂元素出棧，pop方法。
除此之外，棧還有其他的一些屬性和方法：查看當前棧頂的元素值，我們使用 peek 方法，它僅僅返回棧頂元素值，并不刪除它；clear 方法用于清空當前棧內的所有元素；top屬性記錄當前棧頂位置；length方法返回當前棧內元素總數等；接著我們定義棧的數據類型，并利用JS中的數組去實現它。
棧數據類型定義
棧的實現
//定義棧function Stack () { this.dataStore = []; //初始化為空 this.top = 0; //記錄棧頂位置 this.pop = pop; //出棧 this.push = push; //入棧 this.peek = peek; //查看棧頂元素 this.length = length; //查看棧內元素總數 this.clear = clear; //清空棧}我們利用 dataStore 來保存棧內元素，初始化為空數組，top 屬性用于記錄當前棧頂位置，初始化的時候為0，
表示棧頂對應數組的起始位置是0，如果有元素入棧，則該屬性會隨之反生變化。
首先我們先來實現第一個入棧方法。
push：向棧內壓入一個新的元素
//該方法將一個新元素入棧，放到數組中 top 所對應的位置上，并將 top 的值加 1，讓其指向數組的下一個空位置function push( element ){ this.dataStore[this.top++] = element;}能入棧，就得可以出棧，接著我們來看出棧方法：
pop：取出棧頂元素
//該方法與入棧相反，返回棧頂元素，并將 top 的值減 1function pop(){ return this.dataStore[--this.top];}如何查看棧頂元素呢，peek方法！
peek：查看棧頂元素
//該方法返回的是棧頂元素，即 top - 1 個位置元素function peek(){ if( this.top > 0 ) return this.dataStore[this.top-1]; else return 'Empty';}這里我做了個判斷，如果一個空棧調用了 peek 方法，因為棧內沒有任何元素，所以我這里返回了一個 'Empty';
現在，我們已經有了基本的入棧、出棧、查看棧頂元素的方法，我們不妨試一試。
//初始化一個棧var stack = new Stack();console.log( stack.peek() ); // Empty//入棧stack.push('Apple');stack.push('Banana');stack.push('Pear');//查看當前棧頂元素console.log( stack.peek() ); // Pearconsole.log( stack.pop() ); // Pear 如果我放入了一些水果，吃掉了一個，我現在想知道我還剩多少個水果怎么辦？length 方法可以實現
length：返回棧內元素總數
//該方法通過返回 top 屬性的值來返回棧內總的元素個數function length(){ return this.top;}我們把代碼恢復到出棧前的狀態，也就是里面已經放了三個水果，接著我們來看看
console.log( stack.length() ); // 3//出棧stack.pop();console.log( stack.length() ); // 2
好了，我們還剩最后一個clear方法，我們來實現一下
clear：清空棧
//該方法實現很簡單，我們將 top 值置為 0 ， dataStore 數值清空即可function clear(){ delete this.dataStore; this.dataStore = []; this.top = 0;}我們將上面的棧清空試試
stack.clear();console.log( stack.length() ); // 0console.log( stack.peek() ); // Empty
至此，我們已經可以用JS實現一個棧，但是你仍可能處于不知道如何正確使用的狀態，接下來，我們舉兩個例子，一起看看棧的使用。
案例1：實現數制間的相互轉換
我們可以利用棧將一個數字從一種數制轉換成另一種數制。例如將數字 n 轉換成以 b 為基數的數字，可以采用如下算法（該算法只針對基數為 2-9 的情況）：
最高位為 n % b ， 直接壓入棧;
使用 n / b 來代替 n ;
重復上面的步驟，知道 n 為 0 ，并且沒有余數；
以此將棧內元素彈出，直到棧空，并依次將這些元素排列，就得到了轉換后的形式
代碼如下：
//進制轉換（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( 125 , 2 ) ); // 1111101console.log( mulBase( 125 , 8 ) ); // 175案列2：判斷一個字符串是不是回文
回文是指一個字符串，從前往后寫和從后往前寫結果都是一樣的，比如單詞 'level' ， 'racecar'，就是回文，數字 1001 也是回文。
我們采用棧，可以很輕松判斷一個字符串是否是回文，實現算法很簡單，相信你們都猜到了。我們把字符串從左到右依次壓入棧，這樣，棧中保存了該字符串反轉后的字符，我們再依次出棧，通過比較出棧后的字符串是否與原字符串是否相等，就可判斷該字符串是否是回文。
具體代碼實現如下：
//回文判斷function isPalindrome ( word ) { var s = new Stack(); for( var i = 0 ; i < word.length ; i ++ ){ s.push( word[i] ); } var rword = ''; while( s.length() > 0 ){ rword += s.pop(); } if( word == rword ){ return true; }else{ return false; }}console.log( isPalindrome('level') ) // trueconsole.log( isPalindrome('1001') ) // trueconsole.log( isPalindrome('word') ) // false本文主要講的是棧的運用，所以采用上述方式判斷字符串是否是回文，實際上，你完全可以采用以下方式更方便的判斷一個字符串是否是回文：
function isPalindrome ( word ){ return String(word).split('').reverse().join('') == word ? true : false;}到此，棧的內容也基本告一段落，希望你能有所收獲，一起加油~
感興趣的朋友可以使用在線HTML/CSS/JavaScript代碼運行工具：http://tools.VeVB.COm/code/HtmlJsRun測試上述代碼運行效果。
更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數學運算用法總結》、《JavaScript數據結構與算法技巧總結》、《JavaScript數組操作技巧總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》
希望本文所述對大家JavaScript程序設計有所幫助。
新聞熱點
疑難解答
