FIFO Queue in Swift

Queue.swift

/// A First-in first-out queue (FIFO).
///
/// - New elements are added to the end/tail of the queue.
/// - Dequeuing pulls elements from the front/head of the queue.
public struct Queue<Element> {
    private var tail: ContiguousArray<Element?>
    private var head: Int

    /// Creates a new, empty queue.
    public init() {
        head = 0
        tail = []
    }

    /// Adds an element to the end of the collection.
    ///
    /// O(1)
    /// - Parameter element: The element to append to the queue.
    public mutating func enqueue(_ element: Element) {
        tail.append(element)
    }

    /// Removes and returns the first element in the queue.
    ///
    /// O(1) on avarage.
    /// - Returns: The removed element.
    public mutating func dequeue() -> Element? {
        guard head < tail.count else {
            return nil
        }

        let element = tail[head]
        tail[head] = nil
        head += 1

        /// This calculates the percentage of empty spots at the beginning as a ratio of the total array size.
        /// If more than 25% of the array is unused, we chop off that wasted space.
        /// However, if the array is small we do not resize it all the time, so there must be at least 2^6 elements in the array before we try to trim it.
        if tail.count > 64 {
            let percentage = Double(head)/Double(tail.count)
            if percentage > 0.25 {
                tail.removeFirst(head) // O(n)
                head = 0
            }
        }

        return element
    }

    /// A Boolean value indicating whether the queue is empty.
    @inline(__always) public var isEmpty: Bool {
        count == 0
    }

    /// The number of elements in the queue.
    public var count: Int {
        return tail.count - head
    }
}

extension Queue: Equatable where Element: Equatable { }
extension Queue: Decodable where Element: Decodable { }
extension Queue: Encodable where Element: Encodable { }


extension Queue: IteratorProtocol {
    public mutating func next() -> Element? { dequeue() }
}
extension Queue: Sequence { }

I would have loved to use this implementation, but performance was not good in comparison, due to re-allocation overhead:

public struct QueueSlice<Element> {
    private var storage: ArraySlice<Element>

    public init() {
        storage = ArraySlice<Element>()
    }

    /// O(1)
    public mutating func enqueue(_ element: Element) {
        storage.append(element)
    }

    /// O(1)
    /// <https://github.com/apple/swift/blob/a89c882bdb519702c9fb48d76bfe72a3b0efc2c5/stdlib/public/core/Collection.swift#L1052>
    public mutating func dequeue() -> Element? {
        return storage.popFirst()
    }
}