今天要來介紹的資料結構是堆疊。
我們可以用一疊書來做比喻堆疊,最一開始被放在桌上的書會被壓在最下面,而最後被放在書堆的書本則在書堆最上面。而當要拿書離開時,不能從中間抽書出來,必須從最上面的書開始拿取。
我們再用圖片來解釋一次:
我們可以把A~E的資料看成一本本書,A雖然最先被放入書堆,但是會等到最後才會被拿出來,這就是堆疊 先入後出(FILO, First-in-Last-out) 的特性。
而E最後被放入書堆,但會被最先拿出來,此為堆疊 後入先出(LIFO, Last-in-First-out) 的特性。
常見應用:
看完前面的介紹後,我們來實作堆疊吧!
我們使用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()
top為堆疊最上面的元素,如果它不存在就代表堆疊為空
isEmpty() {
return this.top === null
}
將要新增的值變成節點,讓新節點的指標指向原本的top節點,再讓新節點變成top節點,堆疊size加一
push(value) {
let node = new StackNode(value)
node.next = this.top
this.top = node
this.size++
}
邏輯相當簡單,將top下的那個元素換成堆疊的top就可以了,最後這個函式會回傳被pop出的值,堆疊size減一
pop() {
let result = this.top
this.top = this.top.next
this.size--
return result.data
}
回傳top的值即可
peek() {
return this.top.data
}
由於我們在建立LinkedStack類別時已經讓之後產生的物件有size大小的屬性,因此直接回傳此size值即可。
length() {
return this.size
}
也可以參考: Time and Space Complexity of Stack
和一般的 queue 差別在它每一個 element 都額外帶有優先值,愈優先的放在愈前面。分為最大優先佇列(max-priority Queue)與最小優先佇列(min-priority Queue)兩種。
應用:
本次實作的程式碼在此:
https://github.com/a90100/javascript-data-structure/blob/master/day6-stack-linked-list.js
堆疊的介紹就到這邊結束,明天我們將會運用學到的堆疊解決一個問題!