JS數據結構學習：棧

Alfred 發布于2019-08-26 13:28 / 1268人閱讀

摘要：棧的應用前面介紹了那么多棧相關的知識，最后也是介紹棧的應用場景的時候了，棧的實際應用非常廣泛，例如用來存儲訪問過的任務或路徑撤銷的操作。

棧的定義

什么是棧？棧是一種遵循后進先出原則的有序集合，新添加的或者待刪除的元素都保存在棧的同一端，稱為棧頂，另一端稱為棧底，在棧里，新元素靠近棧頂，舊元素靠近棧底，用個圖來看大概這樣式的：

用一個更形象的例子來說明：上網的時候，每點擊一個超鏈接，瀏覽器都會打開一個新的頁面，并且壓入到一個訪問歷史棧中，你可以不斷的點擊打開新的頁面，但總是可以通過回退重新訪問以前的頁面，從瀏覽器的訪問歷史棧中彈出歷史網頁地址，從棧頂彈出，總是最新的最先彈出

棧的創建

首先創建一個類用來表示棧，接著聲明一個數組用來保存棧里的元素：

function Stack() {
  let items = []
  // 方法聲明
}

創建好棧之后，需要為棧聲明一些方法，棧一般會包含以下幾個方法：

push(): 添加新元素到棧頂

pop(): 移除棧頂的元素，同時返回被移除的元素

peek(): 返回棧頂的元素，不對棧做任何修改

isEmpty(): 如果棧里沒有任何元素就返回true，否則返回false

clear(): 移除棧里的所有元素

size(): 返回棧里的元素個數

具體實現：

function Stack() {
  let items = []
  // 添加元素到棧頂，也就是棧的末尾
  this.push = function (element) {
    items.push(element)
  }
  // 棧的后進先出原則，從棧頂出棧
  this.pop = function () {
    return items.pop()
  }
  // 查看棧頂的元素，訪問數組最后一個元素
  this.peek = function () {
    return items[items.length - 1]
  }
  // 檢查棧是否為空
  this.isEmpty = function () {
    return items.length == 0
  }
  // 返回棧的長度，棧的長度就是數組的長度
  this.size = function () {
    return items.length
  }
  // 清空棧 
  this.clear = function () {
    items = []
  }
  // 打印棧元素
  this.print = function () {
    console.log(items.toString())
  }
}

棧的使用

現在我們來看如何使用棧：

let stack = new Stack()
stack.push(1)
stack.push(2)
stack.push(3)
console.log(stack.peek()) // 3
console.log(stack.isEmpty()) // false
console.log(stack.size()) // 3

先向棧中加入三個元素1，2，3，接下來用一張圖來看一下入棧的過程：

入棧過程都是在棧頂依次入棧，接著調用peek方法返回棧頂元素3，isEmpty返回false，size返回棧的長度3，然后在繼續調用pop來看看出棧的過程：

stack.pop()
stack.print() // 1,2

出棧也是和入棧相同，都是從棧頂開始出棧，保證棧的后入先出原則

es6聲明Stack類

上面創建了一個Stack函數來充當類，并且在里面聲明了一個私有變量，但是在es6里面是有類的語法的，可以直接用es6新語法來聲明，代碼大概是這樣事的：

class Stack {
  constructor () {
    this.items = []
  }
  push (element) {
    this.items.push(element)
  }
  pop () {
    return this.items.pop()
  }
  peek () {
    return this.items[items.length - 1]
  }
  isEmpty () {
    return this.items.length == 0
  }
  size () {
    return this.items.length
  }
  clear () {
    this.items = []
  }
  print () {
    console.log(this.items.toString())
  }
}
let stack = new Stack()
stack.push(1)
console.log(stack.isEmpty())
stack.print()

看起來似乎不錯，比之前要簡單，關鍵是看起來更加合理，使用的是類的語法，調用也沒有什么問題，但是如果這么執行呢？

console.log(stack.items)

會發現一個問題，在stack類外面可以直接訪問類里面的屬性，按照設計items應該是Stack類的私有屬性才對，就像之前Stack函數里面的私有變量，是不能在外部訪問的，如何才能將items變成私有屬性呢？應該會有和我一樣想法的人，使用閉包，在閉包里面里面定義私有屬性，然后再將stack類返回回來，代碼實現大概是這樣的：

let Stack = (function () {
  let items = new WeakMap()
  class Stack {
    constructor () {
      items.set(this, [])
    }
    push (element) {
      let s = items.get(this)
      s.push(element)
    }
    pop () {
      let s = items.get(this)
      return s.pop()
    }
    peek () {
      let s = items.get(this)
      return s[s.length - 1]
    }
    isEmpty () {
      let s = items.get(this)
      return s.length == 0
    }
    size () {
      let s = items.get(this)
      return s.length
    }
    clear () {
      let s = items.get(this)
      s = []
    }
    print () {
      let s = items.get(this)
      console.log(s.toString())
    }
  }
  return Stack
})()

可能有人會問為什么這里要把items定義成一個WeakMap對象，先簡單介紹一下WeakMap對象的用法，WeakMap對象是一對鍵/值對的集合，其鍵必須是對象，值可以是任意的，定義成WeakMap就是為了將items屬性變成私有屬性，在外部調用Stack對象的時候無法訪問到items屬性。

棧的應用

前面介紹了那么多棧相關的知識，最后也是介紹棧的應用場景的時候了，棧的實際應用非常廣泛，例如用來存儲訪問過的任務或路徑、撤銷的操作。為了有一個更直觀的應用了解，下面會介紹如何用來解決計算機中的進制轉換問題，將10進制轉換為其他進制數，可能不少人已經忘了如何進行進制轉換了，下面先來看一個簡單的10進制轉2進制的過程:

上面的圖中展示將一個10進制8轉化為2進制數的過程，接下來看看用棧是如何實現的：

function conver(num, radix) {
  let stack = new Stack()
  let binaryString = ""
  let digits = "0123456789ABCDEF"
  while (num > 0) {
    stack.push(num % radix)
    num = parseInt(num / radix)
  }
  while (!stack.isEmpty()) {
    binaryString += digits[stack.pop()]
  }
  console.log(binaryString)
}
conver(8, 2) // 1000

總結

這篇文章主要對棧做了簡單介紹，動手實踐了棧的實現，以及用棧實現了一個簡單進制轉換的功能。如果有錯誤或不嚴謹的地方，歡迎批評指正，如果喜歡，歡迎點贊。

云服務器 GPU云服務器 js技術棧 JS調用棧 js遞歸棧溢出 js數組棧方法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/108885.html

我對JS棧的簡單學習

摘要：我對棧的學習因為是個新手，所以都是最簡單的知識學習梳理。棧是一種遵從后進先出原則的有序集合，新添加的或者待刪除的元素都保留在棧的末尾，稱作棧頂，另一端叫做棧底。棧的學習棧的創建創建一個類來表示棧。對于棧來說只能用和方法來進行添加和刪除元素。我對棧的學習因為是個新手，所以都是最簡單的知識學習梳理。什么是棧數組是計算機科學中最常用的數據結構，是數據元素的集合。有時候我們需要一種添加...

Cobub 2019-08-21 11:36 評論0 收藏0
JS 棧

摘要：棧學習數據結構與算法讀書筆記。棧又名堆棧，是一種遵循后進先出原則的有序集合。新添加或待刪除的元素都保存在棧的末尾，稱作棧頂，另一端稱作棧底。在棧里，新元素都靠近棧頂，舊元素都接近棧底。棧《學習JavaScript數據結構與算法》讀書筆記。棧（stack）又名堆棧，是一種遵循后進先出（LIFO）原則的有序集合。新添加或待刪除的元素都保存在棧的末尾，稱作棧頂，另一端稱作棧底。在棧里，...

Lin_R 2019-08-22 10:35 評論0 收藏0
全棧開發：2017年你最好的選擇[翻譯]

摘要：全棧開發是一個學習實現提高的過程。解除對開發人員的限制所有的職業都在持續的進化。哪怕是爆炸和擁擠的印度招聘市場，全棧工程師在年也非常的搶手。印度的創業公司已經開發意識到全棧工程師的重要意義，全棧會越來越重要。在不斷壯大的招聘市場上，最需要的是有非常廣泛技術棧的人。前言敬愛的讀者，大家好。大家經常討論的話題是作為一個軟件工程師是一個持續學習的過程。因為現有的趨勢和技術在軟件領域會很...

fireflow 2019-07-25 11:32 評論0 收藏0
全棧開發：2017年你最好的選擇[翻譯]

摘要：全棧開發是一個學習實現提高的過程。解除對開發人員的限制所有的職業都在持續的進化。哪怕是爆炸和擁擠的印度招聘市場，全棧工程師在年也非常的搶手。印度的創業公司已經開發意識到全棧工程師的重要意義，全棧會越來越重要。在不斷壯大的招聘市場上，最需要的是有非常廣泛技術棧的人。前言敬愛的讀者，大家好。大家經常討論的話題是作為一個軟件工程師是一個持續學習的過程。因為現有的趨勢和技術在軟件領域會很...

aisuhua 2019-08-20 14:32 評論0 收藏0
全棧開發：2017年你最好的選擇[翻譯]

摘要：全棧開發是一個學習實現提高的過程。解除對開發人員的限制所有的職業都在持續的進化。哪怕是爆炸和擁擠的印度招聘市場，全棧工程師在年也非常的搶手。印度的創業公司已經開發意識到全棧工程師的重要意義，全棧會越來越重要。在不斷壯大的招聘市場上，最需要的是有非常廣泛技術棧的人。前言敬愛的讀者，大家好。大家經常討論的話題是作為一個軟件工程師是一個持續學習的過程。因為現有的趨勢和技術在軟件領域會很...

selfimpr 2019-07-25 13:51 評論0 收藏0