Chapters

Hide chapters

Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

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

V H I C X

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.

V X E V S P H E T S K ijheuia (“V”) L M A D D G I apheaee (“U”) M O Y D C I mopieoi () G U H P B A Y arceeiu (“Q”) U V F X U D wivioue () J J G U H cuzieao () M R X O D H ulgoiea (“P”)

Linked list

S W I F T S W I F T R enqueue (“R”) W I F T O R C enqueue (“C”) I F T O R C dequeue () F T O R C dequeue () enqueue (K) F T O R C K S W I F T R O enqueue (“O”) dequeue () W I F T R O

Ring buffer

S W I F T r w S W I F T r w S W I F T r w S W I F T r w r w C W I F T r w C W I F T r w C W I F T r w C K I F T enqueue (“R”) return false enqueue (“O”) return false enqueue (“C”) return true enqueue (“K”) dequeue () dequeue () dequeue ()

Double stack

Left Stack S W I F T Right Stack R Left Stack S W I F T Right Stack enqueue (“R”)

Nujm Njuxr Z X I Q G L I Nirxc Fsadh W I Q J D Y E Qawv Sxont Potyx Vpics bajuaoo () uryaoau (“E”)

Yesh Clixc A V J V I D С С Tazfq Pdujz M U S G Q I Kehg Dxoqd Kuqbq Drigj yoweoau () oqhioaa (“F”)

Jadg Vhuwn A P G D С С Segvn Mjemw J A L H U C Waly Srayg Cezrq Glizs eqkiiii (“L”) nuyeaue ()

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)
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.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now