iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 6
3

今天要來介紹的資料結構是堆疊
我們可以用一疊書來做比喻堆疊,最一開始被放在桌上的書會被壓在最下面,而最後被放在書堆的書本則在書堆最上面。而當要拿書離開時,不能從中間抽書出來,必須從最上面的書開始拿取。

我們再用圖片來解釋一次:

我們可以把A~E的資料看成一本本書,A雖然最先被放入書堆,但是會等到最後才會被拿出來,這就是堆疊 先入後出(FILO, First-in-Last-out) 的特性。
而E最後被放入書堆,但會被最先拿出來,此為堆疊 後入先出(LIFO, Last-in-First-out) 的特性。

接著來介紹幾個堆疊的常見操作方法,待會我們將會實做這些函式:

  • 推入 push():將資料放入堆疊頂端,堆疊頂端移到新放入的資料。
  • 彈出 pop():將堆疊頂端資料移除,堆疊頂端移到移除後的下一筆資料。
  • peek(): 查出堆疊最上方的元素
  • size(): 查出堆疊共有幾個元素
  • isEmpty(): 是否堆疊內無元素

常見應用:

  • 網頁瀏覽器的「回到前一頁」功能,最先瀏覽的頁面會在最後一此點到前一頁按鈕時才出現
  • 河內塔(搭配遞迴)
  • 可以用 Stack 寫深度優先搜尋演算法(Depth-First-Search,DFS)

看完前面的介紹後,我們來實作堆疊吧!
我們使用linked list來做出堆疊。

先寫出基本結構,建立LinkedStack的類別,並用new 建立stack物件

class StackNode {
  constructor(data, next) {
    this.data = data
    this.next = next
  }
}

class LinkedStack {
  constructor() {
    this.top = null
    this.size = 0
  }

  // 判斷空堆疊
  isEmpty() {

  }

  // 堆疊長度
  length() {

  }

  // 新增堆疊元素
  push(value) {

  }

  // 刪除堆疊元素
  pop() {

  }

  // 查看堆疊最上面元素
  peek() {

  }
}

let stack = new LinkedStack()

完成 isEmpty() 方法:

top為堆疊最上面的元素,如果它不存在就代表堆疊為空

isEmpty() {
  return this.top === null
}

完成 push() 方法:

將要新增的值變成節點,讓新節點的指標指向原本的top節點,再讓新節點變成top節點,堆疊size加一

push(value) {
  let node = new StackNode(value)
  node.next = this.top
  this.top = node
  this.size++
}

完成 pop() 方法:

邏輯相當簡單,將top下的那個元素換成堆疊的top就可以了,最後這個函式會回傳被pop出的值,堆疊size減一

pop() {
  let result = this.top
  this.top = this.top.next
  this.size--
  return result.data
}

完成 peek() 方法:

回傳top的值即可

peek() {
  return this.top.data
}

完成 length() 方法:

由於我們在建立LinkedStack類別時已經讓之後產生的物件有size大小的屬性,因此直接回傳此size值即可。

length() {
  return this.size
}

堆疊的時間複雜度

也可以參考: Time and Space Complexity of Stack

  • push: O(1)
  • pop: O(1)
  • search: O(n)
  • peek: O(1)

Priority Queue 優先權佇列

和一般的 queue 差別在它每一個 element 都額外帶有優先值,愈優先的放在愈前面。分為最大優先佇列(max-priority Queue)與最小優先佇列(min-priority Queue)兩種。

應用:

  • 動態尋找最佳或最差的元素
  • Huffman Coding,資料壓縮

本次實作的程式碼在此:
https://github.com/a90100/javascript-data-structure/blob/master/day6-stack-linked-list.js

堆疊的介紹就到這邊結束,明天我們將會運用學到的堆疊解決一個問題!


上一篇
Day5-陣列(Array)和鏈結串列(Linked List)的比較
下一篇
Day7-利用堆疊解決"平衡括號"問題
系列文
使用JavaScript學習資料結構與演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言