Swift Algorithm Club: Swift Queue Data Structure

Learn how to implement a Swift queue, including enqueue, dequeue, and peek, in this step by step tutorial. Includes a downloadable Swift playground!

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.

Note: New to the Swift Algorithm Club? Check out our getting started post first.

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.

Note: Want to learn how the LinkedList works? Check out our Swift linked list tutorial, which walks you through it step by step.

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)

Where To Go From Here?

I hope you enjoyed this tutorial on making a queue!

Here is a SwiftQueue.Finished.playground with the above code. You can also find alternative implementations and further discussion in the queue section of the Swift Algorithm Club repository.

This was just one of the many algorithms in the Swift Algorithm Club repository. If you’re interested in more, check out the repo.

If you have any questions on queues in Swift, please join the forum discussion below!

Note: The Swift Algorithm Club is always looking for more contributors. If you’ve got an interesting data structure, algorithm, or even an interview question to share, don’t hesitate to contribute! To learn more about the contribution process, check out our Join the Swift Algorithm Club article.

If you enjoyed what you learned in this tutorial, why not check out our Data Structures and Algorithms in Swift book, available on our store?

In Data Structures and Algorithms in Swift, you’ll learn how to implement the most popular and useful data structures and when and why you should use one particular datastructure or algorithm over another. This set of basic data structures and algorithms will serve as an excellent foundation for building more complex and special-purpose constructs.

As well, the high-level expressiveness of Swift makes it an ideal choice for learning these core concepts without sacrificing performance.

  • You’ll start with the fundamental structures of linked lists, queues and stacks, and see how to implement them in a highly Swift-like way.
  • Move on to working with various types of trees, including general purpose trees, binary trees, AVL trees, binary search trees and tries.
  • Go beyond bubble and insertion sort with better-performing algorithms, including mergesort, radix sort, heap sort and quicksort.
  • Learn how to construct directed, non-directed and weighted graphs to represent many real-world models, and traverse graphs and trees efficiently with breadth-first, depth-first, Dijkstra’s and Prim’s algorithms to solve problems such as finding the shortest path or lowest cost in a network.
  • And much, much more!

By the end of this book, you’ll have hands-on experience solving common issues with data structures and algorithms — and you’ll be well on your way to developing your own efficient and useful implementations.

Contributors

Comments