Swift Algorithm Club: Swift Queue Data Structure

The Swift Algorithm Club is an open source project on implementing data structures and algorithms in Swift.

Every month, Kelvin Lau and I feature a cool data structure or algorithm from the club in a tutorial on this site. If you want to learn more about algorithms and data structures, follow along with us!

In this tutorial, you’ll learn how to implement a queue in Swift 3. A queue is one of the most popular data structures, and is fairly simple to implement in Swift.

The queue implementation was first implemented by Matthijs Hollemans, the founder of the Swift Algorithm Club.

Getting Started

A queue is a list where you can only insert new items at the back and remove items from the front. This ensures that the first item you enqueue is also the first item you dequeue. First come, first serve!

Why would you need this? Well, in many algorithms you want to add items to a temporary list at some point and then pull them off this list again at a later time. Often the order in which you add and remove these items matters.

A queue gives you a FIFO or first-in, first-out order. The element you inserted first is also the first one to come out again. It’s only fair! (A very similar data structure, the stack, is LIFO or last-in first-out.)

An example

The easiest way to understand a queue is to see how it’s used.

Imagine you have a queue. Here’s how you would enqueue a number:

queue.enqueue(10)

The queue would now be [ 10 ]. Then you could add the next number to the queue:

queue.enqueue(3)

The queue would now be [ 10, 3 ]. You could add one more number:

queue.enqueue(57)

The queue would now be[ 10, 3, 57 ]. You could dequeue to pull the first element off the front of the queue:

queue.dequeue()

This would return 10 because that was the first number you inserted. The queue would now be [ 3, 57 ]. Every item moved up by one place.

queue.dequeue()

This would returns 3. The next dequeue would return 57, and so on. If the queue is empty, dequeuing would return nil.

Queue Implementation

In this section, you’ll implement a simple general-purpose queue that stores Int values.

Start by downloading the queue starter project. The playground will contain an empty Queue:

public struct Queue {

}

The playground also contains the code for a LinkedList (you can see this by going to View\Project Navigators\Show Project Navigator and opening Sources\LinkedList.

Enqueue

A queue needs an enqueue method. You’ll use the LinkedList implementation included in the starter project to implement your queue. Add the following between the curly braces:

// 1
fileprivate var list = LinkedList<Int>()

// 2
public mutating func enqueue(_ element: Int) {
  list.append(element)
}

Here’s what you’ve done:

1. You’ve added a private LinkedList variable that will be used to store the items in your queue.
2. You’ve added a method to enqueue items. This method will mutate the underlying LinkedList so you’ve explicitly specified that by prepending the mutating keyword in front of the method.

Dequeue

A queue also needs a dequeue method.

// 1
public mutating func dequeue() -> Int? {
  // 2
  guard !list.isEmpty, let element = list.first else { return nil }

  list.remove(element)

  return element.value
}

Here’s what you’ve done:

1. You’ve added a dequeue method that returns the first item in the queue. The return type is nullable to handle the queue being empty. This method will mutate the underlying LinkedList so you’ve explicitly specified that by prepending the mutating keyword in front of the method.
2. You’re using the guard statement handle the queue being empty. If this queue is empty, then guard will fail into the else block.

Peek

A queue also needs a peek method which returns the item at the beginning of the queue without removing it.

Try updating the implementation of Queue to include a peek method.

The solution is provided in the spoiler section down below, but try it yourself first!

[spoiler title=”Solution”]

public func peek() -> Int? {
  return list.first?.value
}

[/spoiler]

IsEmpty

A queue can be empty. You can add an isEmpty property that will return a value based on the underlying LinkedList:

public var isEmpty: Bool {
  return list.isEmpty
}

Printing Your Queue

Let’s try out your new queue. Outside the implementation of Queue, write the following into your playground:

var queue = Queue()
queue.enqueue(10)
queue.enqueue(3)
queue.enqueue(57)

After defining the queue, try printing the queue to the console:

print(queue)

You can bring up the console by pressing the following keys in combination: Command-Shift-Y. You should see the following printed out to the console:

Queue

That isn’t very helpful. To display a more readable output string, you can make Queue adopt the CustomStringConvertable protocol. To do this, add the following just below the implementation of your Queue class:

// 1
extension Queue: CustomStringConvertible {
  // 2
  public var description: String {
    // 3
    return list.description
  }
}

Here’s how the code works:

1. You’ve declared an extension to your Queue class, and you’ve adopted the CustomStringConvertible protocol. This protocol expects you to implement a computed property with the name description, with the String type.
2. You’ve declared the description property. This is a computed property, a read only property that returns a String.
3. You’re returning the description of the underlying LinkedList.

Now, when you call print on your Queue, you’ll get a nice representation of your list like this:

"[10, 3, 57]"

Generic Swift Queue Implementation

At this point, you’ve implemented a general-purpose queue that stores Int values, and have provided functionality to peek, enqueue and dequeue items in your Queue class.

In this section, you will use generics to abstract away the type requirement from your queue.

Update the implementation of your Queue class to the following:

// 1
public struct Queue<T> {

  // 2
  fileprivate var list = LinkedList<T>()

  public var isEmpty: Bool {
    return list.isEmpty
  }
  
  // 3
  public mutating func enqueue(_ element: T) {
    list.append(element)
  }

  // 4
  public mutating func dequeue() -> T? {
    guard !list.isEmpty, let element = list.first else { return nil }

    list.remove(element)

    return element.value
  }

  // 5
  public func peek() -> T? {
    return list.first?.value
  }
}

Here’s what you’ve done:

1. You’ve changed the declaration of the Queue to take a generic type T.
2. Your goal is to allow the Queue to take in values of any type, so you’ll constrain your underlying LinkedList to be type T rather than a Int.
3. You’ve updated enqueue to take any type.
4. You’ve updated dequeue to return any type.
5. You’ve updated peek to return any type.

You can fix up your test code as follows:

var queue = Queue<Int>()
queue.enqueue(10)
queue.enqueue(3)
queue.enqueue(57)

And you can even try your Queue with different types as well:

var queue2 = Queue<String>()
queue2.enqueue("mad")
queue2.enqueue("lad")
if let first = queue2.dequeue() {
  print(first)
}
print(queue2)