Data Structures & Algorithms in Swift: Part 2— Queue

Published in

The Startup

4 min readApr 15, 2020

What is Queue?

Queue is a linear data structure which follows a particular order in terms of which operations are performed (FIFO — First in first out). It is named as queue because it behaves like any real world queue that you may encounter. For example a queue of humans waiting outside a store. If you consider that queue humans can enter a queue at the end and anyone can leave the queue from the front.

Operations on Queue

We will use an array for internal storage of the Queue as it gives us easy methods for adding & removing elements.

ENQUEUE

Enqueuing means to add an element at end of the queue. It simply means we will add an element to the end of array which is a constant time operation. So time complexity for Enqueuing will be O(1) in most cases. But in some cases if the array is full while enqueuing an element Swift will create a new array of double size and move all the elements to the new array, this will be a linear time operation O(n).

DEQUEUE

Dequeuing means to remove an element from the front of the queue. It simply means we will remove an element from the front of the array. Removal of first element is a 2 step process, in first step the element will be removed from the array and in second step all the remaining elements will be moved to their left side to fill the first empty index. Here the good news is Swift automatically does this for us when we can removeFirst() method on an array. Moving all the elements to its left is a linear time operation O(n).

We will have a computed property isEmpty which will tell us whether the queue is empty or not. We will simply check the count of the array, if count is 0 that means our queue is empty

Implementation of Queue

Open Xcode and create a new playground Queue

Let’s break down the code line by line and understand what actually is happening at each step.

We are creating a generic queue which means it can be used to create a queue of Int, Float, Double, String etc etc.
Queue confirms to the protocol Equatable which provides a default functionality of comparing to different queues.

We are creating an array called internalStorage which will be used as a storage container for our queue.

We have two different initialisers: first one is to create an empty queue & second one to create a queue with some elements in it. We can simply pass an array of elements during initialisation and all those elements will be enqueued. You’ll notice one thing that we are using mutating keyword before dequeue and enqueue operation methods, this is because Swift does not allow instance methods of value types to alter their properties. So we have to provide additional information to the instance methods that will be used to alter the properties.

We have created a computed property isEmpty which internally checks whether the array is empty or not. If the array is empty it will return true otherwise false.

We have added an extension to our queue implementation which just converts all the elements of the queue to string and prints them as comma separated value. So basically whenever we do something like print(queue) , it will print all the elements of the queue in a comma separated format.

How to use this Queue?

Let’s start by creating a queue with 0 elements and perform some enqueue and dequeue operations on it.

2. We can do similar operations on a queue of String or any other type which confirms to the Equatable protocol.

3. Let’s take a look at using Equatable protocol which makes it very easy for us to compare two different queues. Without this protocol we would have to loop through both the queues and compare value at each index one by one.
Remember we created two different initialisers in our Queue , we will use second one in this example which gets initialised by an array and enqueues all the elements in the queue.

Can we do better?

Our current implementation of queue has a good time complexity in case of enqueue operation but the time complexity of dequeue is O(n) which can be improved if we use two stacks as internal storage instead of an array. In that case time complexity of both the operations will be O(1). We are not going to cover that implementation in this part but you should definitely think and try to implement a queue using two stacks.