9.
Queue Data Structure Challenges
Written by Vincent Ngo
Heads up... You’re accessing parts of this content for free, with some sections shown as text.
Heads up... You’re accessing parts of this content for free, with some sections shown as 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 doubled-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 basically 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)