Quick Queues in Swift
What is a Queue data structure
You’re probably wondering why we might need queues in the first place. Well, I'm here to hopefully shed some light into the situation. For many algorithms down the road, we need to add items to a list and pull them off from the same list later on. What if the manner we wanted to put in and take out items had to be a specific way? Thankfully, queues are here to save the day.
A quick use case for queues, especially in iOS, is Dispatch Queues. As a brief overview, it uses the GCD (Grand Central Dispatch) API to execute tasks in a First in, First out the order (FIFO). All in all, GCD follows the same rule set that is given in a queue. Hopefully, it is starting to come all together now if not, maybe this analogy will shed some insight into the manner.
Analogy
A simple analogy to visualize how a queue would work is to picture a real-life queue, a line of some sorts. Think of the rules people already follow when they are lining up for their favorite thing in the world. The first person to enter the line is the first one served. Anyone that enters the line from then on has to wait for the person in front of them to finish so they could proceed on. Everyone after has to wait until they are served.
Great! Now… how can we implement this?
Implementation
There are two data structures that come into mind when you want to set up a queue. There are Linked List and Dynamic Arrays. Once you choose either one of them it is up to you to determine which end would be the start or end of the queue. For the rest of the article, I will be using a Linked List to implement my queue.
Enqueue
Since we are using a Linked List for our queue we need to insatiate one. Start by adding the enqueue method. This will be the function that will add an item to your list. Since we want it in the form we can simply append it to the list. As a quick side note, we are mutating the function because we are altering the linked list using enqueue.
Runtime: When I think of the runtime, I like to visualize what is happening with the program and how each element is affected. If we imagine that we added something to the tail of the linked list, we would just set that node as the tail of the list.
It is safe to say that enqueuing an element to the linked list would be O(1). It runs in constant time because we are just appending the item to the beginning and would not require us to shift anything over.
Dequeue
Next, we need to find a way to take that first person in line out of the list. We can accomplish this by implementing a dequeue function to our struct. Let start by setting a guard let statement to both checks if the list is empty and getting the first item in the list. Now we are going to call the .remove method on the first item we set. Make sure the return the element value to make sure we are not throwing this queue off balance in any manner.
Runtime: So now we are taking the item from the head of the linked list and simply deleting it. It would be safe to say that this will have an O(1) runtime. It remains constant time because we just cut off the last node in the linked list and it would require no traversal at all.
Peek
Sweet! We can enqueue and dequeue items in the list properly, but what if I just wanted to return the value in front of the list? I got a perfect function that can help us here. The Peek function! This simple function will just return the first value of the list. Pretty self-explanatory here.
Runtime: I’m pretty sure you can take a wild guess as to what the runtime of this function would be. Since we are returning the front element, it remains as O(1) constant time.
Putting it all together
Take a step back and behold yourself you the queue we’ve implemented! As a whole, a queue is a pretty simple data structure but has many use cases. As you may have noticed as well, all of the operations here are all constant time! With the constructs of a linked list in place. It is really efficient to run a queue into this structure. I hope this article has brought more insight into your knowledge.
