資料結構筆記:堆疊與佇列

考量到文章長度,把資料結構的部分分拆成不同文章,雖然標題是演算法,其實內容介紹資料結構比較多。上課之前不太清楚演算法跟資料結構的關係,上課後有更深一步的感想,看到題目以後需要選擇用哪種資料結構解題,此資料結構又有哪些方法可以使用,才能夠將效率最大化。

Stack 堆疊

結構:

function Stack() {
  let items = []; // 我們這邊使用陣列 array 的方式來儲存堆疊內的元素
}

特性:
插入、刪除需時 O(1) 。搜尋需時 O(N) 。

方法:

  • Push(data):把資料放進Stack,O(1) 。
  • Pop:把「最上面」的資料從Stack中移除,O(1) 。除了最上面的資料可以使用Top()來讀取,無法得知Stack裡面還有其餘哪些資料。要知道Stack裡的所有資料,只能靠Pop(),把資料一個一個拿出來檢查,O(n) 。
  • Top:回傳「最上面」的資料,不影響資料結構本身,O(1) 。
  • IsEmpty:確認Stack裡是否有資料,不影響資料結構本身 ,O(1) 。
  • getSize:回傳Stack裡的資料個數,不影響資料結構本身,O(n)。
cc

圖一。

以圖一為例,一開始Stack是空的:

  • Push(6)後,便把66放入Stack。並用一個稱為top的變數,記錄Stack最上面的資料為何,在此即為66。
  • Push(3)Push(7)後,便把3、73、7放入Stack。並更新top,使其記錄77。
  • Pop()後,便把Stack中「最上面」的資料(77)給移除,所以Stack中剩下6、36、3,並更新top記錄33。
  • Push(14)Push(8)後,便把14、814、8放入Stack。並更新top,使其記錄88。
  • 在以上的任何階段,只要Stack有資料,使用函式Top()會回傳變數top所記錄的資料。
  • 在以上的任何階段,使用IsEmpty()便能判斷Stack裡是否有存放資料。
  • 在以上的任何階段,使用getSize()會回傳Stack中的資料個數。

Stack的應用

Stack最主要的功能是「記得先前的資訊」,所以時常用來處理需要「回復到先前的狀態」的問題,也稱為Back-Tracking問題,例如:

  • 編輯器(如word、sublime等等)中的undo
  • 網頁瀏覽器的「回到前一頁」功能。

Queue 佇列

結構:

以Linked list實作Queue非常直覺,如下圖,把每筆資料視為node,並且以pointer前後連結:

  • Queue的Push():在list的「尾巴」新增資料。
  • Queue的Pop():在list的「開頭」刪除資料。

Linked List: 新增資料、刪除資料、反轉介紹的Linked list的差異在於,因為Queue需要記得frontback的資料,所以Linked list除了原先記錄「第一個node」的pointer之外,要再多一個pointer記錄「最後一個node」。有了back pointer後,便能在時間複雜度O(1)完成「在Linked list尾巴新增資料」。

cc
方法示意圖

特性:
插入、刪除需時 O(1) 。搜尋需時 O(N) 。

方法:

  • Enqueue / Push(data):把資料從Queue的「後面」放進Queue,並更新成新的back
  • Dequeue / Pop:把front所指向的資料從Queue中移除,並更新front
  • getFront:回傳front所指向的資料。
  • getBack:回傳back所指向的資料。
  • IsEmpty:確認Queue裡是否有資料。
  • getSize:回傳Queue裡的資料個數。
cc
方法示意圖

Queue的應用

因為Queue的「First-In-First-Out」特徵,常用於先到先執行、需要排程(scheduling)的應用:

  • 作業系統:被多個程式共享的資源(例如CPU、印表機、網站伺服器),一次只能執行一個需求(例如request、interrupt),因此需要有個Queue來安排多個程式的執行順序(例如device queue、job queue)

參考資料:
1. stack intro : http://alrightchiu.github.io/SecondRound/stack-introjian-jie.html
2. stack method : http://alrightchiu.github.io/SecondRound/stack-yi-arrayyu-linked-listshi-zuo.html
3. stack / queue intro : http://www.csie.ntnu.edu.tw/~u91029/Data.html
4. queue intro : http://alrightchiu.github.io/SecondRound/queue-introjian-jie-bing-yi-linked-listshi-zuo.html

Share on facebook
Facebook
Share on linkedin
LinkedIn
Share on twitter
Twitter

More to explorer

Close Menu