Contents

Hide contents

Data Structures & Algorithms in Swift

Before You Begin

Section 0: 6 chapters
Show chapters Hide chapters

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:

W G I H Y

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.

Q Z U B S B G I B V S iyheuoa (“Y”) N D I R F F O ujniiie (“O”) F U N M G E noveuei () F O Z N N U B anfuuou (“P”) I W J H U H quhooia () H L H A Q motoeiu () Y Z K I S W ocxiiiu (“G”)

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”)

Hujz Gsagr P R U K D L U Xaxht Pwocc X E L D S G O Majx Nrejj Dedwf Mxebr wufuaoe () agbaoei (“U”)

Lidf Smoxr I C T K I Z С С Kosfw Rkodp M U X X W I Purm Ghebw Kakxw Nwojc dizeiee () uhpoiou (“D”)

Hovv Gjegk U Q X L С С Xamcm Fcasv Q I D G I Y Yofq Vzamg Derjw Tjikm ifdiooi (“K”) nepeoao ()

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.
© 2022 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.com Professional subscription.

Unlock Now