What is a Queue?

Introduction

Similar to the stack, a queue is another linear data structure that stores elements in a sequential manner. The only significant difference between stack and queue is that instead of using the LIFO principle, queue implements the First in First Out (FIFO) method.

According to FIFO, the first element inserted is the one that comes out first. You can think of a queue as a pipe with both ends open. Elements enter from one end (back) and leave from the other (front). The following animation illustrates the structure of a queue.

Queues are slightly trickier to implement compared to stacks because you have to track both ends of the array. The elements are inserted from the back and removed from the front.

A perfect real-life example of a queue is when a line of people is waiting to get a ticket at the booth. If a new person comes, they will join the line from the end, and the person standing at the front will be the first to get the ticket and leave the line.

What are queues used for?

Just like stacks, queues are also used widely in searching and sorting algorithms such as the “breadth first search algorithm”.

Most operating systems also perform operations based on a priority queue (a kind of queue), which allows operating systems to switch between appropriate processes. They are also used to store packets on routers in a certain order when a network is congested. Implementing a cache also heavily relies on queues. You generally use queues when:

• You want to prioritize something over another
• A resource is shared between multiple devices

How does a queue work?

A typical queue needs the following set of functions to work perfectly. These operations are listed below in the table:

Function	What does it do?
enqueue(value)	Inserts element to the end of queue
dequeue()	Removes an element from the start of queue
getFront()	Returns the first element of the queue
isEmpty()	Checks if the queue is empty

The entire functionality of queues depends on the first two functions, and the rest are just helper functions to produce simple and understandable code.

Types of queues

Listed below are the three most common types of queues:

• Linear queue
• Circular queue
• Priority queue

The queue that has been discussed so far is a linear queue. Examine the last two types, and see how they are different from a linear queue.

Circular queue

Circular queues are almost similar to linear queues but with one exception. As the name suggests, circular queues are circular in structure, which means that both ends are connected to form a circle. Initially, the front and rear part of the queue point to the same location and eventually move apart as more elements are inserted into the queue. Circular queues are generally used in:

• Simulation of objects
• Event handling (doing something when a particular event occurs)

Priority queue

In priority queues, all elements have a priority associated with them and are sorted such that the most prioritized object appears at the front, and the least prioritized object appears at the end of the queue. These queues are widely used in most operating systems to determine which programs should be given more priority.

---