Types of Queues

Queue is an abstract data type which can be implemented as a linear or circular list. It has a front and rear.

There are four types of Queue:

1. Simple Queue
2. Circular Queue
3. Priority Queue
4. Dequeue (Double Ended Queue)

Simple Queue

Simple queue defines the simple operation of queue in which insertion occurs at the rear of the list and deletion occurs at the front of the list.

Circular Queue

• In a circular queue, all nodes are treated as circular. Last node is connected back to the first node.
• Circular queue is also called as Ring Buffer.
• It is an abstract data type.
• Circular queue contains a collection of data which allows insertion of data at the end of the queue and deletion of data at the beginning of the queue.

The above figure shows the structure of circular queue. It stores an element in a circular way and performs the operations according to its FIFO structure.

Priority Queue

Priority queue is a type of queue where each element has a priority value and the deletion of the elements is depended upon the priority value. In case of max-priority queue, the element will be deleted first which has the largest priority value and in case of min-priority queue the element will be deleted first which has the minimum priority value.

• Priority queue contains data items which have some preset priority. While removing an element from a priority queue, the data item with the highest priority is removed first.
• In a priority queue, insertion is performed in the order of arrival and deletion is performed based on the priority.

Dequeue (Double Ended Queue)

Double ended queue allows insertion and deletion from both the ends i.e. elements can be added or removed from rear as well as front end.

In Double Ended Queue, insert and delete operation can be occur at both ends that is front and rear of the queue.

There are two variations in Dequeue:

• Input restricted deque: In input restricted double ended queue, the insertion operation is performed at only one end and deletion operation is performed at both the ends.

• Output restricted deque: In output restricted double ended queue, the deletion operation is performed at only one end and insertion operation is performed at both the ends.