Queue

Imagine that a shoe store opened next door to you, and on the first day they ran a promotion: you could buy a great pair of sneakers for only $10. It is understandable that a lot of customers immediately came running, forming a queue. To speed up the process, the store manager asks the person in line about their foot size, enters this information into the computer and gives the person a piece of paper with their number in the queue. People stand in order of these numbers, go into the store, take the sneakers of their size and go out (not to mix with the queue, they go out through another door). So, the first person in the queue gets out first – it is an illustration of the programming principle called FIFO (First In, First Out), and the data structure that works this way is called a queue.

Of course, it is an intuitive structure, and in general, its principle is very clear. Let's look at some important details and see how queues can be implemented in programming.

Structure

Let's take a closer look at the mentioned queue for sneakers. The manager gave numbers to people – how handy! Before the store doors opened, the first person in the queue had a piece of paper with the number 1 on it. The second one had two, the third one had three, and so on. Looks like array indexes, doesn't it? This is the simplest implementation of a queue – using an array! What will be your data in the array? All the manager knows about those people is the size of their feet, so this will be your data.

To make it more convenient for the manager and the people in the queue, we added some pointers: one to the first person in the queue, with the word FRONT on it, and the other to the last person in the queue, with the word REAR on it. The first person goes to the store, now the person with the number 2 is at the beginning, and the FRONT pointer points at him. A bit later, three more people came for the sneakers, so the pointer REAR points at the last person who joined the queue. Now let's arrange the same pointers for the array – we are, after all, programmers and will work with the array, not with customers. At this moment, the array will look like this (the first person already entered the store, remember?):

Queue operations

As you have already seen, there are only two events in the queue: an element getting into the queue and an element leaving the queue. The operation when you insert an element into the queue is called enqueue, and the element is added by the REAR pointer. If you remove an element, this operation is called dequeue, and the element that was pointed at by FRONT comes out of the queue. Of course, after any of these operations, the corresponding pointer moves.

To sum up:

• The enqueue operation inserts an element at the end of the queue and moves the REAR pointer;

• The dequeue operation removes an element from the beginning of the queue, and the FRONT pointer moves.

Implementation of queue

Array

This topic has analyzed the simplest implementation of a queue – in an array. In such an implementation, FRONT and REAR can simply be numeric variables that store the indices of the corresponding elements. Then you can access both the first element and the last one in a constant time: the enqueue and dequeue operations will take O(1). However, there is a problem with this implementation: adding and removing elements, you move through the array, which means you need an array of an infinite length.

Linked list

The queue can also be implemented in a linked list, in which each element stores a link to the next one. FRONT and REAR are then pointers to the first and last nodes in the list, which again allows you to do insertion and deletion of elements in O(1). But storing a link to the next item in each item means wasting a lot more memory than the data requires.

Implementation in practice

In most projects, you don't need to implement a queue: it already exists in your programming language. So how does it work? Well, it depends on the specific language, but most often it is implemented on an array with some upgrades. It is safe to say that both enqueue and dequeue operations have the O(1) time complexity.

Bonus: where is the queue used?

The simple answer is everywhere. If you've ever printed a bunch of documents at once, you know that the printer has its own queue to print – this is our data structure. If you've heard of the breadth-first search algorithm, it too uses a queue (if not, it's just one of the most important algorithms in the world, you'll learn it soon).

Have you listened to CDs or MP3s? The queue there is used for buffering. The operating system on your PC uses the queue to handle interruptions; your phone sends you a bunch of missed messages after you turn on the Internet, too, thanks to the queue on the server. To sum up, queues are used everywhere around us, they are simple and yet essential.

Conclusion

As promised in the beginning, the queue works on a fairly obvious principle; however, here's what's important to understand about it:

• A queue is a data structure based on the First In, First Out principle.

• A queue supports two operations – enqueue and dequeue – that have a time complexity of $O(1)$.

• A queue can be implemented using different data structures.

With a queue data structure, you can maintain the sequence of data as it arrives and access the first elements with ease, making it ideal for scenarios where order matters.