Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

Before You Begin

Section 0: 6 chapters

Section I: Introduction

Section 1: 3 chapters

Section II: Elementary Data Structures

Section 2: 6 chapters

9. Queue Challenges Written by Vincent Ngo

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

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.