Home iOS & Swift Books Data Structures & Algorithms in Swift

9
Queue Data Structure 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.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

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)

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.

Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below:

© 2021 Razeware LLC

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

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.