Data Structure in Swift: Queue

Tifo Audi Alif Putra
Apr 2 · 3 min read

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.

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

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.

Geek Culture

Proud to geek out. Follow to join our +500K monthly readers.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store