JavaScript實現(xiàn)棧結構Stack過程詳解

更新時間：2020年03月07日 08:54:36 作者：AhuntSun

這篇文章主要介紹了JavaScript實現(xiàn)棧結構Stack過程詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下

JavaScript實現(xiàn)棧結構（Stack）

一、前言

1.1.

什么是數(shù)據(jù)結構？

數(shù)據(jù)結構就是在計算機中，存儲和組織數(shù)據(jù)的方式。

例如：圖書管理，怎樣擺放圖書才能既能放很多書，也方便??？

主要需要考慮兩個問題：

操作一：新書怎么插入？操作二：怎么找到某本指定的書？

常見的數(shù)據(jù)結構：

數(shù)組（Aarray）棧（Stack）鏈表（Linked List）圖（Graph）散列表（Hash）隊列（Queue）樹（Tree）堆（Heap）

注意：數(shù)據(jù)結構與算法與語言無關，常見的編程語言都有直接或間接的使用上述常見的數(shù)據(jù)結構。

1.2.什么是算法？

算法（Algorithm）的定義

一個有限指令集，每條指令的描述不依賴于語言；接收一些輸入（有些情況下不需要輸入）；產(chǎn)生輸入；一定在有限步驟之后終止；

算法通俗理解：解決問題的辦法/步驟邏輯。數(shù)據(jù)結構的實現(xiàn)，離不開算法。

二、棧結構（Stack）

2.1.簡介

數(shù)組是一個線性結構，并且可以在數(shù)組的任意位置插入和刪除元素。而棧和隊列就是比較常見的受限的線性結構。如下圖所示：

棧的特點為先進后出，后進先出（LIFO：last in first out）。

程序中的棧結構：

函數(shù)調(diào)用棧：A（B（C（D（））））：即A函數(shù)中調(diào)用B，B調(diào)用C，C調(diào)用D；在A執(zhí)行的過程中會將A壓入棧，隨后B執(zhí)行時B也被壓入棧，函數(shù)C和D執(zhí)行時也會被壓入棧。所以當前棧的順序為：A->B->C->D（棧頂）；函數(shù)D執(zhí)行完之后，會彈出棧被釋放，彈出棧的順序為D->C->B->A;

遞歸：為什么沒有停止條件的遞歸會造成棧溢出？比如函數(shù)A為遞歸函數(shù)，不斷地調(diào)用自己（因為函數(shù)還沒有執(zhí)行完，不會把函數(shù)彈出棧），不停地把相同的函數(shù)A壓入棧，最后造成棧溢出（Stack Overfloat）

3.練習：

題目：

有6個元素6，5，4，3，2，1按順序進棧，問下列哪一個不是合法的出棧順序？

A：5 4 3 6 1 2 （√）B：4 5 3 2 1 6 （√）C：3 4 6 5 2 1 （×）D：2 3 4 1 5 6 （√）

題目所說的按順序進棧指的不是一次性全部進棧，而是有進有出，進棧順序為6 -> 5 -> 4 -> 3 -> 2 -> 1。

解析：

A答案：65進棧，5出棧，4進棧出棧，3進棧出棧，6出棧，21進棧，1出棧，2出棧（整體入棧順序符合654321）;
B答案：654進棧，4出棧，5出棧，3進棧出棧，2進棧出棧，1進棧出棧，6出棧（整體的入棧順序符合654321）;
C答案：6543進棧，3出棧，4出棧，之后應該5出棧而不是6，所以錯誤；
D答案：65432進棧，2出棧，3出棧，4出棧，1進棧出棧，5出棧，6出棧。符合入棧順序；

棧常見的操作：

push（element）：添加一個新元素到棧頂位置；
pop（）：移除棧頂?shù)脑?，同時返回被移除的元素；
peek（）：返回棧頂?shù)脑兀粚Ｗ鋈魏涡薷模ㄔ摲椒ú粫瞥龡ｍ數(shù)脑?，僅僅返回它）；
isEmpty（）：如果棧里沒有任何元素就返回true，否則返回false；
size（）：返回棧里的元素個數(shù)。這個方法和數(shù)組的length屬性類似；
toString（）：將棧結構的內(nèi)容以字符串的形式返回。

2.2.封裝棧類

代碼實現(xiàn)：

 // 封裝棧類
  function Stack(){
   // 棧中的屬性
   this.items =[]

   // 棧的相關操作
   // 1.push():將元素壓入棧
   //方式一(不推薦)：給對象添加方法，其他對象不能復用
   // this.push = () => {
   // }
   
   //方式二(推薦)：給Stack類添加方法，能夠多對象復用
   Stack.prototype.push = function(element) {
   // 利用數(shù)組item的push方法實現(xiàn)Stack類的pop方法
    this.items.push(element)
   }

   // 2.pop():從棧中取出元素
   Stack.prototype.pop = () => {
   // 利用數(shù)組item的pop方法實現(xiàn)Stack類的pop方法
    return this.items.pop()
   }

   // 3.peek():查看一下棧頂元素
   Stack.prototype.peek = () => {
    return this.items[this.items.length - 1]
   }

   // 4.isEmpty():判斷棧是否為空
   Stack.prototype.isEmpty = () => {
   // 兩個小時的教訓啊不是this.length(不是Stack對象的length，Stack類沒有l(wèi)ength屬性啊)，而是      Stack類中定義的數(shù)組items才有l(wèi)ength屬性呀
    return this.items.length == 0 
   }

   // 5.size():獲取棧中元素的個數(shù)
   Stack.prototype.size = () => {
    return this.items.length
   }

   // 6.toString():以字符串形式輸出棧內(nèi)數(shù)據(jù)
   Stack.prototype.toString = () => {
    //希望輸出的形式：20 10 12 8 7
    let resultString = ''
    for (let i of this.items){
     resultString += i + ' '
    }
    return resultString
   }
  }

測試代碼：

 // 棧的使用
  let s = new Stack()
  s.push(20)
  s.push(10)
  s.push(100)
  s.push(77)
  console.log(s)                         //65
  console.log(s.pop());                      //68
  console.log(s.pop());                      //69
  
  console.log(s.peek());                     //71
  console.log(s.isEmpty());                    //72
  
  console.log(s.size());                     //74
  console.log(s.toString());                   //75

測試結果：

棧結構的簡單應用：

利用棧結構的特點封裝十進至轉換為二進至的函數(shù)：

  //簡單應用：
  //封裝函數(shù)：將十進制轉成二進制(十轉二的運算最后倒敘取余的特點符合棧'先進后出')
  let dec2bin = decNumber => {
   //1.定義一個棧對象，保存余數(shù)
   var stack = new Stack()

   // 2.循環(huán)操作
   while(decNumber > 0){
    // 2.1.獲取余數(shù)并放入棧中
    stack.push(decNumber % 2)
    // 2.2.獲取整除后的結果作為下一次運算的數(shù)字(floor:向下取整)
    decNumber = Math.floor(decNumber / 2)
   }

   // 3.從棧中取出0和1
   let binaryString = '';
   let a = stack.items.length
   while(stack.items.length != 0){
    binaryString += stack.pop();
   }
   return binaryString;
  }
  
  //測試代碼
  console.log(dec2bin(10));                    //103
  console.log(dec2bin(100));                   //104
  console.log(dec2bin(1000));                   //105

測試結果：