Swift4 Day96：資料結構 Queues

2019.2.1 資料結構 Queues

先來設定 Queue 的 protocol，討論主要會用到 enqueue 跟 dequeue的實作，讓我們先來定義 enqueue 與 dequeue。文末有 github 專案，可以直接拿去測。

• enqueue：加一個新的物件到 Queue 的最後面
• dequeue：刪掉 Queue 中最前面的物件
• isEmpty：這個 Queue 是否是空的
• peek：回傳 Queue 中的第一個物件

public protocol Queue {
associatedtype Element
mutating func enqueue(_ element: Element) ->Bool
mutating func dequeue()->Element?
var isEmpty: Bool { get }
var peek:Element? { get }
}

延伸閱讀：在這幹嘛加mutating？

Queues 採 FIFO 的方法先進先出，就像排隊買票一樣。

再來會介紹四種建立 Queue 的方法

• using array
• using double linked list
• using a ring buffer
• using two stacksd

Using array

• enqueue 每次都是O(1)，因為只要往後面塞就好，但當記憶體滿的時候就會需要找更大塊的記憶體去 alloc，此時為O(n)，但實際上這種狀況很少見，因為一開始通常會給所需要的兩倍記憶體。

• dequeue 就是將第一個物件刪除，後面的所有物件在記憶體中都往前順移一位，為O(n)

沒帶參數但最前面的 Alice 被刪掉了

Using double linked list

linked list 的資料結構是由很多個 Node 組成的，每個 Node 都有自己的value 與 next （或prev），最前面是 head，最後面是 tail。

• enqueue 一樣是O(1)，從往後面塞就好

• dequeue 只要將前面的 Head 換成後面的 Node就好，所以O(1)

dequeue 的時候 Gary 就被刪掉啦

linked list 的 程式碼結構

using a ring buffer

1. read 會在 queue 最前方
2. write 會在下一個空格

• enqueue 時每增加一個物件，write 就會指向物件後面空著的部分。

• dequeue 時 write 就會指到第一格，當你 enqueue 的時候就會對這部分做覆蓋。

執行dequeue index0 的 Gary 沒有消失，要再次 enqueue 時 Alice 就會覆蓋原本的資料

dequeue的時候，element還是在，要再次enqueue的時候會直接覆蓋。

using two stacksd

• enqueue 時都先加到右側的 stack 裡，此時為O(1)

• dequeue 時先檢查是否是空的，將右側的 tash 移到左側，最底層的物件則刪除。

這次的原始碼總整理，資料結構學了很多，刷題的時候可能比較有用，但覺得對工作沒有幫助哈哈哈，Apple 底層都幫你優化了～～～👉

wl02722691/DataStructures_Queues

參考文獻：

Data Structures & Algorithms in Swift Chapter3: Linked List

Data Structures & Algorithms in Swift Chapter5: Queue