Data Structure in Swift: Queue

Let’s rock another data structure in Swift. Queue!

Photo by Melanie Pongratz on Unsplash

Overview

Queue is an abstract data structure that represent queue in real world like the picture above. In computer science terminology, queue is FIFO (First in First out) which mean the first data that come in to the queue also will be the first data come out from the queue. You might need to use queue if you have to maintain the order of the data.

Basic Operations

First of all, let’s define basic protocol for queue here

There are two main operations in queue data structure which are enqueue and dequeue. We also define two additional properties in this protocol.

1. Enqueue
   This operation is add new data to the end of the queue. This function will return true if operation is success.
2. Dequeue
   This operation is remove the first data of the queue. If the queue is not empty, then it should return the data.
3. isEmpty
   This property will check if the queue is empty or not. Will return boolean value.
4. Peek
   This property will get the first data of the queue without removing it.

Imagine queue like this:

In the first state of the queue, there are four person which are Brian, Roy, Tony, and Senvia and they in the line of queue for buying cinema ticket. Then Brian already got the ticket so he will be dequeued from the queue and there will be new person called Quinn and she will be enqueued or inserted to the queue. In this state, the queue is not empty and if we called peek then the the person would be returned is Roy. Hope you understand :].

So how we can create this data structure in Swift? well basically we can create queue with four ways.

1. Array
2. Doubly linked list
3. Ring Buffer
4. Two Stacks

But in this article I will create the queue just using array implementation. Let’s dive to the code.

Implementation

Okay, we created generic QueueArray struct and conform it to Queue protocol that we already created before. Inside it we use array as a storage to enqueue and dequeue the data. Then for isEmpty property we can directly called array.isEmpty for check if there is any data or not in the queue. For peek, because it return optional then we can straight forward to call array.first since peek is return the first data in the queue without removing it. Enqueue is insert new data to the last of the queue, then we can call array.append() and it take O(1) complexity. Then for dequeue, we need to check the current queue is empty or not. If it empty then we return nil otherwise we called array.removeFirst(). But for dequeue operation, it take O(N) because we use array and if we remove the first data in array, we need to move the existing data to the new index one by one. If we have a huge data, then it not recommend to use array as a storage for queue data structure. And you can try another options for create queue such us doubly linked list, ring buffer, or using two stacks.

Key Points

1. Queue is FIFO (First in First out) data structure, which mean the first data that was added to the queue will always be the first data removed from the queue.
2. Use queue if you need to maintain the order of the data. You just need to insert data to the last and remove the first data. You don’t care the data in between them.
3. It not recommend to use array for create queue if you have a huge data set. Because when you call dequeue operation it take O(N) complexity. You can think another option like doubly linked list, ring buffer, or two stacks.