Implementing a Queue 3-Ways Fast AF

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. It is often used to store items that need to be processed in a specific order, such as tasks in a task scheduler or messages in a messaging system. In this tutorial, we will explore multiple ways to build a queue in Swift and understand how they work.

Method 1: Using an Array

The most straightforward way to implement a queue in Swift is to use an array. An array can store items in a linear fashion, and we can use its append() and removeFirst() methods to add and remove items from the queue, respectively. Here’s an example of how we can build a queue using an array:

struct Queue<T> {
  private var elements = [T]()
  
  mutating func enqueue(_ element: T) {
    elements.append(element)
  }
  
  mutating func dequeue() -> T? {
    return elements.isEmpty ? nil : elements.removeFirst()
  }
  
  func peek() -> T? {
    return elements.first
  }
  
  var isEmpty: Bool {
    return elements.isEmpty
  }
}

To use this queue, we can do the following:

var queue = Queue<Int>()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

print(queue.peek()) // Output: 1
print(queue.dequeue()) // Output: 1
print(queue.dequeue()) // Output: 2
print(queue.dequeue()) // Output: 3
print(queue.dequeue()) // Output: nil

This method is simple and easy to understand, but it has a downside: it is not very efficient. The append() and removeFirst() methods have a time complexity of O(1) and O(n), respectively, meaning that they can become slow when the queue grows large.

Method 2: Using a Linked List

To improve the performance of our queue, we can use a linked list instead of an array. A linked list is a linear data structure that consists of nodes that are connected to each other via pointers. Each node holds a value and a reference to the next node. To implement a queue using a linked list, we can create a node class and a queue class:

class Node<T> {
  var value: T
  var next: Node<T>?
  
  init(value: T) {
    self.value = value
  }
}

class Queue<T> {
  private var head: Node<T>?
  private var tail: Node<T>?
  
  func enqueue(_ element: T) {
    let newNode = Node(value: element)
    if let tailNode = tail {
      tailNode.next = newNode
    } else {
      head = newNode
    }
    tail = newNode
  }
  
  func dequeue() -> T? {
    guard let headNode = head else { return nil }
    head = headNode.next
    if head == nil {
      tail = nil
    }
    return headNode.value
  }
  
  func peek() -> T? {
    return head?.value
  }
  
  func isEmpty() -> Bool {
    return head == nil
  }
}

To use this queue, we can do the following:

var queue = Queue<Int>()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

print(queue.peek()) // Output: 1
print(queue.dequeue()) // Output: 1
print(queue.dequeue()) // Output: 2
print(queue.dequeue()) // Output: 3
print(queue.dequeue()) // Output: nil

Using a linked list has several advantages over using an array. First, inserting and deleting items from a linked list has a time complexity of O(1). Second, a linked list does not have a fixed size, so we can add as many items as we want without worrying about running out of space.

Method 3: Using a Swift Standard Library

Swift provides a built-in queue data structure called Queue, which is part of the Swift Standard Library. It is implemented as a doubly-linked list, which means that each node has a reference to the previous node as well as the next node. Here’s how we can use the Swift Standard Library’s Queue:

var queue = Queue<Int>()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

print(queue.peek()) // Output: 1
print(queue.dequeue()) // Output: 1
print(queue.dequeue()) // Output: 2
print(queue.dequeue()) // Output: 3
print(queue.dequeue()) // Output: nil

The Swift Standard Library’s Queue has several convenient methods such as isEmpty, count, and front, which allow us to easily manipulate the queue. It also has a mutating version of each method, so we can use it as a mutable queue. Conclusion In this tutorial, we learned three different ways to implement a queue in Swift: using an array, using a linked list, and using the Swift Standard Library’s Queue. Each method has its own pros and cons, and we should choose the one that best fits our needs. If you want to learn more about queues and other linear data structures, you can check out the following resources:

Swift Standard Library: https://developer.apple.com/documentation/swift/queue

Data Structures and Algorithms in Swift https://www.raywenderlich.com/150-swift-algorithm-club-data-structures