The Queue Data Structure.

Photo by Adrien Delforge on Unsplash

The basics

A queue is a linear data structure that follows an order in which the elements can be accessed. It is very similar to stacks, but the only difference is that a queue is open on both ends. One end is used to add elements, and the other end is used to remove elements. The technical term for adding and removing elements is called Enqueue and Dequeue, respectively.

A simple illustration of the queue data structure.

The exciting part of queues is that we cannot operate upon each element present in the queue. Only the front and the rear of the queue can be accessed or operated upon.

Question: Why don’t we perform operations upon each element of a queue?
Answer: If we can perform operations upon each element of a queue, then there is just no point of queues. Queues then just become an array. In an array, each element can be accessed directly and be operated upon. The application of queues are different compared to that of an array (dicussed in this article).

A queue data structure is a First In First Out (FIFO) data structure. Items in the queue are retrieved in the order in which they are inserted.

Note: To implement a queue data structure, we can make use of an array, stack, or a linked list.

The methods

A queue utilizes these five methods.

1. enqueue() — Adds an element to the queue
2. dequeue() — Removes and returns the first item entered in the queue
3. isEmpty() — Returns true or false based on if the queue is empty or not
4. front() — Returns the front element of the queue
5. print() — Returns all the elements of the queue

Note: the print() function just returns all the elements inside the queue. It is not a way to access a particular element of the queue directly.

A detailed example

A short comic strip, giving a basic idea about the queue data structure.

Now, let us understand the above comic strip a bit technically!

An illustration showing the queue data structure from the comic strip above.

In the above comic strip, four people are waiting at the cash counter to buy books. As soon as the first person pays for the books, he/she exits the queue (the first element is dequeued). Hence, from the original queue — which had all four persons — the 1st element is dequeued, making the 2nd person the first element in the queue. Similarly, when the 2nd person finishes paying for the books, he/she exits the queue (dequeue), after which the 3rd person becomes the first element in the queue. If another person joins the queue, he/she will be added at the top of the queue.

An illustration showing the enqueue() operation in the queue data structure.

This was a simple explanation of how the queue data structure works. Now let us understand the advantages of queues and when you should use them.

The Big O Notation

According to the queue data structure theory, all operations' time complexity should be O(1). For those who do not know what this means, O(1) is the most efficient time complexity a data structure or an algorithm can have. O(1) tells that, even if the number of elements in the queue increase, the time taken for that operation to complete will be constant.

Question: Why is the time complexity O(1)?
Answer: When we are using the enqueue operation, we are adding elements to the rear. There is no need to loop the entire list of elements to complete the operation. Hence, the time complexity is O(1). Similiarly, in the dequeue operation, you are removing elements from the front, and again there is no need to loop all elements; however, this complexity for dequeue changes when implementing a queue using an array.

Question: Why does the time complexity change for queues when it is implemented using an array?
Answer: When the dequeue operation is used in a queue implemented using an array, the time complexity changes to O(N). The reason is simple. Since arrays are based on indexes, whenever an element is removed from the front, each element of the queue should be shifted by a value of -1 (each item’s index should be original index of the element - 1). Hence, the time complexity of the dequeue operation changes. The image below illustrates the same.

Note: The above explanation applies when we implement a queue using an array. If we are using a linked list to implement a queue, the time complexity for enqueue and dequeue operation is O(1).

An illustration of the dequeue operation in a queue implemented using an array.

Application/Uses of the queue data structure

There are multiple use cases of a queue data structure. Something that involves first come, first serve might use queues. Some real-world applications include:

1. Multiplayer video games/battle royale based video games
2. Model physical queues, people waiting in a line for a supermarket checkout
3. When sending data over the internet, various data packets wait in a queue to be sent.
4. A server responding to requests. Usually, these requests are stored in queues. The first-come, first responded policy is followed in such cases.

I have another article on how to implement the queue data structure using arrays in javascript. You can read it here.

If you liked the article, a clap would motivate me to continue writing such articles :)