Fast Queue implementation for SWIFT

The Swift Standard Library currently implements the three most essential general-purpose data structures: Array, Set and Dictionary. These are the right tool for a wide variety of use cases, and they are particularly well-suited for use as currency types. But sometimes, in order to efficiently solve a problem or to maintain an invariant, Swift programmers would benefit from a larger library of data structures.

Swift Collections, is a new open-source package focused on extending the set of available Swift data structures. Like the Swift Algorithms and Swift Numericspackages. Until Swift collection is released be aware that the standard structures do not provide good runtime complexity and you have to do it yourself. However this can be fun as the following article is showing.

A Queue is renown data structure in computer science to execute operation in a linear order. Each element would be computed in the same order they were inserted in before moving to the next one. We queue each element one by one in their insertion order. The first inserted element would be the first treated, therefor the first one to be removed from the queue. That’s what’s called FIFO (first in, first out).

A Queue includes couple functions and properties by default:

• a way to enqueue element: to add a new element to the queue
• a way to dequeue element: to remove the next element to the queue to be executed
• a front or head: the element at the top of the queue
• a rear or tail: the element at the bottom of it

Let’s move on to an implementation in Swift. The implementation has runtime O(1) for enqueue and dequeue and is based on a ring buffer implementation. It is using defer and guard to assure data structure invariant.

Also checkout my queue gist to reuse this small piece of code!

import Foundation


public struct Queue<T> {

    private var array: Array<T?>

    private var availableSpaceCount: Int
    
    private var readIndex: Int
    private var writeIndex: Int

    
    public var isFull: Bool {
       return availableSpaceCount == 0
    }
    
    public var isEmpty: Bool {
        return availableSpaceCount == array.count
    }
    
    public init(capacity: Int) {
        array = [T?](repeating: nil, count: capacity)
        readIndex  = 0
        writeIndex = 0
        availableSpaceCount = capacity
    }

    
    public mutating func enqueue(_ element: T) -> Bool {
       guard !isFull else { return false }
       defer {
           // adjust invariants Dijkstra would love it :-)
           writeIndex += 1
           writeIndex %= array.count
           availableSpaceCount -= 1
       }
       array[writeIndex] = element
       return true
    }

    public mutating func dequeue() -> T? {
       guard !isEmpty else {
           return nil
       }
       defer {
           // adjust invariants Dijkstra would love it :-)
           array[readIndex] = nil
           readIndex += 1
           readIndex %= array.count
           availableSpaceCount += 1
       }
       return array[readIndex]
     }
    
    public func peek() -> T? {
        guard !isEmpty else {
            return nil
        }
        return array[readIndex]
    }
    
    

}


extension Queue: Sequence {
  public func makeIterator() -> AnyIterator<T> {
    var index = readIndex
    var count = array.count - availableSpaceCount
    return AnyIterator {
        guard count > 0  else { return nil }
        defer {
            index += 1
            index %= self.array.count
            count -= 1
            
        }
        return self.array[index]
    }
  }
}