Queues

Mar 7, 2018 · 3 minute read

TL;DR

Queues are a very useful FIFO data structure.

They can be implemented using a Linked List

When creating custom collections in swift conforming to Sequence, ExpressibleByArrayLiteral and CustomDebugStringConvertible makes them more powerful and easier to use.

API

Queues are a fundamental FIFO data structure. In their most basic implementation, a queue should support three operations:

protocol QueueType {
  associatedtype Element
  /// Number of elements in the queue
  var count: Int { get }
  /// Adds a new element to the back of the queue
  func enqueue(_ value: Element)
  /// Removes an element from the front of the queue
  func dequeue() -> Element?
}

Implementation

A possible implementation of the previous API, that aims to preserve the O(1) performance requirements of a Queue could be based on a Linked List as shown below:

class Queue<T>: QueueType {

    private var head: Node<T>?
    private var tail: Node<T>?

    // MARK: - QueueType

    var count: Int = 0

    func enqueue(_ value: T) {
        let node = Node(value: value)
        if head == nil {
            head = node
            tail = node
        } else {
            tail?.next = node
            tail = node
        }
        count += 1
    }

    @discardableResult
    func dequeue() -> T? {
        guard count > 0 else { return nil }
        let value = head?.value
        head = head?.next
        if head == nil { tail = nil }
        count -= 1
        return value
    }
}

private class Node<T> {
    var value: T
    var next: Node<T>?

    init(value: T, next: Node<T>? = nil) {
        self.value = value
        self.next = next
    }
}

Extensions

We could make the previous implementation more versatile and easier to use by conforming to a couple of protocols present in the standard library of swift:

extension Queue: Sequence {
    func makeIterator() -> AnyIterator<T> {
        var current = head
        return AnyIterator<T> {
            guard current != nil else { return nil }
            let next = current?.value
            current = current?.next
            return next
        }
    }
}

extension Queue: CustomDebugStringConvertible {
    var debugDescription: String {
        return "[\(map { "\($0)" }.joined(separator: ", "))]"
    }
}

The usage of this data structure can be made even more comfortable by adding conformance to ExpressibleByArrayLiteral. Unfortunately this cannot be done via extensions so a modification to the original implementation will be needed.

class Queue<T>: QueueType, ExpressibleByArrayLiteral {
    // ...
    required init(arrayLiteral elements: T...) {
        elements.forEach { enqueue($0) }
    }
    // ...
}

Usage

Finally, here is an example of how to use the Queue structure:

// This initialization style is possible thanks to the 
// conformance to "ExpressibleByArrayLiteral"
let queue: Queue<Int> = [1, 2, 3, 4, 5]

// Functions like map, flatMap and filter are all available 
// to us thanks to the conformance to "Sequence"
let squares = queue.map { $0 * $0 }

// We obtain debugger friendly output thanks to the
// conformance to "CustomDebugStringConvertible"
Swift.print(queue)