[[337051]]

本文轉載自微信公眾號「泰斗賢若如」，作者AhuntSun 。轉載本文請聯系泰斗賢若如公眾號。   

一、前言

1.1.什么是數據結構?

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

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

主要需要考慮兩個問題：

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

「常見的數據結構：」

• 「數組」(Aarray)
• 「棧」(Stack)
• 「鏈表」(Linked List)
• 「圖」(Graph)
• 「散列表」(Hash)
• 「隊列」(Queue)
• 「樹」(Tree)
• 「堆」(Heap)

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

1.2.什么是算法?

算法(Algorithm)的定義

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

算法通俗理解：解決問題的辦法/步驟邏輯。數據結構的實現，離不開算法。

二、棧結構(Stack)

2.1.簡介

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

image-20200226131817102

棧的特點為「先進后出，后進先出」(LIFO：last in first out)。

「程序中的棧結構：」

• 「函數調用棧」：A(B(C(D())))：即A函數中調用B，B調用C，C調用D;在A執行的過程中會將A壓入棧，隨后B執行時B也被壓入棧，函數C和D執行時也會被壓入棧。所以當前棧的順序為：A->B->C->D(棧頂);函數D執行完之后，會彈出棧被釋放，彈出棧的順序為D->C->B->A;
• 「遞歸」：為什么沒有停止條件的遞歸會造成棧溢出?比如函數A為遞歸函數，不斷地調用自己(因為函數還沒有執行完，不會把函數彈出棧)，不停地把相同的函數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()：移除棧頂的元素，同時返回被移除的元素;
• peek()：返回棧頂的元素，不對棧做任何修改(該方法不會移除棧頂的元素，僅僅返回它);
• isEmpty()：如果棧里沒有任何元素就返回true，否則返回false;
• size()：返回棧里的元素個數。這個方法和數組的length屬性類似;
• toString()：將棧結構的內容以字符串的形式返回。

2.2.封裝棧類

「代碼實現：」

// 封裝棧類 
    function Stack(){ 
      // 棧中的屬性 
      this.items =[] 
 
      // 棧的相關操作 
      // 1.push():將元素壓入棧 
      //方式一(不推薦)：給對象添加方法，其他對象不能復用 
      // this.push = () => { 
      // } 
       
      //方式二(推薦)：給Stack類添加方法，能夠多對象復用 
      Stack.prototype.push = function(element) { 
      // 利用數組item的push方法實現Stack類的pop方法 
        this.items.push(element) 
      } 
 
      // 2.pop():從棧中取出元素 
      Stack.prototype.pop = () => { 
      // 利用數組item的pop方法實現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類沒有length屬性啊)，而是           Stack類中定義的數組items才有length屬性呀 
        return this.items.length == 0  
      } 
 
      // 5.size():獲取棧中元素的個數 
      Stack.prototype.size = () => { 
        return this.items.length 
      } 
 
      // 6.toString():以字符串形式輸出棧內數據 
      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 

「測試結果：」

image-20200305205050816

「棧結構的簡單應用：」

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

//簡單應用： 
    //封裝函數：將十進制轉成二進制(十轉二的運算最后倒敘取余的特點符合棧'先進后出') 
    let dec2bin = decNumber => { 
      //1.定義一個棧對象，保存余數 
      var  stack = new Stack() 
 
      // 2.循環操作 
      while(decNumber > 0){ 
        // 2.1.獲取余數并放入棧中 
        stack.push(decNumber % 2) 
        // 2.2.獲取整除后的結果作為下一次運算的數字(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 

「測試結果：」

image-20200305205547226