A Functional 'Queue' Implementation in Swift

A queue is a sequence data structure that allows for elements to be inserted at one end and removed from the opposite end. Elements are always deleted in the same order in which they are inserted. In other words, a queue is said to be a “first in, first out” structure.


Why should we care about queues? After all, we could just use a simple list representation to store our sequences instead. Well, queues offer dramatic efficiency gains over ordinary lists because they are cognizant of the elements at their own “beginning” and “end”.


At a high level, a queue can be represented to 2 pointers: one to the front of the queue, and another to the back. With these pointers, we can push and pop from the queue without having to scan from one end to the other. Data access can be accomplished in Θ(1) time rather than Θ(n) time, so our queue can scale infinitely without taking an efficiency hit.


This week, we thought it would be neat to challenge ourselves to implement this data structure using only Swift’s value types.


Here’s how we did it:


We knew that each element of our queue would be a linked list, so we began by creating that data structure:


enum List<T> { case empty indirect case cons(T, List<T>) }


Then, we established and implemented a protocol to allow for decomposition:


``` protocol Decomposable {

associatedtype T

init(withElement element: T?)

var car: T? { get }
var cdr: List<T>? { get }

}

extension List: Decomposable {

typealias String = T

init(withElement element: T?) {
    self = element != nil ? .cons(element!, .empty) : .empty
}

var car: T? {
    switch self {
    case .empty:
        return nil
    case .cons(let car, _):
        return car
    }
}

var cdr: List<T>? {
    switch self {
    case .empty:
        return nil
    case .cons(_, let cdr):
        return cdr
    }
}

}


<br />
This `queue` implementation was guided by the need for 2 essential operations:

<br />
`insert` - to insert a new element at the rear of the `queue`
`delete` - to remove an element from the front of the `queue`

<br />
Beyond that, there was little else to do beyond providing an interface to perform those operations:

<br />

struct Queue {

var isEmpty: Bool {
    return frontPtr == nil
}
var frontPtr: Element?
var rearPtr: Element?

mutating func insert(element: Element) {
    if isEmpty {
        frontPtr = element
    }
    rearPtr = element
}

mutating func delete() {
    guard !isEmpty, let frontPointer = frontPtr?.cdr as? Element else {
        return
    }
    frontPtr = frontPointer
} } ```


Our insert function simply set the front pointer to the inserted element (in addition to the rear pointer if the queue is empty initially).


Our delete function, on the other hand, set the front pointer to the tail (or cdr) of the preexisting front pointer (or does nothing if the queue is empty).1


And there you have it. This simple API gave us the full functionality of a queue given our initial definition.


For a fuller implementation and some example usage, see our contribution to Swift Book Club’s playground for exercise 3.22 of Structure and Interpretation of Computer Programs.

  1. car and cdr are fundamental functions in the Lisp family of programming languages. They represent the 2 constituent elements that compose a simple list data structure. car corresponds to the first item in a list, and cdr corresponds to the sequence of remaining items in the list after the first item. cons, another foundational function, is a constructor that builds a list from a car and cdr.