Data Structure - How to implement a Queue in Swift

Recently revisiting computer science fundamentals, I was interested to see how specific data structure applies to iOS development, starting this week one of most common data structure: the queue.

My daily usage of data structure is often limited to native one available in iOS development: arrays, sets, dictionaries. However, if there is a data structure that isn’t available natively but heavily used in different implementation is the queue. Let’s revisit it’s concept, how to implement one in swift and some concrete usage for it.

Concept

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).

queue-data-structure-swift

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.

Implementation

In Swift, a Queue would be represented as a wrapper around an array. It should also include a way to get enqueue new element as wells consume the first one. Same as other Array and Dictionary type, I’ll be using Struct for this. I’ll make it generic to be reusable.

struct Queue<T> {
  private var elements: [T] = []

  mutating func enqueue(_ value: T) {
    elements.append(value)
  }

  mutating func dequeue() -> T? {
    guard !elements.isEmpty else { 
      return nil
    }
    return elements.removeFirst()
  }

  var head: T? {
    return elements.first
  }

  var tail: T? {
    return elements.last
  }
}

Here is a concrete example. We want to queue a series of customers and serve them in the order they arrived. We’ll use their name for it.

let queue = Queue<String>()
queue.enqueue("Adam")
queue.enqueue("Julia")
queue.enqueue("Ben")

// we have 3 customers to serve, we're going to serve them in order of arrived
let serving = queue.dequeue() // Adam
let nextToServe = queue.head // Julia

So far so good. We know now how to use one. We can also add other properties to make it more handy, like using isEmpty to know whenever the queue has been fully served in our case.

Like any other data structure, you should know how a Queue performs. Here is a representation of its performance with Big O notation:

enqueue() performs at O(1) time and space.
dequeue() might depends of your implementation. On the paper, it should be O(1) time and space (and that’s what makes Queue great). However using removeFirst or removeAt(at: 0), it performs at O(n) time because every items has to shift of one index. For a better performance, we would need to implement our own index to move through elements, like a Circular Queue. This will depends of what you’re looking for.
searchability is a weak spot for a Queue because it’s designed to only access both ends of it. Therefore it performs O(n): going through each element to find the one. For complex search features, it’s probably not the best data structure to use.

Usage

Now that we know the concept of Queue and how to implement a generic one. Let see how it can be used in our daily usage.

Thing is you probably use the same concept in iOS without noticing, some already relies in specific framework. For instance, when you want to execute specific operation, you probably queued them into an NSOperationQueue or DispatchQueue.

That being said, if it’s the same applied there, the implementation might differ under the hood for performance purpose, something I discovered recently here.

Other than that, a Queue fits quite well any use-cases where the information needs to be computed in the specific entry order. For instance, if you build a chat interface, you want to include each message in the same way they have been typed. Queueing them in the same order while sent to a backend service would be a nice way to do it.

Another example, if you build your own text input, the order of letters tapped by user is super important, so you want to display them as they come.

That’s it for today, we saw how useful a Queue can be and how easy it is to implement our own. Hope you’ll give it a try next time.

Happy coding

Where to go from here

Data Structure - How to implement a Queue in Swift

Concept

Implementation

Usage

Benoit Pasquier