Swift Queue Data Structure Implementation

Filed Under: Swift

In this tutorial, we’ll be discussing and implementing the Data structure Queues using Swift. We’ll create Swift Queues using Array and LinkedList separately.

Swift Queue Data Structure

Queues are a data structure in which you can insert new data from one end and delete data from the other end. That means it works like FIFO – First In First Out.

swift queue flow

Enqueue operation is used to insert an element at the beginning.

Dequeue operation is used to remove an element from the end.

In the following section, we’ll create a Queue structure using an Array.

Open up your Swift Playground in XCode and let’s start coding.

Queue – Enqueue, Dequeue

Following is the code for our Queue:


struct Queue{
    
    var items:[String] = []
    
    mutating func enqueue(element: String)
    {
        items.append(element)
    }
    
    mutating func dequeue() -> String?
    {
        
        if items.isEmpty {
            return nil
        }
        else{
            let tempElement = items.first
            items.remove(at: 0)
            return tempElement
        }
    }
    
}

The Queue is an Array of Strings.

The enqueue method appends a string to the last.

The dequeue method removes the first string.

In the dequeue function, we return an optional type since the array can be empty, in which case a nil would be returned wrapped in the optional.

Following is the output of our operations on the above queue.

swift queue implementation example

We can create a Generic Swift Queue in order to use it for all types.

The below illustration refactors the above code by using a generic type T in place of String.

swift queue generic

In the next section, we’ll create a Swift Queue using a LinkedList in place of Array.

Swift Queue Using LinkedList

First create a class that holds the LinkedList data structure:


public class LinkedList<T> { 
    var data: T
    var next: LinkedList?
    public init(data: T){
        self.data = data
    }
}

The class consists of data and a reference to the next Node of the LinkedList.

Since each element of a LinkedList is commonly known as Node, we can rename the above class type to Node using typealias.


public class Queue<T> {
    typealias LLNode = LinkedList<T>
    var head: LLNode!
    public var isEmpty: Bool { return head == nil }
    var first: LLNode? { return head }
    var last: LLNode? {
        if var node = self.head {
            while case let next? = node.next {
                node = next
            }
            return node
        } else {
            return nil
        }
    }

    func enqueue(key: T) {
        let nextItem = LLNode(data: key)
        if let lastNode = last {
            lastNode.next = nextItem
        } else {
            head = nextItem
        }
    }
    func dequeue() -> T? {
        if self.head?.data == nil { return nil  }
        if let nextItem = self.head?.next {
            head = nextItem
        } else {
            head = nil
        }
        return head?.data
    }
}

first Node points to the same reference as the head. It represents the first Node of the LinkedList present in the queue.

In the enqueue function, we go until the end of the LinkedList by setting the head to next Node until the next is nil. This is done in if let.

In the dequeue, we remove the reference of the first Node by setting head to the next node.

while case let is similar to if let in Swift except the fact that it’s used in loops.

Double Ended Queue

A Double Ended Queue lets you add and remove elements at both ends of the queue. That means besides the enqueue, dequeue functions, you need to add two additional equeueFront and dequeueBack functions too.

Following code shows a Double Ended Queue structure using an Array.


public struct Deque<T> {
    private var items = [T]()
    
    mutating func enqueue(element: T) {
        items.append(element)
    }
    
    mutating func enqueueFront(element: T) {
        items.insert(element, at: 0)
    }
    
    mutating func dequeue() -> T?{
        if items.isEmpty {
            return nil
        } else {
            return items.removeFirst()
        }
    }
    
    mutating func dequeueBack() -> T? {
        if items.isEmpty {
            return nil
        } else {
            return items.removeLast()
        }
    }
}

swift doubly queue implementation

In the above illustration, enqueueFront adds the new element before the current one. deuqueBack() deletes the last element from the queue.

This brings an end to this quick tutorial on Swift Queue data structure implementation.

Comments

  1. iOSDev says:

    Could you please tell me How we can use a class instead of structure to perform queue operation? and also is there any way to update an element inside the queue?

  2. iOSDev says:

    it is remove(at: o(zero index)) which O(1).

  3. Ashish says:

    The dequeue implementation in the queue implemented with array is wrong since its supposed to be an O(1) operation. But since you are using remove(at: 0) which is an O(n) operation, it doesntfulfil the requirement.

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages