9. Queue Challenges

Written by Vincent Ngo

Think you have a handle on queues? In this chapter, you will explore five different problems related to queues. This serves to solidify your fundamental knowledge of data structures in general.

Challenge 1: Stack vs. Queue

Explain the difference between a stack and a queue. Provide two real-life examples for each data structure.

Challenge 2: Step-by-step Diagrams

Given the following queue:

Provide step-by-step diagrams showing how the following series of commands affects the queue:

enqueue("R")
enqueue("O")
dequeue()
enqueue("C")
dequeue()
dequeue()
enqueue("K")

Do this for the following queue implementations:

1. Array-based
2. Linked list
3. Ring buffer
4. Stack-based

Assume that the array and ring buffer each have an initial size of 5.

Challenge 3: Whose turn is it?

Open the starter project, and navigate to Challenge 3’s playground page to begin.

Imagine that you are playing a game of Monopoly with your friends. The problem is that everyone always forgets whose turn it is! Create a Monopoly organizer that always tells you whose turn it is. Below is a protocol that you can conform to:

protocol BoardGameManager {

  associatedtype Player
  mutating func nextPlayer() -> Player?
}

Challenge 4: Reverse Queue

Navigate to Challenge 4’s playground page to begin.

Implement a method to reverse the contents of a queue.

Hint: The Stack data structure has been included in the Sources folder.

extension QueueArray {

  func reversed() -> QueueArray {
    var queue = self
    // Solution here.
    return queue
  }
}

Challenge 5: Double-ended Queue

A double-ended queue — a.k.a. a deque — is, as its name suggests, a queue where elements can be added or removed from the front or back.

• A queue (FIFO order) allows you to add elements to the back and remove them from the front.
• A stack (LIFO order) allows you to add elements to the back and remove them from the back.

Deque can be considered both a queue and a stack at the same time.

A simple Deque protocol has been provided to help you build your data structure. An enum Direction has been provided to help describe whether you are adding or removing an element from the front or back of the deque. You can use any data structure you prefer to construct a Deque.

Note:

In DoubleLinkedList.swift one additional property and function has been added:

• A property called last has been added to help get the tail element of a double-linked list.
• A function called prepend(_:) has been added to help you add an element to the front of a double-linked list.

enum Direction {
  case front
  case back
}

protocol Deque {
  associatedtype Element
  var isEmpty: Bool { get }
  func peek(from direction: Direction) -> Element?
  mutating func enqueue(_ element: Element,
                        to direction: Direction) -> Bool
  mutating func dequeue(from direction: Direction) -> Element?
}

Solutions

Solution to Challenge 1

Queues have a behavior of first-in-first-out. What comes in first must come out first. Items in the queue are inserted from the rear and removed from the front.

Queue Examples:

1. Line in a movie theatre: You would hate for people to cut the line at the movie theatre when buying tickets!
2. Printer: Multiple people could print documents from a printer in a similar first-come-first-serve manner.

Stacks have a behavior of last-in-first-out. Items on the stack are inserted at the top and removed from the top.

Stack Examples:

1. Stack of plates: Placing plates on top of each other and removing the top plate every time you use a plate. Isn’t this easier than grabbing the one at the bottom?
2. Undo functionality: Imagine typing words on a keyboard. Clicking Ctrl-Z will undo the most recent text you typed.

Solution to Challenge 2

Array

Keep in mind whenever the array is full, and you try to add a new element, a new array will be created with twice the capacity with existing elements being copied over.

Linked list

Ring buffer

Double stack

Solution to Challenge 3

Creating a board game manager is straightforward. All you care about is whose turn it is. A queue data structure is the perfect choice to adopt the BoardGameManager protocol!

extension QueueArray: BoardGameManager {

  public typealias Player = T

  public mutating func nextPlayer() -> T? {
    guard let person = dequeue() else { // 1
      return nil
    }
    enqueue(person) // 2
    return person // 3
  }
}

There are two requirements to adopt this protocol. You first set the typealias equal to the parameter type T. Next, you implement nextPlayer, which works as follows:

1. Get the next player by calling dequeue. If the queue is empty, return nil.
2. enqueue the same person, putting the player at the end of the queue.
3. Return the next player.

The time complexity depends on the queue implementation you pick. For the array-based queue, it is overall _O(n) time complexity. dequeue takes _O(n) time, because it has to shift the elements to the left every time you remove the first element. Test it out:

var queue = QueueArray<String>()
queue.enqueue("Vincent")
queue.enqueue("Remel")
queue.enqueue("Lukiih")
queue.enqueue("Allison")
print(queue)

print("===== boardgame =======")
queue.nextPlayer()
print(queue)
queue.nextPlayer()
print(queue)
queue.nextPlayer()
print(queue)
queue.nextPlayer()
print(queue)

Solution to Challenge 4

A queue uses first-in-first-out, whereas a stack uses last-in-first-out. You can use a stack to help reverse the contents of a queue. By inserting all the contents of the queue into a stack, you reverse the order once you pop every single element off the stack!

extension QueueArray {

  func reversed() -> QueueArray {
    var queue = self // 1
    var stack = Stack<T>() // 2
    while let element = queue.dequeue() { // 3
      stack.push(element)
    }
    while let element = stack.pop() { // 4
      queue.enqueue(element)
    }
    return queue // 5
  }
}

It doesn’t matter what implementation of a queue you pick. As long as it conforms to the Queue protocol, you can generalize it to any queue!

For this solution, you can extend QueueArray by adding a reversed function. It works the following way:

1. Create a copy of the queue.
2. Create a stack.
3. dequeue all the elements in the queue onto the stack.
4. pop all the elements off the stack and insert them into the queue.
5. Return your reversed queue!

The time complexity is overall O(n). You loop through the elements twice. Once for removing the elements off the queue, and once for removing the elements off the stack.

Testing it out:

var queue = QueueArray<String>()
queue.enqueue("1")
queue.enqueue("21")
queue.enqueue("18")
queue.enqueue("42")

print("before: \(queue)")
print("after: \(queue.reversed())")

Solution to Challenge 5

Deque is made up of common operations from the Queue and Stack data structures. There are many ways to implement a Deque. You could build one using a circular buffer, two stacks, an array, or a doubly linked list. The solution below makes use of a doubly linked list to construct a Deque.

First setup the doubly linked list deque as shown below:

class DequeDoubleLinkedList<Element>: Deque {

  private var list = DoublyLinkedList<Element>()
  public init() {}

}

Now you have to conform to the Deque protocol. First, implement isEmpty by checking if the linked list is empty. This is an O(1) operation.

var isEmpty: Bool {
  list.isEmpty
}

Next, you need a way to look at the value from the front or back of the Deque.

func peek(from direction: Direction) -> Element? {
  switch direction {
  case .front:
    return list.first?.value
  case .back:
    return list.last?.value
  }
}

To peek(_:) at the element from the front or back, check the list’s first and last values. This is an O(1) operation since you need to look at the head and tail of the list.

Now you need a way to add elements to the front or back of the Deque.

func enqueue(_ element: Element, to direction: Direction) -> Bool {
  switch direction {
  case .front:
    list.prepend(element)
  case .back:
    list.append(element)
  }
  return true
}

Adding an element to the front or back of a Deque:

1. Front: prepend an element to the front of the list. Internally the linked list will update the new node as the head of the linked list.
2. Back: append an element to the back of the list. Similarly, the linked list will update the new node as the tail of the linked list.

These are both O(1) operations, as all you have to do is update the head or tail previous and next pointers of a node.

Now that we have a way to add elements, how about a way to remove elements?

func dequeue(from direction: Direction) -> Element? {
  let element: Element?
  switch direction {
  case .front:
    guard let first = list.first else { return nil }
    element = list.remove(first)
  case .back:
    guard let last = list.last else { return nil }
    element = list.remove(last)
  }
  return element
}

Removing an element from the front or back of a Deque is simple. Since a doubly linked list references head and tail, you can grab their nodes and disconnect the node’s previous and next pointers.

1. Front: Get the first (head) node in the list and remove it.
2. Back: Similarly, get the last (tail) node in the list and remove it.

Similar to enqueue(_:), this is an O(1) operation.

Lastly, add the following CustomStringConvertible so you can test your Deque.

extension DequeDoubleLinkedList: CustomStringConvertible {

  public var description: String {
    String(describing: list)
  }
}

That’s all there is to building a Deque! Add the following code below to test your implementation:

let deque = DequeDoubleLinkedList<Int>()
deque.enqueue(1, to: .back)
deque.enqueue(2, to: .back)
deque.enqueue(3, to: .back)
deque.enqueue(4, to: .back)

print(deque)

deque.enqueue(5, to: .front)

print(deque)

deque.dequeue(from: .back)
deque.dequeue(from: .back)
deque.dequeue(from: .back)
deque.dequeue(from: .front)
deque.dequeue(from: .front)
deque.dequeue(from: .front)

print(deque)