使出栈和入栈的时间复杂度都为O(1)
protocol Queue {
associatedtype Element
mutating func enqueue(_ newElement: Element)
mutating func dequeue() -> Element?
}
struct FIFOQueue<Element>: Queue {
private var left: [Element] = []
private var right: [Element] = []
/// 将元素添加到队列最后
/// - 复杂度：O(1)
/// - Parameter newElement: Element
mutating func enqueue(_ newElement: Element) {
right.append(newElement)
}
/// 从当前队列前端移除一个元素
/// 当队列为空时，返回nil
/// - 复杂度：平摊 O(1)
mutating func dequeue() -> Element? {
if left.isEmpty {
left = right.reversed()
right.removeAll()
}
return left.popLast()
}
}
就和数组的扩容一样，扩容的操作并不是时刻发生，它的频率是低频的，平摊下来接近于O(1)这里的将 right 数组 reversed 到 left 数组，虽然是 O(n) 的操作，但是队列入栈和出栈的频次是完全高于 reversed 的，所以平摊复杂度是 O(1)
