如需轉(zhuǎn)載, 請(qǐng)咨詢作者, 并且注明出處.
有任何問題, 可以關(guān)注我的微博: coderwhy, 或者添加我的微信: 372623326

棧也是一種非常常見的數(shù)據(jù)結(jié)構(gòu), 并且在程序中的應(yīng)用非常廣泛.

一. 認(rèn)識(shí)棧結(jié)構(gòu)

我們先來簡(jiǎn)單認(rèn)識(shí)一下棧結(jié)構(gòu), 它的特點(diǎn)和應(yīng)用場(chǎng)景等.

棧結(jié)構(gòu)

• 數(shù)組

  • 我們知道數(shù)組是一種線性結(jié)構(gòu), 并且可以在數(shù)組的任意位置插入和刪除數(shù)據(jù).
  • 但是有時(shí)候, 我們?yōu)榱藢?shí)現(xiàn)某些功能, 必須對(duì)這種任意性加以限制.
  • 而棧和隊(duì)列就是比較常見的受限的線性結(jié)構(gòu), 我們先來學(xué)習(xí)棧結(jié)構(gòu).

• 棧（stack）账千，它是一種運(yùn)算受限的線性表,后進(jìn)先出(LIFO)

  • LIFO(last in first out)表示就是后進(jìn)入的元素, 第一個(gè)彈出椊拿桑空間. 類似于自動(dòng)餐托盤, 最后放上的托盤, 往往先把拿出去使用.
  • 其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算暗膜。這一端被稱為棧頂，相對(duì)地鞭衩，把另一端稱為棧底学搜。
  • 向一個(gè)棧插入新元素又稱作進(jìn)棧、入椔垩埽或壓棧瑞佩，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素坯台；
  • 從一個(gè)棧刪除元素又稱作出椌嫱瑁或退棧，它是把棧頂元素刪除掉蜒蕾，使其相鄰的元素成為新的棧頂元素稠炬。

• 生活中類似于棧的

  • 自助餐的托盤, 最新放上去的, 最先被客人拿走使用.
  • 收到很多的郵件(實(shí)體的), 從上往下依次處理這些郵件. (最新到的郵件, 最先處理)
  • 注意: 不允許改變郵件的次序, 比如從最小開始, 或者處于最緊急的郵件, 否則就不再是棧結(jié)構(gòu)了. 而是隊(duì)列或者優(yōu)先級(jí)隊(duì)列結(jié)構(gòu).

• 棧結(jié)構(gòu)的圖解

  img

• 程序中什么是使用棧實(shí)現(xiàn)的呢?

  • 學(xué)了這么久的編程, 是否聽說過, 函數(shù)調(diào)用棧呢?
  • 我們知道函數(shù)之間和相互調(diào)用: A調(diào)用B, B中又調(diào)用C, C中又調(diào)用D.
  • 那樣在執(zhí)行的過程中, 會(huì)先將A壓入棧, A沒有執(zhí)行完, 所有不會(huì)彈出棧.
  • 在A執(zhí)行的過程中調(diào)用了B, 會(huì)將B壓入到棧, 這個(gè)時(shí)候B在棧頂, A在棧底.
  • 如果這個(gè)時(shí)候B可以執(zhí)行完, 那么B會(huì)彈出棧. 但是B有執(zhí)行完嗎? 沒有, 它調(diào)用了C.
  • 所以C會(huì)壓棧, 并且在棧頂. 而C調(diào)用了D, D會(huì)壓入到棧頂.
  • 所以當(dāng)前的棧順序是: 棧頂A->B->C->D棧頂
  • D執(zhí)行完, 彈出棧. C/B/A依次彈出棧.
  • 所以我們有函數(shù)調(diào)用棧的稱呼, 就來自于它們內(nèi)部的實(shí)現(xiàn)機(jī)制. (通過棧來實(shí)現(xiàn)的)

• 函數(shù)調(diào)用棧圖解:

  img

棧面試題

• 面試題目:

  img

• 題目答案: C

  • A答案: 65進(jìn)棧, 5出棧, 4進(jìn)棧出棧, 3進(jìn)棧出棧, 6出棧, 21進(jìn)棧,1出棧, 2出棧
  • B答案: 654進(jìn)棧, 4出棧, 5出棧, 3進(jìn)棧出棧, 2進(jìn)棧出棧, 1進(jìn)棧出棧, 6出棧
  • D答案: 65432進(jìn)棧, 2出棧, 3出棧, 4出棧, 1進(jìn)棧出棧, 5出棧, 6出棧

二. 棧結(jié)構(gòu)實(shí)現(xiàn)

我們來實(shí)現(xiàn)一個(gè)類, 用于模擬棧中的操作.

棧的創(chuàng)建

• 我們先來創(chuàng)建一個(gè)棧的類, 用于封裝棧相關(guān)的操作

  // 棧類
  function Stack() {
      // 棧中的屬性
      var items = []
      
      // 棧相關(guān)的方法
  }
  

• 代碼解析:

  • 我們創(chuàng)建了一個(gè)Stack構(gòu)造函數(shù), 用戶創(chuàng)建棧的類.
  • 在構(gòu)造函數(shù)中, 定義了一個(gè)變量, 這個(gè)變量可以用于保存當(dāng)前棧對(duì)象中所有的元素.
  • 這個(gè)變量是一個(gè)數(shù)組類型. 我們之后無論是壓棧操作還是出棧操作, 都是從數(shù)組中添加和刪除元素.
  • 棧有一些相關(guān)的操作方法, 通常無論是什么語言, 操作都是比較類似的.

棧的操作

• 棧常見有哪些操作呢?

  • push(element): 添加一個(gè)新元素到棧頂位置.
  • pop()：移除棧頂?shù)脑兀瑫r(shí)返回被移除的元素咪啡。
  • peek()：返回棧頂?shù)脑厥灼簦粚?duì)棧做任何修改（這個(gè)方法不會(huì)移除棧頂?shù)脑兀瑑H僅返回它）撤摸。
  • isEmpty()：如果棧里沒有任何元素就返回true毅桃，否則返回false褒纲。
  • clear()：移除棧里的所有元素。
  • size()：返回棧里的元素個(gè)數(shù)钥飞。這個(gè)方法和數(shù)組的length屬性很類似莺掠。

• 現(xiàn)在我們來實(shí)現(xiàn)這些方法:

• push方法

  • 注意: 我們的實(shí)現(xiàn)是將最新的元素放在了數(shù)組的末尾, 那么數(shù)組末尾的元素就是我們的棧頂元素

  // 壓棧操作
  this.push = function (element) {
      items.push(element)
  }
  

• pop方法

  • 注意: 出棧操作應(yīng)該是將棧頂?shù)脑貏h除, 并且返回.
  • 因此, 我們這里直接從數(shù)組中刪除最后一個(gè)元素, 并且將該元素返回就可以了

  // 出棧操作
  this.pop = function (element) {
      return items.pop()
  }
  

• peek方法

  • peek方法是一個(gè)比較常見的方法, 主要目的是看一眼棧頂?shù)脑?
  • 注意: 和pop不同, peek僅僅的瞥一眼棧頂?shù)脑? 并不需要將這個(gè)元素從棧頂彈出.

  // peek操作
  this.peek = function () {
      return items[items.length - 1]
  }
  

• isEmpty方法

  • isEmpty方法用戶判斷棧中是否有元素.
  • 實(shí)現(xiàn)起來非常簡(jiǎn)單, 直接判斷數(shù)組中的元素個(gè)數(shù)是為0, 為0返回true, 否則返回false

  // 判斷棧中的元素是否為空
  this.isEmpty = function () {
      return items.length == 0
  }
  

• size方法

  • size方法是獲取棧中元素的個(gè)數(shù).
  • 因?yàn)槲覀兪褂玫氖菙?shù)組來作為棧的底層實(shí)現(xiàn)的, 所以直接獲取數(shù)組的長(zhǎng)度即可.(也可以使用鏈表作為棧的頂層實(shí)現(xiàn))

  // 獲取棧中元素的個(gè)數(shù)
  this.size = function () {
      return items.length
  }
  

完整代碼

• 下面我們給出自定義棧的完整代碼:

  • 注意: 這里我們?yōu)榱藢傩苑椒ǚ旁谝黄? 沒有使用原型來封裝方法.

  // 棧類
  function Stack() {
      // 棧中的屬性
      var items = []
  
      // 棧相關(guān)的方法
      // 壓棧操作
      this.push = function (element) {
          items.push(element)
      }
  
      // 出棧操作
      this.pop = function () {
          return items.pop()
      }
  
      // peek操作
      this.peek = function () {
          return items[items.length - 1]
      }
  
      // 判斷棧中的元素是否為空
      this.isEmpty = function () {
          return items.length == 0
      }
  
      // 獲取棧中元素的個(gè)數(shù)
      this.size = function () {
          return items.length
      }
  }
  

棧的使用

• 我們來使用封裝的棧, 模擬剛才的面試題

  • 我們做了一下A, 其他大家可以自己練習(xí)一下.
  • C是無法使用棧來模擬的, 因?yàn)椴徽_的是C

  // 模擬面試題
  var stack = new Stack()
  
  // 情況下代碼模擬
  stack.push(6)
  stack.push(5)
  stack.pop()     // 5
  stack.push(4)
  stack.pop()     // 4
  stack.push(3)
  stack.pop()     // 3
  stack.pop()     // 6
  stack.push(2)
  stack.push(1)
  stack.pop()     // 1
  stack.pop()     // 2
  

三. 棧結(jié)構(gòu)應(yīng)用

我們已經(jīng)學(xué)會(huì)了如何使用Stack類，現(xiàn)在就用它解決一些計(jì)算機(jī)科學(xué)中的問題读宙。

十進(jìn)制轉(zhuǎn)二進(jìn)制

• 為什么需要十進(jìn)制轉(zhuǎn)二進(jìn)制?

  • 現(xiàn)實(shí)生活中汁蝶，我們主要使用十進(jìn)制。
  • 但在計(jì)算科學(xué)中论悴，二進(jìn)制非常重要掖棉，因?yàn)橛?jì)算機(jī)里的所有內(nèi)容都是用二進(jìn)制數(shù)字表示的（0和1）。
  • 沒有十進(jìn)制和二進(jìn)制相互轉(zhuǎn)化的能力膀估，與計(jì)算機(jī)交流就很困難幔亥。

• 如何實(shí)現(xiàn)十進(jìn)制轉(zhuǎn)二進(jìn)制?

  • 要把十進(jìn)制轉(zhuǎn)化成二進(jìn)制，我們可以將該十進(jìn)制數(shù)字和2整除（二進(jìn)制是滿二進(jìn)一）察纯，直到結(jié)果是0為止帕棉。

  • 舉個(gè)例子，把十進(jìn)制的數(shù)字10轉(zhuǎn)化成二進(jìn)制的數(shù)字饼记，過程大概是這樣：

    img

• 如果我們希望使用代碼來實(shí)現(xiàn)這個(gè)功能呢?

  // 封裝十進(jìn)制轉(zhuǎn)二進(jìn)制的函數(shù)
  function dec2bin(decNumer) {
      // 定義變量
      var stack = new Stack()
      var remainder;
  
      // 循環(huán)除法
      while (decNumer > 0) {
          remainder = decNumer % 2
          decNumer = Math.floor(decNumer / 2)
          stack.push(remainder)
      }
  
      // 將數(shù)據(jù)取出
      var binayriStrng = ""
      while (!stack.isEmpty()) {
          binayriStrng += stack.pop()
      }
      return binayriStrng
  }
  

• 測(cè)試代碼:

  // 測(cè)試函數(shù)
  alert(dec2bin(10))
  alert(dec2bin(233))
  alert(dec2bin(1000))