# 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:

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

### Challenge 3: Whose turn is it?

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

``````protocol BoardGameManager {

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

### Challenge 4: Reverse Queue

Navigate to Challenge 4’s playground page to begin.

``````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`.

#### Note:

``````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.

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

### 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
}
}
``````
``````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
}
}

``````
``````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`.

``````class DequeDoubleLinkedList<Element>: Deque {

public init() {}

}
``````
``````var isEmpty: Bool {
list.isEmpty
}
``````
``````func peek(from direction: Direction) -> Element? {
switch direction {
case .front:
return list.first?.value
case .back:
return list.last?.value
}
}
``````
``````func enqueue(_ element: Element, to direction: Direction) -> Bool {
switch direction {
case .front:
list.prepend(element)
case .back:
list.append(element)
}
return true
}
``````
``````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
}
``````
``````extension DequeDoubleLinkedList: CustomStringConvertible {

public var description: String {
String(describing: list)
}
}
``````
``````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)
``````
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.