## Swift Algorithm Club: Swift Queue Data Structure

Chris Pilcher

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 function. 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()   // 2 public mutating func enqueue(_ element: Int) { list.append(element) }```

Here’s what you’ve done:

1. You’ve added private `LinkedList` variable that will be used to store the items in your queue.
2. You’ve added a function to enqueue items. This function 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 function.

 ```// 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` function that returns the first item in the queue. The return type is `nullable` to handle the queue being empty. This function 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 function which returns the item at the beginning of the queue without removing it.

Try updating the implementation of `Queue` to include a peek function.

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

Solution Inside: Solution SelectShow

### 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 our queue.

Update the implementation of your `Queue` class to the following:

 ```// 1 public struct Queue {   // 2 fileprivate var list = LinkedList()   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() queue.enqueue(10) queue.enqueue(3) queue.enqueue(57)```

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

 ```var queue2 = Queue() 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 algorithm clubs focused on 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.

## Team

Each tutorial at www.raywenderlich.com is created by a team of dedicated developers so that it meets our high quality standards. The team members who worked on this tutorial are:

Chris Pilcher

I'm a software developer based in Auckland, New Zealand. I help maintain the Swift Algorithm Club.

Outside of coding, I enjoy video games and skydiving.

# raywenderlich.com Weekly

Sign up to receive the latest tutorials from raywenderlich.com each week, and receive a free epic-length tutorial as a bonus!

... 19 total!

... 16 total!

... 30 total!

... 15 total!

... 11 total!

... 10 total!

... 11 total!

... 11 total!

... 11 total!