隊列（Queue）數(shù)據(jù)結構是先進先出（FIFO凌唬，first-in, first-out）的線性表，先進入隊列的元素漏麦，最先被移除客税。隊列適用于移除順序需與添加順序保持一致的情況。
這篇文章將介紹隊列的常用操作撕贞，使用多種方式實現(xiàn)隊列更耻，并分析其時間復雜度。
1. 常用操作
下面是為創(chuàng)建隊列所提供的協(xié)議：
public protocol Queue {
associatedtype Element
mutating func enqueue(_ element: Element) -> Bool
mutating func dequeue() -> Element?
var isEmpty: Bool { get }
var peek: Element? { get }
}
上述協(xié)議定義了隊列的核心操作：
- 入隊 enqueue：向隊列尾部添加元素捏膨。操作成功返回 true秧均；反之食侮，返回 false。
- 出隊 dequeue：移除隊列頭部元素目胡，并返回移除的元素锯七。
- isEmpty：檢查隊列是否為空。
- peek：返回隊列頭部元素誉己，但并不移除眉尸。
隊列只能從頭部移除、尾部添加巨双，不關心中間元素噪猾。如果有其他類型操作，數(shù)組可能更能滿足你的需要筑累。
下面將介紹四種不同創(chuàng)建隊列的方式：
- 數(shù)組（Array）
- 雙向鏈表（Doubly linked list）
- 圓形緩沖區(qū)（Ring Buffer）
- 使用兩個棧（Stack）袱蜡。
2. 使用數(shù)組實現(xiàn)隊列
Swift 標準庫提供了一些高度優(yōu)化的基本數(shù)據(jù)結構（如有序的數(shù)組），可以使用這些數(shù)據(jù)結構構建更為高級的數(shù)據(jù)結構疼阔。
這一部分將使用數(shù)組創(chuàng)建隊列：
創(chuàng)建 QueueArray.swift 文件戒劫，添加以下代碼：
/// 使用數(shù)組實現(xiàn)隊列
public struct QueueArray<T>: Queue {
// 存儲使用數(shù)組
private var array: [T] = []
public init() { }
}
這里定義了通用類型結構體半夷，遵守了Queue協(xié)議婆廊。
2.1 隊列狀態(tài)
繼續(xù)向 QueueArray 添加以下代碼：
public var isEmpty: Bool {
array.isEmpty
}
public var peek: T? {
array.first
}
使用數(shù)組已有功能可以很方便的查看隊列是否為空，查看隊列第一個元素巫橄。這些操作的復雜度為O(1)淘邻。
2.2 入隊 Enqueue
向隊列尾部添加元素只需調(diào)用數(shù)組的append()方法。添加以下代碼：
/// 入隊元素
/// - Parameter element: 要入隊的元素
/// - Returns: 入隊成功湘换，返回true宾舅；入隊失敗，返回false彩倚。
public mutating func enqueue(_ element: T) -> Bool {
array.append(element)
return true
}
入隊操作的平均復雜度是O(1)筹我。
上圖中，添加了Mic后還有兩個空間帆离。添加兩個元素后蔬蕊，數(shù)據(jù)將被填滿。再嘗試添加元素時哥谷，數(shù)據(jù)將會擴容岸夯。
擴容時需要重新分配內(nèi)存，將數(shù)組原來元素復制過來们妥。每次擴容時容量都會翻倍猜扮，因此，擴容發(fā)生的頻率并不高监婶。入隊的平均復雜度是O(1)旅赢，最壞情況復雜度是O(n)齿桃。
2.3 出隊 Dequeue
使用以下代碼出隊元素：
/// 出隊元素
/// - Returns: 出隊的元素。當隊列為空時煮盼，返回nil源譬。
public mutating func dequeue() -> T? {
isEmpty ? nil : array.removeFirst()
}
從數(shù)據(jù)最前面移除元素是線性時間操作，它需要后面元素前移孕似。出隊復雜度是O(n)踩娘。
2.4 實戰(zhàn)
為了方便測試，讓 QueueArray 遵守CustomStringConvertible協(xié)議喉祭，代碼如下：
extension QueueArray: CustomStringConvertible {
public var description: String {
String(describing: array)
}
}
使用以下代碼對隊列進行測試：
public func testQueueArray() {
var queue = QueueArray<String>()
queue.enqueue("Ray")
queue.enqueue("Brian")
queue.enqueue("Eric")
queue
queue.dequeue()
queue
queue.peek
}
根據(jù)控制臺輸出养渴，查看隊列表現(xiàn)是否符合預期。
2.5 復雜度
基于數(shù)組的隊列大部分操作都是常數(shù)時間的泛烙，只有dequeue()的時間復雜度是線性時間理卑。
| 操作 | 平均復雜度 | 最壞情況復雜度 |
|---|---|---|
| enqueue | O(1) | O(n) |
| dequeue | O(n) | O(n) |
使用基于數(shù)組的隊列非常簡單，但也有一些缺陷蔽氨。從最前面移除元素需移動后面所有元素藐唠，性能太低，數(shù)據(jù)量變大時尤為明顯鹉究。數(shù)組填滿時需擴容宇立，且擴容后占用很多空閑空間。隨著時間推移自赔，它占用空間可能越來越大妈嘹。
這些不足可以避免嗎？下面看下基于鏈表的隊列绍妨。
3. 基于雙向鏈表的隊列
雙向鏈表與單向鏈表有些類似润脸，只是結點同時包含了指向上一個結點的指針。
由于這篇文章的重點不在雙向鏈表他去，你可以直接在這里獲取雙向鏈表的實現(xiàn)毙驯。如果你對鏈表不了解，可以查看我的另一篇文章鏈表 LinkedList灾测。
創(chuàng)建 QueueLinkedList.swift 文件爆价，并添加以下類：
public class QueueLinkedList<T>: Queue {
// 內(nèi)部存儲使用雙向鏈表
private var list = DoublyLinkedList<T>()
public init() { }
}
3.1 入隊 enqueue
使用下面代碼向隊列添加元素：
/// 入隊。
/// - Parameter element: 要入隊的元素
/// - Returns: 入隊成功行施，返回 true允坚；反之，返回 false蛾号。使用基于鏈表的隊列稠项，不會入隊失敗。
public func enqueue(_ element: T) -> Bool {
list.append(element)
return true
}
雙向鏈表會更新 tail 節(jié)點的上一個鲜结、下一個指針展运，使其指向新添加的節(jié)點活逆。由于只需更改指針，復雜度為O(1)拗胜。
3.2 出隊 Dequeue
使用下面代碼移除頭部元素：
/// 出隊蔗候，并返回出隊的元素。
/// - Returns: 隊列為空時埂软，返回空锈遥；反之，返回移除的元素勘畔。
public func dequeue() -> T? {
guard !list.isEmpty, let element = list.first else {
return nil
}
return list.remove(element)
}
從頭部移除元素時只需操作指針所灸，復雜度為O(1)。與基于數(shù)組的隊列相比炫七，無需移動元素爬立，只需更新前面兩個節(jié)點的next和previous指針。
3.3 隊列狀態(tài)
與數(shù)組類似万哪，借助DoublyLinkedList的peek侠驯、isEmpty屬性提供隊列首部元素、是否為空功能奕巍。
public var peek: T? {
list.first?.value
}
public var isEmpty: Bool {
list.isEmpty
}
3.4 實戰(zhàn)
使用下面代碼檢驗隊列功能：
public func testQueueDoublyLinkedList() {
let queue = QueueLinkedList<String>()
queue.enqueue("Ray")
queue.enqueue("Brian")
queue.enqueue("Eric")
queue
queue.dequeue()
queue
queue.peek
}
這里的輸出應與 QueueArray 隊列輸出相同吟策。
3.5 復雜度
下面是基于雙向鏈表的隊列復雜度：
| 操作 | 平均復雜度 | 最壞情況復雜度 |
|---|---|---|
| enqueue | O(1) | O(1) |
| dequeue | O(1) | O(1) |
QueueArray 主要問題是 dequeue 元素為線性時間，而基于雙向鏈表的隊列 dequeue 操作為恒定時間伍绳，即復雜度為O(1)踊挠。
上面表格并未體現(xiàn)出基于雙向鏈表隊列的缺點乍桂。盡管復雜度是O(1)冲杀，但它帶有額外開銷。每個元素都需要開辟額外空間存儲指向上一個睹酌、下一個結點的指針权谁，且每次創(chuàng)建元素時，都需要分配內(nèi)存憋沿。與之相反旺芽，基于數(shù)組的隊列一次開辟大量內(nèi)存空間，其比多次開辟小空間性能更好辐啄。
是否可以避免多次分配內(nèi)存空間采章，又保持O(1)復雜度？如果隊列大小固定壶辜，可以使用環(huán)形緩沖區(qū)（Ring Buffer悯舟，也稱為圓形緩沖區(qū) circular buffer、圓形隊列 circular queue砸民、循環(huán)緩沖區(qū) cyclic buffer）實現(xiàn)抵怎。例如奋救，玩游戲時，使用基于環(huán)形緩沖區(qū)的隊列記錄游戲參與者的次序反惕。
4. 基于環(huán)形緩沖區(qū)的隊列
環(huán)形緩沖區(qū) ring buffer是固定大小的數(shù)組尝艘。
4.1 Ring Buffer 工作原理
下面介紹如何使用 ring buffer 實現(xiàn)隊列。
創(chuàng)建大小固定為四的環(huán)形緩沖區(qū)姿染，它的兩個指針用途如下：
- read 指針跟蹤 queue 的頭部背亥。
- write 指針跟蹤下一個可用空間，覆蓋掉已經(jīng)被讀取的元素悬赏。
enqueue 元素如下：
每次入隊元素 write 指針加一隘梨。繼續(xù)入隊元素：
Write 指針在 read 指針前面兩步，意味著隊列不為空舷嗡。
下面出隊兩個元素：
出隊就是 read 指針讀取 ring buffer 元素轴猎。
再次入隊元素以填滿隊列：
Write 指針到達尾部時，再次從頭部開始进萄，這也是這種數(shù)據(jù)結構為何被稱為環(huán)形緩沖區(qū) circular buffer捻脖。
再次 dequeue 兩個元素：
Read 指針也指向了頭部，與 write 指針相遇中鼠，這時隊列為空可婶。
下面是 RingBuffer 的實現(xiàn)：
public struct RingBuffer<T> {
// 使用數(shù)組存儲
private var array: [T?]
private var readIndex = 0
private var writeIndex = 0
public init(count: Int) {
array = Array<T?>(repeating: nil, count: count)
}
public var first: T? {
array[readIndex]
}
/// 入隊。
/// - Parameter element: 要入隊的原
/// - Returns: 入隊成功時援雇，返回 true矛渴；反之，返回 false惫搏。當隊列滿時具温，入隊會失敗。
public mutating func write(_ element: T) -> Bool {
if !isFull {
array[writeIndex % array.count] = element
writeIndex += 1
return true
} else {
return false
}
}
/// 出隊
/// - Returns: 隊列為空時筐赔，返回 nil铣猩；反之，返回出隊的元素茴丰。
public mutating func read() -> T? {
if !isEmpty {
let element = array[readIndex % array.count]
readIndex += 1
return element
} else {
return nil
}
}
private var availableSpaceForReading: Int {
writeIndex - readIndex
}
public var isEmpty: Bool {
availableSpaceForReading == 0
}
private var availableSpaceForWriting: Int {
array.count - availableSpaceForReading
}
public var isFull: Bool {
availableSpaceForWriting == 0
}
}
extension RingBuffer: CustomStringConvertible {
public var description: String {
let values = (0..<availableSpaceForReading).map {
String(describing: array[($0 + readIndex) % array.count]!)
}
return "[" + values.joined(separator: ", ") + "]"
}
}
在QueueRingBuffer.swift文件中添加以下代碼：
public struct QueueRingBuffer<T>: Queue {
/// 使用環(huán)形緩沖區(qū)存儲
private var ringBuffer: RingBuffer<T>
/// 初始化隊列
/// - Parameter count: 指定隊列的固定大小
public init(count: Int) {
ringBuffer = RingBuffer<T>(count: count)
}
public var isEmpty: Bool {
ringBuffer.isEmpty
}
public var peek: T? {
ringBuffer.first
}
}
為了遵守Queue協(xié)議达皿，這里也創(chuàng)建了isEmpty和peek屬性。這里并未暴露RingBuffer類贿肩，而是提供了接口峦椰。isEmpty和peek操作的復雜度都是O(1)。
4.2 入隊 enqueue
使用以下方法入隊元素：
/// 入隊
/// - Parameter element: 要入隊的元素
/// - Returns: 入隊成功時汰规，返回 true汤功；反之，返回 false控轿。當隊列滿時冤竹，入隊會失敗拂封。
public mutating func enqueue(_ element: T) -> Bool {
ringBuffer.write(element)
}
直接調(diào)用RingBuffer的write(_:)方法即可。由于 Ring Buffer 有固定大小鹦蠕，需根據(jù)入隊是否成功返回true冒签、false。
4.3 出隊 dequeue
使用以下方法出隊元素：
/// 出隊
/// - Returns: 隊列為空時钟病，返回 nil萧恕；反之，返回出隊的元素肠阱。
public mutating func dequeue() -> T? {
ringBuffer.read()
}
4.4 實戰(zhàn)
使用下面代碼檢驗基于環(huán)形緩沖區(qū)的隊列：
public func testQueueRingBuffer() {
var queue = QueueRingBuffer<String>(count: 3)
queue.enqueue("Ray")
queue.enqueue("Brian")
queue.enqueue("Eric")
queue
queue.dequeue()
queue
queue.peek
}
上面方法輸出與使用基于數(shù)組票唆、雙向鏈表的隊列一致。
4.5 復雜度
基于環(huán)形緩沖區(qū)的隊列復雜度如下：
| 操作 | 平均復雜度 | 最壞情況復雜度 |
|---|---|---|
| enqueue | O(1) | O(1) |
| dequeue | O(1) | O(1) |
基于環(huán)形緩沖區(qū)隊列復雜度與基于雙向鏈表隊列復雜度相同屹徘，但因為環(huán)形緩沖區(qū)有固定大小走趋，enqueue 可能失敗。
截止目前噪伊，分別介紹了基于數(shù)組簿煌、雙向鏈表、環(huán)形緩沖區(qū)的隊列鉴吹。下面將介紹一種基于兩個堆棧的隊列姨伟，它在內(nèi)存讀取、存儲方面優(yōu)于雙向鏈表豆励，也無需像環(huán)形緩沖區(qū)那樣有固定大小夺荒。
5. 基于兩個棧的隊列
在QueueStack.swift文件中添加以下結構體：
public struct QueueStack<T> : Queue {
// 使用兩個數(shù)組存儲
private var leftStack: [T] = []
private var rightStack: [T] = []
public init() { }
}
基于兩個棧的隊列整體邏輯很簡單，當 enqueue 元素時良蒸，進入 Right Stack技扼；當 dequeue 元素時，將 Right Stack 放入 Left Stack诚啃，再從 Left Stack pop 元素淮摔，這樣就滿足了先進先出原則。
為了遵守Queue協(xié)議始赎，添加以下屬性：
public var isEmpty: Bool {
// 隊列是否為空，只有兩個棧都為空時才為空仔燕。
leftStack.isEmpty && rightStack.isEmpty
}
public var peek: T? {
// 如果leftStack不為空造垛，返回它的最后一個；如果為空晰搀，返回rightStack第一個五辽。
!leftStack.isEmpty ? leftStack.last : rightStack.first
}
isEmpty和peek操作復雜度都是O(1)。
5.1 入隊 enqueue
使用以下方法入隊：
public mutating func enqueue(_ element: T) -> Bool {
// 入隊時每次向 rightStack 添加
rightStack.append(element)
return true
}
添加元素的復雜度是O(1)外恕。
5.2 出隊 dequeue
使用下面代碼出隊元素：
public mutating func dequeue() -> T? {
if leftStack.isEmpty { // 如果 leftStack 為空杆逗，將rightStack反轉后存入leftStack乡翅，并清空rightStack。
leftStack = rightStack.reversed()
rightStack.removeAll()
} else { // leftStack不為空罪郊，則移除最后一個元素蠕蚜。
return leftStack.popLast()
}
}
只有當 leftStack 為空時，才會將 rightStack 棧內(nèi)元素反轉后移動到 leftStack悔橄。
雖然反轉數(shù)組復雜度是
O(n)靶累，但出隊平均復雜度依然是O(1)。例如癣疟，左右兩個棧均有很多元素挣柬，只有左側棧為空時，才會將右側棧反轉后移動到左側棧睛挚，之后繼續(xù)移除左側棧元素邪蛔。反轉操作發(fā)生頻率很低。
5.3 實戰(zhàn)
使用下面代碼檢驗基于兩個棧實現(xiàn)的隊列：
public func testQueueStacks() {
var queue = QueueStack<String>()
queue.enqueue("Ray")
queue.enqueue("Brian")
queue.enqueue("Eric")
queue
queue.dequeue()
queue
queue.peek
}
上面方法輸出與使用基于數(shù)組扎狱、雙向鏈表店溢、圓形緩沖區(qū)的隊列一致。
5.4 復雜度
基于兩個棧隊列復雜度如下：
| 操作 | 平均復雜度 | 最壞情況復雜度 |
|---|---|---|
| enqueue | O(1) | O(n) |
| dequeue | O(1) | O(n) |
與基于數(shù)組的隊列相比委乌，基于兩個棧的隊列將出隊時間復雜度從O(n)降低到了O(1)床牧。
與基于環(huán)形緩沖區(qū)的隊列相比，基于兩個棧的隊列沒有固定大小遭贸。當右側棧需要反轉或容量變滿時戈咳，它的復雜度是O(n)，但這些情況發(fā)生的頻率并不高壕吹。
由于數(shù)組內(nèi)存空間是連續(xù)的著蛙，首次訪問時會添加到緩存，后續(xù)讀取也會命中緩存耳贬。因此踏堡，在存取方面基于兩個棧的隊列，性能優(yōu)于基于雙向鏈表的隊列咒劲。如下圖所示：
鏈表元素內(nèi)存空間并未連續(xù)顷蟆，會增加查找時間：
6. 隊列算法題
這一部分介紹三道隊列算法題。
6.1 記錄游戲次序
假設你在和朋友玩游戲腐魂，但大家都記不住該誰玩了帐偎。可以創(chuàng)建一個管理者蛔屹，記錄游戲次序削樊。
隊列數(shù)據(jù)結構適合解決上述問題。
下面是記錄次序的協(xié)議：
protocol BoardGameManager {
associatedtype Player
mutating func nextPlayer() -> Player?
}
為QueueLinkedList添加以下 extension：
extension QueueLinkedList: BoardGameManager {
public typealias Player = T
public func nextPlayer() -> T? {
// 通過dequeue獲取下一個選手，如果獲取不到漫贞，直接返回空甸箱。
guard let person = dequeue() else { return nil }
// enqueue 同一位選手，會將其添加到尾部迅脐。
enqueue(person)
return person
}
}
使用以下代碼進行測試：
var queue = QueueLinkedList<String>()
queue.enqueue("Vincent")
queue.enqueue("Remel")
queue.enqueue("Lukiih")
queue.enqueue("Allison")
print(queue)
print("==== boardgame ====")
queue.nextPlayer()
print(queue)
queue.nextPlayer()
print(queue)
queue.nextPlayer()
print(queue)
queue.nextPlayer()
print(queue)
使用不同的實現(xiàn)方式芍殖，它的時間復雜度可能不同。上面的算法使用了雙向鏈表仪际，它的時間復雜度是O(1)围小，空間復雜度也是O(1)；如果使用基于數(shù)據(jù)的隊列树碱，它的時間復雜度是O(n)肯适，空間復雜度是O(1)。
6.2 反轉隊列
實現(xiàn)一個算法成榜，對隊列進行反轉框舔。
Queue 是先進先出，Stack 是后進先出赎婚×跣澹可以使用 stack 輔助反轉隊列，即將 queue 內(nèi)容插入 stack挣输，再將 stack 元素 pop 后添加到 queue纬凤。
如下所示：
extension QueueArray {
func reversed() -> QueueArray {
// 創(chuàng)建 queue 副本
var queue = self
// 創(chuàng)建 stack
var stack = Stack<T>()
// dequeue queue的所有元素，并添加到 stack撩嚼。
while let element = queue.dequeue() {
stack.push(element)
}
// 將 stack pop 后添加到 queue停士。
while let element = stack.pop() {
queue.enqueue(element)
}
return queue
}
}
由于需遍歷兩次，它的時間復雜度是O(n)完丽。
使用以下代碼進行測試：
var queue = QueueArray<String>()
queue.enqueue("1")
queue.enqueue("8")
queue.enqueue("11")
queue.enqueue("648")
print("before: \(queue)")
print("after: \(queue.reversed())")
6.3 雙端隊列
雙端隊列（doubled-ended queue恋技，簡寫為 deque）是一種具有隊列和棧性質的抽象數(shù)據(jù)類型，可以從兩端插入逻族、移除雙端隊列的元素蜻底。可以把 deque 認為既是 queue聘鳞，又是 stack薄辅。
下面的Deque協(xié)議用于輔助創(chuàng)建自定義數(shù)據(jù)結構，Direction枚舉用于描述操作針對頭部還是尾部搁痛。
enum Direction {
case front
case back
}
protocol Deque {
associatedtype Element
var isEmpty:Bool { get }
func peek(from direction: Direction) -> Element?
mutating func enqueue(_ element: Element, to direction: Direction) -> Bool
mutating func dequeue(from direction: Direction) -> Element?
}
環(huán)形緩沖區(qū)长搀、棧、數(shù)組鸡典、雙向鏈表都可用于構建雙端隊列，這里使用雙向鏈表枪芒。
首先創(chuàng)建DequeDoubleLinkedList類彻况，如下所示：
class DequeDoubleLinkedList<Element>: Deque {
// 使用雙向鏈表存儲
private var list = DoublyLinkedList<Element>()
public init() { }
}
實現(xiàn)isEmpty谁尸，其復雜度是O(1)。
var isEmpty: Bool {
list.isEmpty
}
下面實現(xiàn)peek(from:)方法纽甘，它的復雜度是O(1)良蛮。
func peek(from direction: Direction) -> Element? {
// 根據(jù)direction決定查看first還是last。
switch direction {
case .front:
return list.first?.value
case .back:
return list.last?.value
}
}
下面實現(xiàn)enqueue(_:)方法悍赢，根據(jù)方向添加元素：
func enqueue(_ element: Element, to direction: Direction) -> Bool {
// 根據(jù)direction決定添加方式决瞳。
switch direction {
case .front:
// 會將 element 設置為新的頭節(jié)點
list.prepend(element)
case .back:
// 會將 element 設置為新的尾節(jié)點
list.append(element)
}
return true
}
上面的方法只需更新指針指向，因此它的復雜度是O(1)左权。
下面實現(xiàn)dequeue(_:)方法：
func dequeue(from direction: Direction) -> Element? {
let element: Element?
// 雙向鏈表有指向前皮胡、后結點的指針，只需移除指針即可赏迟。
switch direction {
case .front:
guard let first = list.first else { return nil }
element = list.remove(first)
case .back:
guard let last = list.last else { return nil }
element = list.remove(last)
}
return element
}
與enqueue(_:)類似屡贺，dequeue(_:)的復雜度也是O(1)。
使用以下代碼驗證雙端隊列：
let deque = DequeDoubleLinkedList<Int>()
deque.enqueue(1, to: .back)
deque.enqueue(2, to: .back)
deque.enqueue(3, to: .back)
deque.enqueue(4, to: .back)
print(deque)
deque.enqueue(5, to: .front)
print(deque)
deque.dequeue(from: .back)
deque.dequeue(from: .back)
deque.dequeue(from: .back)
deque.dequeue(from: .front)
deque.dequeue(from: .front)
deque.dequeue(from: .front)
print(deque)
總結
- 隊列是先進先出锌杀。
- enqueue 將元素添加到尾部甩栈。
- dequeue 移除隊列頭部元素。
- 數(shù)組的元素分布在連續(xù)內(nèi)存塊中糕再；鏈表的元素隨機分布量没，緩存命中率低。
- 環(huán)形緩沖區(qū)適合固定大小的隊列突想。
- 使用兩個椗固悖可以將
dequeue(_:)平均復雜度降低到O(1)，并且在查找方面優(yōu)于雙向鏈表蒿柳。
Demo名稱：Queue
源碼地址：https://github.com/pro648/BasicDemos-iOS/tree/master/Queue
