Introduction to data structures: Queue

Learn about the queue data structure in an intuitive way

November 18th, 2024 3 minute read

The queue data structure should be one of the more intuitive data structures. The reason is that we spend so much of our time waiting in lines (i.e. queues).
The queue data structure follows an interesting principle called "first in first out" or FIFO for short.
Let's learn what the queue data structure is and how it works.

We mentioned that we spend a lot of our time in queues. Let's give a few examples:

When we wait in line to pay for groceries.
When we want to get into a venue (e.g. concert, cinema).
When we are at a traffic stop.

Queues are used when there are more items than can be handled (i.e. processed) and there is a need to store them and handle them at a later time.
In the example with the groceries there is a queue because there are more customers than there are employees working at the registers.
In the example with the venue, there is a queue because there are more people that want to get into the vanue than there are enterances to the venue.

What is the FIFO principle?
The FIFO principle states that the first item that was inserted into the queue is the first one to be removed from the queue.
In our example with the groceries, the first person that entered the queue (i.e. line) is the first person to pay for their groceries. Someone could of course "cut the line" and try to pay for their groceries before the people in front of them, but that is not very nice.
In programming "cutting the line" or removing items from positions other than the front of the queue is not allowed.

The queue data structure usually provides the following operations:

enqueue - used to insert an item at the back of the queue.
dequeue - used to remove an item from the front of the queue.
peek - used to "see" what item is at the front of the queue without removing it.
isEmpty - used to check if the queue is empty.
size - used to check how many items are in the queue.

Let's give a few practical uses of the queue data structure:

JavaScript callback queue - JavaScript is a single threaded programming language. Callback functions that need to be executed in response to certain events (e.g. keyboard press, mouse click) in most cases can not be processed immediately after the event happens. They have to be placed into a queue and processed at a later time. The JavaScript runtime will pick up the callback functions from the callback queue and process them in FIFO order when appropriate.
Server request queue - A server might not be able to process every client request immediately (e.g. if there are more client requests than sever resources). In such a case, the server can queue the requests and process them in FIFO order.

How do queues work internally?
The queue data structure usually uses a linked list internally. It can also work with an array, but the linked list offers greater flexibility which goes well with the dynamic nature of queues (i.e. they change their size often).

If you enjoy my articles, please consider supporting me.