重讀《學習JavaScript數據結構與演算法-第三版》- 第4章 棧

  • 2019 年 10 月 3 日
  • 筆記

定場詩

金山竹影幾千秋，雲索高飛水自流；  萬里長江飄玉帶，一輪銀月滾金球。  遠自湖北三千里，近到江南十六州；  美景一時觀不透，天緣有分畫中游。

前言

本章是重讀《學習JavaScript數據結構與演算法-第三版》的系列文章，本章為各位小夥伴分享數據結構-棧的故事，請讓胡哥帶你走進棧的世界

棧

何為棧？棧是一種遵從後進先出（LIFO）原則的有序集合。

新添加或待刪除的元素都保存在棧的同一端，稱作棧頂；另一端就叫棧底。

在棧里，新元素都靠近棧頂，舊元素都接近棧底。

基於數組的棧

我們將創建一個基於數組的棧，了解棧的結構、運行規則

/**   * 基於數組array的棧Stack   * @author huxiaoshuai   */  class Stack {    // 初始化    constructor () {      this.items = []    }  }

使用數組保存棧里的元素

數組允許我們在任何位置添加和刪除元素，那基於棧遵循LIFO原則，我們對元素的插入和刪除功能進行封裝

方法 描述
push(element(s)) 添加一個（或多個）新元素到棧頂
pop() 移除棧頂元素，同時返回被移除的元素
peek() 返回棧頂的元素，不對棧做任何修改
isEmpty() 判斷棧是否為空，為空則返回true，否則返回false
clear() 移除棧的所有元素
size() 返回棧的元素個數

程式碼實現

class Stack {    // 初始化    constructor () {      this.items = []    }      /**     * push() 添加元素到棧頂     */    push (element) {      this.items.push(element)    }      /**     * pop() 移除棧頂元素並返回     */    pop () {      return this.items.pop()    }      /**     * peek() 返回棧頂部元素     */    peek () {      return this.items[this.items.length - 1]    }      /***     * isEmpty() 檢測棧是否為空     */    isEmpty () {      return this.items.length === 0    }      /**     * size() 返回棧的長度     */    size () {      return this.items.length    }      /**     * clear() 清空棧元素     */    clear () {      this.items = []    }  }

使用Stack類

const stack = new Stack()    console.log(stack.isEmpty()) // true    // 添加元素  stack.push(5)  stack.push(8)    // 輸出元素  console.log(stack.peek()) // 8    stack.push(11)  console.log(stack.size()) // 3  console.log(stack.isEmpty()) // false    stack.push(15)

基於以上棧操作的示意圖
基於以上棧操作的示意圖

stack.pop()  stack.pop()  console.log(stack.size()) // 2

基於以上棧操作的示意圖
基於以上棧操作的示意圖

基於對象的棧

創建一個Stack類最簡單的方式是使用一個數組來存儲元素。在處理大量數據的時候，我們同樣需要評估如何操作數據是最高效的。

使用數組時，大部分方法的時間複雜度是O(n)。簡單理解：O(n)的意思為我們需要迭代整個數組直到找到要找的那個元素，在最壞的情況下需要迭代數組的所有位置，其中的n代表數組的長度。數組越長，所需時間會更長。另外，數組是元素的一個有序集合，為保證元素的有序排列，會佔用更多的記憶體空間。

使用JavaScript對象來存儲所有的棧元素，以實現可以直接獲取元素，同時佔用較少的記憶體空間，同時保證所有的元素按照我們的需要進行排列，遵循後進先出（LIFO）原則。

程式碼實現

/**   * 基於對象的Stack類   * @author huxiaoshai   */  class Stack {    // 初始化    constructor () {      this.items = {}      this.count = 0    }      /**     * push() 向棧中添加元素     */    push (element) {      this.items[this.count] = element      this.count++    }      /**     * isEmpty() 判斷是否為空     */    isEmpty () {      return this.count === 0    }      /**     * size() 返回棧的長度     */    size () {      return this.count    }      /**     * pop() 棧頂移除元素並返回     */    pop () {      if (this.isEmpty()) {        return undefined      }      this.count--      let result = this.items[this.count]      delete this.items[this.count]      return result    }      /**     * peek() 返回棧頂元素，如果為空則返回undefined     */    peek () {      if (this.isEmpty()) {        return undefined      }      return this.items[this.count - 1]    }      /**     * clear() 清空棧數據     */    clear () {      this.items = {}      this.count = 0    }      /**     * toString() 實現類似於數組結構列印棧內容     */    toString () {      if (this.isEmpty()) {        return ''      }      let objStr = `${this.items[0]}`      for (let i = 1; i < this.count; i++) {        objStr = `${objStr},${this.items[i]}`      }      return objStr    }  }

保護數據結構內部元素

私有屬性

有時候我們需要創建供其他開發者使用的數據結構和對象時，我們希望保存內部元素，只有使用允許的方法才能修改內部結構。很不幸，目前JS是沒有辦法直接聲明私有屬性的，目前業內主要使用一下幾種方式實現私有屬性。

  1. 下劃線命名約定

    class Stack {    constructor () {      this._items = {}      this._count = 0    }  }

    這只是約定，一種規範，並不能實際保護數據

  2. 基於ES6的限定作用域Symbol實現類

    const _items = Symbol('stackItems')  class Stack {    constructor () {      this[_items] = []    }  }

    假的私有屬性，ES6新增的Object.getOwnPropertySymbols方法能夠獲取類裡面聲明的所有Symbols屬性

  3. 基於ES6的WeakMap實現類

    /**   * 使用WeekMap實現類的私有屬性   */  const items = new WeakMap()  console.log(items) // WeakMap { [items unknown] }    class Stack {    constructor () {      items.set(this, [])    }      push (element) {      const s = items.get(this)      s.push(element)    }      pop () {      const s = items.get(this)      const r = s.pop()      return r    }      toString () {      const s = items.get(this)      return s.toString()    }  }    const stack = new Stack()  stack.push(1)  stack.push(2)  stack.push(3)    console.log(stack.toString()) // 1,2,3  console.log(stack.items) // undefined

    使用該方式，items是Stack類里的私有屬性，但是此種方式程式碼的可讀性不強，而且在擴展該類時無法繼承私有屬性。

  4. ECMAScript類屬性提案

    有一個關於JavaScript類中增加私有屬性的提案。通過在屬性前添加井號(#)作為前綴來聲明私有屬性。

class Stack {    #count = 0    #items = []  }

使用棧來解決問題

棧的實際應用非常廣泛。在回溯問題中，它可以存儲訪問過的任務或路徑、撤銷的操作（後續會在討論圖和回溯問題時進一步詳細講解）。棧的使用場景有很多，如漢諾塔問題、平衡圓括弧、電腦科學問題：十進位轉二進位問題

/**   * decimalToBinary() 實現十進位轉二進位的演算法   */  function decimalToBinary (decNumber) {    // 實例化棧數據結構    const remStack = new Stack()    let number = decNumber    let rem;    let binaryString = ''      // 依次將獲取的二進位數壓入棧中    while (number > 0) {      rem = Math.floor(number % 2)      remStack.push(rem)      number = Math.floor(number / 2)    }    // 拼接要輸出的二進位字元串    while (!remStack.isEmpty()) {      binaryString += remStack.pop().toString()    }    return binaryString  }    console.log(decimalToBinary(10)) // 1010  console.log(decimalToBinary(23)) // 10111

後記

以上就是胡哥今天給大家分享的內容，喜歡的小夥伴記得收藏、轉發、點擊右下角按鈕在看，推薦給更多小夥伴呦，歡迎多多留言交流…

胡哥有話說，一個有技術，有情懷的胡哥！京東開放平台首席前端攻城獅。與你一起聊聊大前端，分享前端系統架構，框架實現原理，最新最高效的技術實踐！

長按掃碼關注，更帥更漂亮呦！關注胡哥有話說公眾號，可與胡哥繼續深入交流呦！

胡哥有話說

VirMach 便宜 VPS

QNews

QNews