Swift Queue

A Queue implementation in Swift with constant (O(1)) time enqueue and dequeue operations that adopts Value Semantics.

Overview

Queue and LinkedList are both value types (structs). LinkedList is composed of Nodes to refer to the next node.

Queue adopts Value Semantics while also maintaining the constant time operations. The copying only takes place on write (mutating) operations when the list's tail is referenced more than once. Copying operates in linear (O(n)) time as it copies the whole list recursively. This is an innate tradeoff we have to make when we want to adopt Value Semantics. However, it only applies when the struct is copied AND mutated.

If it is modified via those functions or only shared and read, there is no copying that takes place. Thus, leaving queue:value and enqueue:value of Queue and append:value, prepend:value, removeFirst functions of LinkedList to operate in constant time (O(1)).

Installation

Add it to your Package list:
Xcode -> File -> Add Packages -> Paste the Repo URL to Search { https://github.com/alpavanoglu/Queue }

Or you can simply copy over the Queue.swift along with LinkedList.swift.

Usage

Construct with an empty initializer:

let queue: Queue<Int> = []

Or an Array:

let queue: Queue = ["one", "two", "three"]

Access the front and rear of the Queue as:

let queue: Queue = ["one", "two", "three"]
queue.front // "three"
queue.rear // "one"

Enqueue:

queue.enqueue("zero") // ["zero", "one", "two", "three"]

And dequeue:

queue.enqueue("dequeue") // ["zero", "one", "two",]