JS中的算法與數(shù)據(jù)結(jié)構(gòu)之棧(Stack)實(shí)例詳解

本文實(shí)例講述了JS中的算法與數(shù)據(jù)結(jié)構(gòu)之棧(Stack)。分享給大家供大家參考，具體如下：

棧(Stack)

上一篇我們說到了列表，它是一種最自然的數(shù)據(jù)組織方式，如果對數(shù)據(jù)的存儲順序要求不重要，那么列表就是一種非常適合的數(shù)據(jù)結(jié)構(gòu)，但對于計(jì)算機(jī)其他的一些應(yīng)用（比如后綴表達(dá)式），那么列表就顯得有些無能為力， 所以，我們需要一種和列表功能相似但更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。
棧，又叫堆棧，是和列表類似的一種數(shù)據(jù)結(jié)構(gòu)，但是卻更高效，因?yàn)闂?nèi)的元素只能通過列表的一端訪問，稱為棧頂，數(shù)據(jù)只能在棧頂添加或刪除，遵循 先入后出(LIFO，last-in-first-out) 的原則，普遍運(yùn)用于計(jì)算機(jī)的方方面面。
對棧的操作主要有兩種，一是將一個(gè)元素壓入棧，push方法，另一個(gè)就是將棧頂元素出棧，pop方法。
除此之外，棧還有其他的一些屬性和方法：查看當(dāng)前棧頂?shù)脑刂?，我們使?peek 方法，它僅僅返回棧頂元素值，并不刪除它；clear 方法用于清空當(dāng)前棧內(nèi)的所有元素；top屬性記錄當(dāng)前棧頂位置；length方法返回當(dāng)前棧內(nèi)元素總數(shù)等；接著我們定義棧的數(shù)據(jù)類型，并利用JS中的數(shù)組去實(shí)現(xiàn)它。

棧數(shù)據(jù)類型定義

棧的實(shí)現(xiàn)

//定義棧

function Stack () {
  this.dataStore = [];  //初始化為空
  this.top = 0;      //記錄棧頂位置
  this.pop = pop;     //出棧
  this.push = push;    //入棧
  this.peek = peek;    //查看棧頂元素
  this.length = length;  //查看棧內(nèi)元素總數(shù)
  this.clear = clear;   //清空棧
}

我們利用 dataStore 來保存棧內(nèi)元素，初始化為空數(shù)組，top 屬性用于記錄當(dāng)前棧頂位置，初始化的時(shí)候?yàn)?，

表示棧頂對應(yīng)數(shù)組的起始位置是0，如果有元素入棧，則該屬性會隨之反生變化。

首先我們先來實(shí)現(xiàn)第一個(gè)入棧方法。

push：向棧內(nèi)壓入一個(gè)新的元素

//該方法將一個(gè)新元素入棧，放到數(shù)組中 top 所對應(yīng)的位置上，并將 top 的值加 1，讓其指向數(shù)組的下一個(gè)空位置

function push( element ){
  this.dataStore[this.top++] = element;
}

能入棧，就得可以出棧，接著我們來看出棧方法：

pop：取出棧頂元素

//該方法與入棧相反，返回棧頂元素，并將 top 的值減 1

function pop(){
  return this.dataStore[--this.top];
}

如何查看棧頂元素呢，peek方法！

peek：查看棧頂元素

//該方法返回的是棧頂元素，即 top - 1 個(gè)位置元素

function peek(){
  if( this.top > 0 ) return this.dataStore[this.top-1];
  else return 'Empty';
}

這里我做了個(gè)判斷，如果一個(gè)空棧調(diào)用了 peek 方法，因?yàn)闂?nèi)沒有任何元素，所以我這里返回了一個(gè) 'Empty';
現(xiàn)在，我們已經(jīng)有了基本的入棧、出棧、查看棧頂元素的方法，我們不妨試一試。

//初始化一個(gè)棧
var stack = new Stack();
console.log( stack.peek() );  // Empty

//入棧
stack.push('Apple');
stack.push('Banana');
stack.push('Pear');

//查看當(dāng)前棧頂元素
console.log( stack.peek() );  // Pear
console.log( stack.pop() );   // Pear  

如果我放入了一些水果，吃掉了一個(gè)，我現(xiàn)在想知道我還剩多少個(gè)水果怎么辦？length 方法可以實(shí)現(xiàn)

length：返回棧內(nèi)元素總數(shù)

//該方法通過返回 top 屬性的值來返回棧內(nèi)總的元素個(gè)數(shù)

function length(){
  return this.top;
}

我們把代碼恢復(fù)到出棧前的狀態(tài)，也就是里面已經(jīng)放了三個(gè)水果，接著我們來看看

console.log( stack.length() );   // 3

//出棧
stack.pop();

console.log( stack.length() );   // 2

好了，我們還剩最后一個(gè)clear方法，我們來實(shí)現(xiàn)一下

clear：清空棧

//該方法實(shí)現(xiàn)很簡單，我們將 top 值置為 0 ， dataStore 數(shù)值清空即可

function clear(){
  delete this.dataStore;
  this.dataStore = [];
  this.top = 0;
}

我們將上面的棧清空試試

stack.clear();

console.log( stack.length() );   // 0
console.log( stack.peek() );    // Empty

至此，我們已經(jīng)可以用JS實(shí)現(xiàn)一個(gè)棧，但是你仍可能處于不知道如何正確使用的狀態(tài)，接下來，我們舉兩個(gè)例子，一起看看棧的使用。

案例1：實(shí)現(xiàn)數(shù)制間的相互轉(zhuǎn)換

我們可以利用棧將一個(gè)數(shù)字從一種數(shù)制轉(zhuǎn)換成另一種數(shù)制。例如將數(shù)字 n 轉(zhuǎn)換成以 b 為基數(shù)的數(shù)字，可以采用如下算法（該算法只針對基數(shù)為 2-9 的情況）：

最高位為 n % b ， 直接壓入棧;
使用 n / b 來代替 n ;
重復(fù)上面的步驟，知道 n 為 0 ，并且沒有余數(shù)；
以此將棧內(nèi)元素彈出，直到?？眨⒁来螌⑦@些元素排列，就得到了轉(zhuǎn)換后的形式

代碼如下：

//進(jìn)制轉(zhuǎn)換（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：判斷一個(gè)字符串是不是回文

回文是指一個(gè)字符串，從前往后寫和從后往前寫結(jié)果都是一樣的，比如單詞 'level' ， 'racecar'，就是回文，數(shù)字 1001 也是回文。
我們采用棧，可以很輕松判斷一個(gè)字符串是否是回文，實(shí)現(xiàn)算法很簡單，相信你們都猜到了。我們把字符串從左到右依次壓入棧，這樣，棧中保存了該字符串反轉(zhuǎn)后的字符，我們再依次出棧，通過比較出棧后的字符串是否與原字符串是否相等，就可判斷該字符串是否是回文。
具體代碼實(shí)現(xiàn)如下：

//回文判斷

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

本文主要講的是棧的運(yùn)用，所以采用上述方式判斷字符串是否是回文，實(shí)際上，你完全可以采用以下方式更方便的判斷一個(gè)字符串是否是回文：

function isPalindrome ( word ){
  return String(word).split('').reverse().join('') == word ? true : false;
}

到此，棧的內(nèi)容也基本告一段落，希望你能有所收獲，一起加油~

感興趣的朋友可以使用在線HTML/CSS/JavaScript代碼運(yùn)行工具：http://tools.jb51.net/code/HtmlJsRun測試上述代碼運(yùn)行效果。

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》

希望本文所述對大家JavaScript程序設(shè)計(jì)有所幫助。