Queue and its types

                                                             Introduction:                       

A Queue is a simple structure that follows a certain order in which tasks are performed. The order is First in First Out (FIFO). Any consumer line of the device where the first-time buyer is given the first is an excellent illustration of a queue.

Because 1 is retained in line before 2, it is the first to be removed from the line again in the figure above (Follows FIFO rule).

A single-lane one-way road, where the car enters first and departs first, is an example of a queue in the real world. Queues at ticket windows and bus stations are two more real-world examples.

Operations on Queue:

 

On Queue, the four main operations mostly performed are:

· Enqueue: Add an item to the queue. A situation of overflow occurs when a queue is completely filled.

 

· Dequeue: Dequeues an item and removes it from the queue. The sequence in which items are pressed determines how they are displayed. Underflow mode occurs when the queue is empty.

 ·  Front: Locate the queue's previous item.

 · Rear: Locate the final item in the queue.

 

Queue representation:

 

 As we now know, we access both ends of the queue for different reasons. The diagram below attempts to describe queue representation as a data structure –

Types of Queues:

 

There are four different types of queues:

·       Simple Queue:

In a simple queue, the installation occurs in the background while the removal occurs in the front. It upholds the FIFO law  (First Start Out).

 

·       Circular Queue:

The final item in a circular queue points to the first item, forming a circular connection.

A circular queue has a significant benefit over a simple queue in terms of memory utilization. We can put something in the first slot if the last position is full and the first position is empty. On a simple queue, this motion is not feasible.

 

The operation of traffic lights is a great illustration of circular queue performance. The colors of traffic lights are organized in a circular pattern. A circular list of pages is stored in page replacement algorithms, and when the page has to be replaced, the page in front of the line is selected.

 

·       Priority Queue:

 

A priority queue is a form of queue in which each item has a priority and is allocated to it based on that priority. When items with the same value arrive, they are shown in a 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 doesn't follow the FIFO (First In First Out) rule.

There are two types of deque that are discussed as follows -

• Input restricted deque - As the name implies, in input restricted queue, insertion operation can be performed at only one end, while deletion can be performed from both ends.

• Output restricted deque - As the name implies, in output restricted queue, deletion operation can be performed at only one end, while insertion can be performed from both ends.

Conclusion:

 

The queue data structure is a sort of linear data structure for storing elements. The elements in this data structure are stored using the FIFO method. During the implementation of a queue data structure, an array or linked list is used. The REAR end of the queue receives insertions, whereas the FRONT end receives deletions. This data structure is designed to handle many requests from a single shared resource.