Queues

October 6, 2022

swift

As we did for the Stacks, we are going to create our Queue Struct.

A queue uses FIFO (first-in first-out) ordering and these are its basic operations:

• add(element): Or enqueue(element), add an element.
• remove(): Or dequeue(), remove and return an element.
• peek(): Return the first element of the queue.
• isEmpty()

First contact

An array can already do everything a queue needs; building a Queue is mostly a matter of restricting that behaviour.

The code below shows how the array methods map onto a queue: append() for add(), removeFirst() for remove().

var queue: [String] = []

queue.append("A")
queue.append("B")
queue.append("C")

while !queue.isEmpty {
    let e = queue.removeFirst()
    print(e)
}

Output

A
B
C

Version 1: A generic struct

struct Queue<Element> {
    private var array: [Element] = []

    mutating func add(_ element: Element) {
        array.append(element)
    }

    mutating func remove() -> Element? {
        array.removeFirst()
    }

    func peek() -> Element? {
        array.first
    }

    var isEmpty: Bool {
        array.isEmpty
    }
}

Since the add() and remove() functions must modify the content or the array (which is an attribute of the Struct), then it is necessary that this function be mutating. Note that the peek() function does not modify or extract a value, it only reads the top element, that’s why you don’t need the mutating keyword.

Remember that if the function has only one line of code you can save the return keyword.

How to use

var queue = Queue<String>()

queue.add("A")
queue.add("B")
queue.add("C")

while !queue.isEmpty {
    let e = queue.remove()
    print(e ?? "")
}

Alternatively instead of using an array you can also use a LinkedList as the main container to create the Struct.

Updated for Swift 5.7