8. Queues

Written by Vincent Ngo

We are all familiar with waiting in line. Whether you are in line to buy tickets to your favorite movie or waiting for a printer to print a file, these real-life scenarios mimic the queue data structure.

Queues use FIFO or first-in first-out ordering, meaning the first element added will always be the first to be removed. Queues are handy when you need to maintain the order of your elements to process later.

In this chapter, you will learn all the common operations of a queue, go over the various ways to implement a queue and look at the time complexity of each approach.

Common operations

Let’s establish a protocol for queues:

public protocol Queue {
  associatedtype Element
  mutating func enqueue(_ element: Element) -> Bool
  mutating func dequeue() -> Element?
  var isEmpty: Bool { get }
  var peek: Element? { get }
}

The protocol describes the core operations for a queue:

• enqueue: Insert an element at the back of the queue. Returns true if the operation was successful.
• dequeue: Remove the element at the front of the queue and return it.
• isEmpty: Check if the queue is empty.
• peek: Return the element at the front of the queue without removing it.

Notice that the queue only cares about removal from the front and insertion at the back. You don’t need to know what the contents are in between. If you did, you would probably just use an array.

Example of a queue

The easiest way to understand how a queue works is to see a working example. Imagine a group of people waiting in line for a movie ticket.

The queue currently holds Ray, Brian, Sam and Mic. Once Ray has received his ticket, he moves out of the line. By calling dequeue(), Ray is removed from the front of the queue.

Calling peek will return Brian since he is now at the front of the line.

Now comes Vicki, who just joined the line to buy a ticket. By calling enqueue("Vicki"), Vicki gets added to the back of the queue.

In the following sections, you will learn to create a queue in four different ways:

• Using an array
• Using a doubly linked list
• Using a ring buffer
• Using two stacks

Array-based implementation

The Swift standard library comes with a core set of highly optimized, primitive data structures that you can use to build higher-level abstractions. One of them is Array, a data structure that stores a contiguous, ordered list of elements. In this section, you will use an array to create a queue.

Open the starter playground. To the QueueArray page, add the following:

public struct QueueArray<T>: Queue {
  private var array: [T] = []
  public init() {}
}

Here, you’ve defined a generic QueueArray struct that adopts the Queue protocol. Note that the compiler infers the associated type Element from the type parameter T.

Next, you’ll complete the implementation of QueueArray to conform to the Queue protocol.

Leveraging arrays

Add the following code to QueueArray:

public var isEmpty: Bool {
  array.isEmpty // 1
}

public var peek: T? {
  array.first // 2
}

Using the features of Array, you get the following for free:

1. Check if the queue is empty.
2. Return the element at the front of the queue.

These operations are all O(1).

Enqueue

Adding an element to the back of the queue is easy. Just append an element to the array. Add the following:

public mutating func enqueue(_ element: T) -> Bool {
  array.append(element)
  return true
}

Enqueueing an element is, on average, an O(1) operation. This is because the array has empty space at the back.

In the example above, notice that, once you add Mic, the array has two empty spaces.

After adding multiple elements, the array will eventually be full. When you want to use more than the allocated space, the array must resize to make additional room.

You might find it surprising that enqueueing is an O(1) operation even though sizing is an O(n) operation. Resizing, after all, requires the array to allocate new memory and copy all existing data over to the new array. The key is that this doesn’t happen very often. This is because the capacity doubles each time it runs out of space. As a result, if you work out the amortized cost of the operation (the average cost), enqueueing is only O(1). That said, the worst-case performance is O(n) when the copy is performed.

Dequeue

Removing an item from the front requires a bit more work. Add the following:

public mutating func dequeue() -> T? {
  isEmpty ? nil : array.removeFirst()
}

If the queue is empty, dequeue simply returns nil. If not, it removes the element from the front of the array and returns it.

Removing an element from the front of the queue is an O(n) operation. To dequeue, you remove the element from the beginning of the array. This is always a linear-time operation because it requires all the remaining elements in the array to be shifted in memory.

Debug and test

For debugging purposes, you’ll have your queue adopt the CustomStringConvertible protocol. Add the following at the bottom of the page:

extension QueueArray: CustomStringConvertible {
  public var description: String {
    String(describing: array)
  }
}

Time to try out the queue that you just implemented! Add the following to the bottom of the page:

var queue = QueueArray<String>()
queue.enqueue("Ray")
queue.enqueue("Brian")
queue.enqueue("Eric")
queue
queue.dequeue()
queue
queue.peek

This code puts Ray, Brian and Eric in the queue, then removes Ray and peeks at Brian, but it doesn’t remove him.

Strengths and weaknesses

Here is a summary of the algorithmic and storage complexity of the array-based queue implementation. Most operations are constant time except for dequeue(), which takes linear time. Storage space is also linear.

You have seen how easy it is to implement an array-based queue by leveraging a Swift Array. Enqueue is, on average, very fast, thanks to an O(1) append operation.

There are some shortcomings to the implementation. Removing an item from the front of the queue can be inefficient, as removal causes all elements to shift up by one. This makes a difference for very large queues. Once the array gets full, it has to resize and may have unused space. This could increase your memory footprint over time. Is it possible to address these shortcomings? Let’s look at a linked list-based implementation and compare it to a QueueArray.

Doubly linked list implementation

Switch to the QueueLinkedList playground page. Within the page’s Sources folder, you will notice a DoublyLinkedList class. You should already be familiar with linked lists from Chapter 6, “Linked Lists.” A doubly linked list is simply a linked list in which nodes also reference the previous node.

Start by adding a generic QueueLinkedList to the very end of the page as shown below:

public class QueueLinkedList<T>: Queue {
  private var list = DoublyLinkedList<T>()
  public init() {}
}

This implementation is similar to QueueArray, but instead of an array, you create a DoublyLinkedList.

Next, let’s start conforming to the Queue protocol.

Enqueue

To add an element to the back of the queue, simply add the following:

public func enqueue(_ element: T) -> Bool {
  list.append(element)
  return true
}

Behind the scenes, the doubly linked list will update its tail node’s previous and next references to the new node. This is an O(1) operation.

Dequeue

To remove an element from the queue, add the following:

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

This code checks to see if the list is not empty and the first element of the queue exists. If it doesn’t, it returns nil. Otherwise, it removes and returns the element at the front of the queue.

Removing from the front of the list is also an O(1) operation. Compared to the array implementation, you didn’t have to shift elements one by one. Instead, in the diagram above, you simply update the next and previous pointers between the first two nodes of the linked list.

Checking the state of a queue

Similar to the array implementation, you can implement peek and isEmpty using the properties of the DoublyLinkedList. Add the following:

public var peek: T? {
  list.first?.value
}

public var isEmpty: Bool {
  list.isEmpty
}

Debug and test

For debugging purposes, you can add the following at the bottom of the page:

extension QueueLinkedList: CustomStringConvertible {
  public var description: String {
    String(describing: list)
  }
}

This conformance leverages DoublyLinkedList’s default implementation for the CustomStringConvertible protocol.

That’s all there is to implementing a queue using a linked list! In the QueueLinkedList page of playground, you can try the example:

var queue = QueueLinkedList<String>()
queue.enqueue("Ray")
queue.enqueue("Brian")
queue.enqueue("Eric")
queue
queue.dequeue()
queue
queue.peek

This test code yields the same results as your QueueArray implementation.

Strengths and weaknesses

Let’s summarize the algorithmic and storage complexity of the doubly linked list-based queue implementation.

One of the main problems with QueueArray is that dequeuing an item takes linear time. With the linked list implementation, you reduced it to a constant operation, O(1). All you needed to do was update the node’s previous and next pointers.

The main weakness with QueueLinkedList is not apparent from the table. Despite O(1) performance, it suffers from high overhead. Each element has to have extra storage for the forward and back reference. Moreover, every time you create a new element, it requires a relatively expensive dynamic allocation. By contrast, QueueArray does a faster bulk allocation.

Can you eliminate allocation overhead and maintain O(1) dequeues? If you don’t have to worry about your queue growing beyond a fixed size, you can use a different approach like the ring buffer. For example, you might have a game of Monopoly with five players. You can use a queue based on a ring buffer to keep track of whose turn is coming up next. You’ll take a look at a ring buffer implementation next.

Ring buffer implementation

A ring buffer, also known as a circular buffer, is a fixed-size array. This data structure strategically wraps around to the beginning when there are no more items to remove at the end.

Going over a simple example of how a queue can be implemented using a ring buffer:

You first create a ring buffer that has a fixed size of 4. The ring buffer has two pointers that keep track of two things:

1. The read pointer keeps track of the front of the queue.
2. The write pointer keeps track of the next available slot so that you can override existing elements that have already been read.

Let’s enqueue an item:

Each time you add an item to the queue, the write pointer increments by one. Let’s add a few more elements:

Notice that the write pointer moved two more spots and is ahead of the read pointer. This means that the queue is not empty.

Next, let’s dequeue two items:

Dequeuing is the equivalent of reading a ring buffer. Notice how the read pointer moved twice.

Now, enqueue one more item to fill up the queue:

Since the write pointer reached the end, it simply wraps around to the starting index again. This is why the data structure is known as a circular buffer.

Finally, dequeue the two remaining items:

The read pointer wraps to the beginning, as well.

As a final observation, notice that whenever the read and write pointers are at the same index, the queue is empty.

Now that you have a better understanding of how ring buffers make a queue let’s implement one!

Go to the QueueRingBuffer playground page. Within the page’s Sources folder, you’ll notice a RingBuffer class.

Note: If you want to learn more about the implementation of this class, check out this full walk-through at https://github.com/kodecocodes/swift-algorithm-club/tree/master/Ring%20Buffer.

In the QueueRingBuffer page, add the following:

public struct QueueRingBuffer<T>: Queue {
  private var ringBuffer: RingBuffer<T>

  public init(count: Int) {
    ringBuffer = RingBuffer<T>(count: count)
  }

  public var isEmpty: Bool {
    ringBuffer.isEmpty
  }

  public var peek: T? {
    ringBuffer.first
  }
}

Here, you defined a generic QueueRingBuffer. Note that you must include a count parameter since the ring buffer has a fixed size.

To conform to the Queue protocol, you also created two properties isEmpty and peek. Instead of exposing ringBuffer, you provide helper variables to access the front of the queue and to check if the queue is empty. Both of these are O(1) operations.

Enqueue

Next, add the method below:

public mutating func enqueue(_ element: T) -> Bool {
  ringBuffer.write(element)
}

To append an element to the queue, you simply call write(_:) on the ringBuffer. This increments the write pointer by one.

Since the queue has a fixed size, you must now return true or false to indicate whether the element has been successfully added. enqueue(_:) is still an O(1) operation.

Dequeue

Next add the following:

public mutating func dequeue() -> T? {
  ringBuffer.read()
}

To remove an item from the front of the queue, you simply call read() on the ringBuffer. Behind the scenes, it checks if the ringBuffer is empty and, if so, returns nil. If not, it returns an item from the front of the buffer and increments the read pointer by one.

Debug and test

To see your results in the playground, add the following:

extension QueueRingBuffer: CustomStringConvertible {
  public var description: String {
   String(describing: ringBuffer)
  }
}

This code creates a string representation of the Queue by delegating to the underlying ring buffer.

That’s all there is to it! Test your ring buffer-based queue by adding the following at the bottom of the page:

var queue = QueueRingBuffer<String>(count: 10)
queue.enqueue("Ray")
queue.enqueue("Brian")
queue.enqueue("Eric")
queue
queue.dequeue()
queue
queue.peek

This test code works just like the previous examples dequeuing Ray and peeking at Brian.

Strengths and weaknesses

How does the ring-buffer implementation compare? Let’s look at a summary of the algorithmic and storage complexity.

The ring buffer-based queue has the same time complexity for enqueue and dequeue as the linked list implementation. The only difference is the space complexity. The ring buffer has a fixed size, which means that enqueue can fail.

So far, you have seen three implementations: a simple array, a doubly linked list and a ring buffer.

Although they appear to be eminently useful, you’ll next look at a queue implemented using two stacks. You will see how its spatial locality is far superior to the linked list. It also doesn’t need a fixed size like a ring buffer.

Double-stack implementation

Open the QueueStack playground page and start by adding a generic QueueStack as shown below:

public struct QueueStack<T> : Queue {
  private var leftStack: [T] = []
  private var rightStack: [T] = []
  public init() {}
}

The idea behind using two stacks is simple. Whenever you enqueue an element, it goes in the right stack.

When you need to dequeue an element, you reverse the right stack and place it in the left stack so that you can retrieve the elements using FIFO order.

Leveraging arrays

Implement the common features of a queue, starting with the following:

public var isEmpty: Bool {
  leftStack.isEmpty && rightStack.isEmpty
}

To check if the queue is empty, check that both the left and right stacks are empty. This means that there are no elements left to dequeue, and no new elements have been enqueued.

Next, add the following:

public var peek: T? {
  !leftStack.isEmpty ? leftStack.last : rightStack.first
}

You know that peeking looks at the top element. If the left stack is not empty, the element on top of this stack is at the front of the queue.

If the left stack is empty, the right stack will be reversed and placed in the left stack.

In this case, the element at the bottom of the right stack is next in the queue. Note that the two properties isEmpty and peek are still O(1) operations.

Enqueue

Next add the method below:

public mutating func enqueue(_ element: T) -> Bool {
  rightStack.append(element)
  return true
}

Recall that the right stack is used to enqueue elements.

You simply push to the stack by appending to the array. Previously, from implementing the QueueArray, you know that appending an element is an O(1) operation.

Dequeue

Removing an item from a two-stack-based implementation of a queue is tricky. Add the following method:

public mutating func dequeue() -> T? {
  if leftStack.isEmpty { // 1
    leftStack = rightStack.reversed() // 2
    rightStack.removeAll() // 3
  }
  return leftStack.popLast() // 4
}

1. Check to see if the left stack is empty.

2. If the left stack is empty, set it as the reverse of the right stack.

3. Invalidate your right stack. Since you have transferred everything to the left, just clear it.
4. Remove the last element from the left stack.

Remember, you only transfer the elements in the right stack when the left stack is empty!

Note: Yes, reversing the contents of an array is an O(n) operation. The overall dequeue cost is still amortized O(1). Imagine having a large number of items in both the left and right stack. If you dequeue all of the elements, first it will remove all of the elements from the left stack, then reverse-copy the right stack only once, and then continue removing elements off the left stack.

Debug and test

To see your results in the playground, add the following:

extension QueueStack: CustomStringConvertible {
  public var description: String {
    String(describing: leftStack.reversed() + rightStack)
  }
}

Here, you simply combine the left stack with the reverse of the right stack, and you print all the elements.

Let’s try out the double-stack implementation:

var queue = QueueStack<String>()
queue.enqueue("Ray")
queue.enqueue("Brian")
queue.enqueue("Eric")
queue
queue.dequeue()
queue
queue.peek

Like all of the examples before, this code enqueues Ray, Brian and Eric, dequeues Ray and then peeks at Brian.

Strengths and weaknesses

Let’s look at a summary of the algorithmic and storage complexity of your two-stack-based implementation.

Compared to the array-based implementation, by leveraging two stacks, you were able to transform dequeue(_:) into an amortized O(1) operation.

Moreover, your two-stack implementation is fully dynamic and doesn’t have the fixed size restriction that your ring-buffer-based queue implementation has. Worst-case performance is O(n) when the right queue needs to be reversed or runs out of capacity. Running out of capacity doesn’t happen very often thanks to doubling it every time it happens.

Finally, it beats the linked list in terms of spatial locality. This is because array elements are next to each other in memory blocks. So a large number of elements will be loaded in a cache on first access. Even though arrays require O(n), for simple copy operations, it is a very fast O(n) happening close to memory bandwidth.

Compare the two images below:

A linked list wherein the elements aren’t in contiguous blocks of memory. This non-locality could lead to more cache misses, which will increase access time.

Key points

• Queue takes a FIFO strategy; an element added first must also be removed first.
• Enqueue inserts an element to the back of the queue.
• Dequeue removes the element at the front of the queue.
• Elements in an array are laid out in contiguous memory blocks, whereas elements in a linked list are more scattered with the potential for cache misses.
• Ring-buffer-queue-based implementation is suitable for queues with a fixed size.
• Compared to other data structures, leveraging two stacks improves the dequeue(_:) time complexity to amortized O(1) operation.
• Double-stack implementation beats out linked list in terms of storage locality.