通过两个数组实现队列

使出栈和入栈的时间复杂度都为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)

来自 https://leejnull.github.io/2019/12/30/2019-12-30-01/