Queue and it’s types

Introduction:

A Queue is a straightforward structure that follows a certain order in which tasks are performed. The order is First in First Out (FIFO). A good example of a queue is any consumer line of the device where the first-time buyer is given the first.

In the image above, as 1 is kept in line before 2, it is the first to be removed from the line again (Follows FIFO rule).

A real-world example of queue can be a single-lane one-way road, where the vehicle enters first, exits first. More real-world examples can be seen as queues at the ticket windows and bus-stops.

Operations on Queue:

Mainly the following four basic operations are performed on queue

1) Enqueue: Add an item to the queue. When the queue is full, it is called a state of overflow.

2) Dequeue: Removes an item from the queue. Items are displayed in the order in which they are pressed. If the queue is empty, it is called Underflow mode.

3) Front: Find the previous item in the queue.

4) Rear: Find the last item in line.

Queue representation:

As we now understand that in queue, we access both ends for different reasons. The following diagram given below tries to explain queue representation as data structure −

Types of Queue:

There are four different types of queues:

• Simple Queue:

In a simple queue, the installation takes place in the background and the removal takes place in the front. It strictly adheres to the FIFO law (First Start Out).

• Circular Queue:

In a circular queue, the last item points to the first item that forms the circular link.

The great advantage of a circular queue on a simple queue is better memory usage. If the last position is full and the first position is empty, we can put something in the first place. This action is not possible on a simple line.

Traffic light performance is an excellent example for circular queue. Colors in traffic light follow a circular pattern .In page replacement algorithms, a circular list of pages is saved and when the page needs to be changed, the page in front of the line will be selected.

• Priority Queue:

A priority queue is a special type of queue where each item is associated with a priority and is assigned according to its priority. When elements of the same value arrive, they are presented in chronological order.

Insertion occurs based on the arrival of the values and removal occurs based on priority. Prism’s algorithm , Dijkstra’s shortest path algorithm , A* Search algorithm can be done using priority queue.

• Deque (Double ended queue):

In a double ended queue, insertion and removal of elements can be performed from either from the front or rear. Thus, it does not follow the FIFO (First In First Out) rule.

-Videhi Bavishi