Swift 实现队列（一）- 数组队列

队列是一种数据结构，一种操作受限的线性表结构。它只支持入队（enqueue）和出队（dequeue）操作，数据流动遵循先进先出（First In， First Out）的规则。

我们既可以用数组实现队列，也可以用链表实现队列。用数组实现的队列叫做数组队列，用链表实现的队列叫做链表队列。

如何用 Swift 实现一个数组队列？

基础版本

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

public struct ArrayQueue<T>: Queue {
    private var items: [T]
    public init(_ items: [T] = []) { self.items = items }
    
    @discardableResult
    public mutating func enqueue(_ item: T) -> Bool {
        items.append(item)
        return true
    }
    
    public mutating func dequeue() -> T? {
        isEmpty ? nil : items.removeFirst()
    }
    
    public var isEmpty: Bool {
        items.isEmpty
    }
}

添加友好输出

extension ArrayQueue: CustomStringConvertible {
    public var description: String {
        return "<- \(items) <-"
    }
}

var queue = ArrayQueue<String>()
queue.enqueue("Ray")
queue.enqueue("Brian")
queue.enqueue("Eric")
print(queue)
// <- ["Ray", "Brian", "Eric"] <-

添加使用数组字面量初始化

extension ArrayQueue: ExpressibleByArrayLiteral {
    public init(arrayLiteral elements: T...) {
        self.init(elements)
    }
}

var queue: ArrayQueue = ["Ray", "Brian", "Eric"]
print(queue)
// <- ["Ray", "Brian", "Eric"] <-

分析复杂度

• 时间复杂度
  • enqueue
    • 平均/最好：O(1)
    • 最坏：O(n)
  • dequeue
    • 平均/最好/最坏：O(n)

• 空间复杂度：O(n)

参考链接

• Swift Algorithm Club: Queue