9.
Queue Challenges
Written by Vincent Ngo
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
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:
In DoubleLinkedList.swift one additional property and function has been added:
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.
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
}
}
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 {
private var list = DoublyLinkedList<Element>()
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)