Swift Queue fun

There are many ways to write Queues in Swift, but wrapping an Array is about as easy a solution as you can get. You get all the push/pop behavior for free. (Yes, there are better solutions for complexity, but I really want to show off ArrayLiteralConvertible in this write-up.)

Wrapping an Array

Start with a basic struct to envelope your queue:

public struct Queue<T> {
    public private(set) var elements: Array<T> = []
}

Notice the private(set) modifier for elements. This restricts the read-write scope of the property. Your elements are visible but cannot be  set outside the file that declares them.  This “private” behavior can surprise you in playgrounds, where your timeline acts as a single file.  Consuming the queue in the same timeline means private elements can be overridden. This is an unusual use-case.

var q = Queue(elements: [1, 2, 3]) // 1, 2, 3
q.elements = [4, 5]
q.elements // 4, 5

Next, decide where you want your expensive operations to happen: on push or pop. Both removeLast() and append(value) are O(1) but insert(value, atIndex: n) and removeFirst() are O(`count`). Choose one cheap operation and one expensive operation.

public struct Queue<T> { 
    public private(set) var elements: Array<T> = []
    public mutating func push(value: T) { elements.append(value) } // O(1)
    public mutating func pop() -> T { return elements.removeFirst() } // O(`count`)
}

Guarding against Fatal Errors

At this point, you’ve now got a working queue. Unfortunately, there’s a major problem with this implementation. Calling `removeFirst` on an empty collection raises a fatal error. Oops.

Screen Shot 2016-03-08 at 12.26.57 PM

You can resolve this in several ways:

  1. Stick with the status quo and live dangerously (The “Russian Roulette queue”)
  2. You can make the queue throwing (ugh)
  3. You can make the return type optional (you have to test and unwrap)
  4. You can introduce an isEmpty property so you can test before popping.

I like option 4.

public struct Queue<T> { 
    public private(set) var elements: Array<T> = []
    public mutating func push(value: T) { elements.append(value) }
    public mutating func pop() -> T { return elements.removeFirst() }
    public var isEmpty: Bool { return elements.isEmpty }
}

Adding the property lets you guard your actions before applying any dangerous calls.

while !q.isEmpty { print(q.pop(), q.elements) }

Better Initialization

Structs offer free memberwise initialization, so you get an initializer for free that looks something like this:

var q = Queue(elements: [4, 5])

I find it more aesthetically pleasing to initialize using a standard array with inferred types:

var q: Queue<String> = [] // Queue<String>
var p: Queue = [1, 2, 3] // Queue<Int>

This behavior is courtesy of ArrayLiteralConvertible, and it’s really simple to implement. Just declare conformance and add an extra initializer:

/// A first-in/first-out queue of unconstrained size
/// - Complexity: push is O(1), pop is O(`count`)
public struct Queue<T>: ArrayLiteralConvertible {
    /// backing array store
    public private(set) var elements: Array<T> = []
 
    /// introduce a new element to the queue in O(1) time
    public mutating func push(value: T) { elements.append(value) }
 
    /// remove the front of the queue in O(`count` time
    public mutating func pop() -> T { return elements.removeFirst() }
 
    /// test whether the queue is empty
    public var isEmpty: Bool { return elements.isEmpty }
 
    /// queue size, computed property
    public var count: Int { return elements.count }
 
    /// offer `ArrayLiteralConvertible` support
    public init(arrayLiteral elements: T...) { self.elements = elements }
}

And there you have it, a simple, easy-to-use queue. If you want to adapt this implementation to a Stack, you get O(1) complexity for both push and pop operations using native Swift arrays.

7 Comments

  • What about making the isEmpty var private and calling if from within pop() to detect the stack underflow before it happens. You’d still have to return and optional to support the underflow case, but more “textbook” I guess….?

  • I usually think of push/pop for a Stack, and enqueue/dequeue for a Queue. I also think it’s fairly straightforward, and common, to implement a Queue using a simple linked list (doable in Swift), with just count, head and tail properties. I don’t have to publicly expose the underlying implementation construct (Array in your solution), and all of it’s capabilities. My implementation limits the capabilities exposed to only what I need it to expose. Yes, the implementation is more complex to implement a Queue as a linked list, but you do it once, and usage is straightforward. dequeue() would return an optional T. I would also implement isEmpty() – not a property – based on count.

  • Oh, and I did read what you said about wanting to show off ArrayLiteralConvertible, but I still wouldn’t implement a Queue with an Array. 🙂

  • Isn’t any non-atomic check/do operation like isEmpty subject to race conditions under multi-threaded use?

  • […] Showcase of ArrayLiteralConvertible queues. Personally I never used arrays this way. Anyway it’s interesting way to handle non-realtime streams for examples. […]

  • Interesting implement. Thank you.

  • Is this safe for multi-threaded use? Looks like I could push and pop in two different threads with no protection. How would you protect while modifying?