Chapters
Chapters

Chapters

Hide chapters

Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

Before You Begin

Section 0: 6 chapters
Show chapters Hide chapters

Section I: Introduction

Section 1: 3 chapters
Show chapters Hide chapters

Section II: Elementary Data Structures

Section 2: 6 chapters
Show chapters Hide chapters

Section III: Trees

Section 3: 16 chapters
Show chapters Hide chapters

Section IV: Sorting Algorithms

Section 4: 10 chapters
Show chapters Hide chapters

Section V: Graphs

Section 5: 11 chapters
Show chapters Hide chapters

8. Queues
Written by Vincent Ngo

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

We are all familiar with waiting in line. Whether you are in line to buy tickets to your favorite movie or waiting for a printer to print a file, these real-life scenarios mimic the queue data structure.

Queues use FIFO or first-in first-out ordering, meaning the first element added will always be the first to be removed. Queues are handy when you need to maintain the order of your elements to process later.

In this chapter, you will learn all the common operations of a queue, go over the various ways to implement a queue and look at the time complexity of each approach.

Common operations

Let’s establish a protocol for queues:

public protocol Queue {
  associatedtype Element
  mutating func enqueue(_ element: Element) -> Bool
  mutating func dequeue() -> Element?
  var isEmpty: Bool { get }
  var peek: Element? { get }
}

The protocol describes the core operations for a queue:

  • enqueue: Insert an element at the back of the queue. Returns true if the operation was successful.
  • dequeue: Remove the element at the front of the queue and return it.
  • isEmpty: Check if the queue is empty.
  • peek: Return the element at the front of the queue without removing it.

Notice that the queue only cares about removal from the front and insertion at the back. You don’t need to know what the contents are in between. If you did, you would probably just use an array.

Example of a queue

The easiest way to understand how a queue works is to see a working example. Imagine a group of people waiting in line for a movie ticket.

Kjaux Nag Roc Jokdu Hid bfiyc bavg urAsbbj = giwmo emyeiai Hiq Nuj Mmues Xac piveuoo

Array-based implementation

The Swift standard library comes with a core set of highly optimized, primitive data structures that you can use to build higher-level abstractions. One of them is Array, a data structure that stores a contiguous, ordered list of elements. In this section, you will use an array to create a queue.

wukc bmanj Soz Mtuex Zur
A hahzwe Dmupz azxed din ci atas ma ticuv xwa raioi.

public struct QueueArray<T>: Queue {
  private var array: [T] = []
  public init() {}
}

Leveraging arrays

Add the following code to QueueArray:

public var isEmpty: Bool {
  array.isEmpty // 1
}

public var peek: T? {
  array.first // 2
}

Enqueue

Adding an element to the back of the queue is easy. Just append an element to the array. Add the following:

public mutating func enqueue(_ element: T) -> Bool {
  array.append(element)
  return true
}
kons rjivh Xer Ndeaj Jam Zih enfaieu (“Dob”)

tuwh mlogp Xuj Sfuig Cug Gib Vizsa Xlik Upyoy uk dith Ikus Fuq Kruox Yiq Cel Qikse Jjox ehruoui (“Eced”)

Dequeue

Removing an item from the front requires a bit more work. Add the following:

public mutating func dequeue() -> T? {
  isEmpty ? nil : array.removeFirst()
}
tubaiia (“Ziy”) ladh ddujt Tpauw Mub Roy

Debug and test

For debugging purposes, you’ll have your queue adopt the CustomStringConvertible protocol. Add the following at the bottom of the page:

extension QueueArray: CustomStringConvertible {
  public var description: String {
    String(describing: array)
  }
}

var queue = QueueArray<String>()
queue.enqueue("Ray")
queue.enqueue("Brian")
queue.enqueue("Eric")
queue
queue.dequeue()
queue
queue.peek

Strengths and weaknesses

Here is a summary of the algorithmic and storage complexity of the array-based queue implementation. Most operations are constant time except for dequeue(), which takes linear time. Storage space is also linear.

Ehecipeutl Otezugu bilu Kudlk faru aqseeua O(1) U(c) xavoaeo I(j) U(q) Xwize Reldhamand A(f) O(d) Oqhox-Xojol Coioo

Doubly linked list implementation

Switch to the QueueLinkedList playground page. Within the page’s Sources folder, you will notice a DoublyLinkedList class. You should already be familiar with linked lists from Chapter 6, “Linked Lists.” A doubly linked list is simply a linked list in which nodes also reference the previous node.

public class QueueLinkedList<T>: Queue {
  private var list = DoublyLinkedList<T>()
  public init() {}
}

Enqueue

To add an element to the back of the queue, simply add the following:

public func enqueue(_ element: T) -> Bool {
  list.append(element)
  return true
}
Quf Ksuet Vep Law vueh tamm jhoq Xuxcu ehfoaao(“Xuzza”) haij

Dequeue

To remove an element from the queue, add the following:

public func dequeue() -> T? {
  guard !list.isEmpty, let element = list.first else {
    return nil
  }
  return list.remove(element)
}
Qug Gqiaj Yeg Fog bouv jeqeuoa (“Bas”) cihn vcop Xopzi cuud

Checking the state of a queue

Similar to the array implementation, you can implement peek and isEmpty using the properties of the DoublyLinkedList. Add the following:

public var peek: T? {
  list.first?.value
}

public var isEmpty: Bool {
  list.isEmpty
}

Debug and test

For debugging purposes, you can add the following at the bottom of the page:

extension QueueLinkedList: CustomStringConvertible {
  public var description: String {
    String(describing: list)
  }
}

var queue = QueueLinkedList<String>()
queue.enqueue("Ray")
queue.enqueue("Brian")
queue.enqueue("Eric")
queue
queue.dequeue()
queue
queue.peek

Strengths and weaknesses

Let’s summarize the algorithmic and storage complexity of the doubly linked list-based queue implementation.

Usojejeiny Ovezuza nezo Vethn ziso elhoeuo E(6) U(8) lokuooi E(7) U(0) Qrimo Derhyijegz E(w) O(m) Fobtew-Gupf Kofep Kieiu

Ring buffer implementation

A ring buffer, also known as a circular buffer, is a fixed-size array. This data structure strategically wraps around to the beginning when there are no more items to remove at the end.

Hvoci Cail

Zoah Ffuga Xfliw

Xeid Fluvo Xqnox Fafvyuf Jcuhm

Paux Hfiwi Ythox Bumcluc Kxagq

Koot Krubo Llton Saszgof Hlimh Noyme

Roug Vwuyu Kqsup Dohcpin Kzawb Zecji 

public struct QueueRingBuffer<T>: Queue {
  private var ringBuffer: RingBuffer<T>

  public init(count: Int) {
    ringBuffer = RingBuffer<T>(count: count)
  }

  public var isEmpty: Bool {
    ringBuffer.isEmpty
  }

  public var peek: T? {
    ringBuffer.first
  }
}

Enqueue

Next, add the method below:

public mutating func enqueue(_ element: T) -> Bool {
  ringBuffer.write(element)
}

Dequeue

Next add the following:

public mutating func dequeue() -> T? {
  ringBuffer.read()
}

Debug and test

To see your results in the playground, add the following:

extension QueueRingBuffer: CustomStringConvertible {
  public var description: String {
   String(describing: ringBuffer)
  }
}

var queue = QueueRingBuffer<String>(count: 10)
queue.enqueue("Ray")
queue.enqueue("Brian")
queue.enqueue("Eric")
queue
queue.dequeue()
queue
queue.peek

Strengths and weaknesses

How does the ring-buffer implementation compare? Let’s look at a summary of the algorithmic and storage complexity.

Iyasoheodt Okejowa vaqo Mecvr gafo ijpaioe U(0) O(8) hehuooe O(2) U(7) Tdodi Foycsahong A(r) O(n) Moxp-Qoyqam Pisap Wiiau

Double-stack implementation

Open the QueueStack playground page and start by adding a generic QueueStack as shown below:

public struct QueueStack<T> : Queue {
  private var leftStack: [T] = []
  private var rightStack: [T] = []
  public init() {}
}
Gotc Nrayg Saruuee 2 2 2 Gacs Qvotw Humaaee Umxuoeo 2 8 3 Vugcx Qbapf Ubkeuua Cijhz Ttoxz

Leveraging arrays

Implement the common features of a queue, starting with the following:

public var isEmpty: Bool {
  leftStack.isEmpty && rightStack.isEmpty
}

public var peek: T? {
  !leftStack.isEmpty ? leftStack.last : rightStack.first
}

Enqueue

Next add the method below:

public mutating func enqueue(_ element: T) -> Bool {
  rightStack.append(element)
  return true
}
Dulm Zgugt Vuzaeaa 6 Ibgaeee Saxdh Xcuyt 4 9 2

Dequeue

Removing an item from a two-stack-based implementation of a queue is tricky. Add the following method:

public mutating func dequeue() -> T? {
  if leftStack.isEmpty { // 1
    leftStack = rightStack.reversed() // 2
    rightStack.removeAll() // 3
  }
  return leftStack.popLast() // 4
}
Vusk Kbuvz Paneiio 6 0 7 5 Keqv Smorf Weviuui gizaeie() 7 1 4 1 Nerct Jgizq Ovyeuoa Mepfw Jvuyz Uknoeae

Debug and test

To see your results in the playground, add the following:

extension QueueStack: CustomStringConvertible {
  public var description: String {
    String(describing: leftStack.reversed() + rightStack)
  }
}

var queue = QueueStack<String>()
queue.enqueue("Ray")
queue.enqueue("Brian")
queue.enqueue("Eric")
queue
queue.dequeue()
queue
queue.peek

Strengths and weaknesses

Let’s look at a summary of the algorithmic and storage complexity of your two-stack-based implementation.

Asohaneoml Apakapa bigi Guqqy silo uffaoaa E(1) E(m) yuneaoo O(7) I(r) Fpihe Tasjfiqedy E(z) A(x) Juokdo Qteln Wagar Duuuo

5 2 1 4 1 3

3 5 6 1 7 1

Key points

  • Queue takes a FIFO strategy; an element added first must also be removed first.
  • Enqueue inserts an element to the back of the queue.
  • Dequeue removes the element at the front of the queue.
  • Elements in an array are laid out in contiguous memory blocks, whereas elements in a linked list are more scattered with the potential for cache misses.
  • Ring-buffer-queue-based implementation is suitable for queues with a fixed size.
  • Compared to other data structures, leveraging two stacks improves the dequeue(_:) time complexity to amortized O(1) operation.
  • Double-stack implementation beats out linked list in terms of storage locality.
7. Linked List Challenges
9. Queue Challenges
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 accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now