溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了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 的值減 1
function 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() ); // Pear
console.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() ); // 0 console.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 ) ); // 1111101
console.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') ) // true
console.log( isPalindrome('1001') ) // true
console.log( isPalindrome('word') ) // false
本文主要講的是棧的運用，所以采用上述方式判斷字符串是否是回文，實際上，你完全可以采用以下方式更方便的判斷一個字符串是否是回文：
function isPalindrome ( word ){
return String(word).split('').reverse().join('') == word ? true : false;
}
到此，棧的內容也基本告一段落，希望你能有所收獲，一起加油~
感興趣的朋友可以使用在線HTML/CSS/JavaScript代碼運行工具：http://tools.jb51.net/code/HtmlJsRun測試上述代碼運行效果。
更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數學運算用法總結》、《JavaScript數據結構與算法技巧總結》、《JavaScript數組操作技巧總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》
希望本文所述對大家JavaScript程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
