Queue Variations

QUEUE VARIATIONS

Circular QUEUE

A circular queue is one in which the insertion of a new element is done at the very first location of the queue if the last location of the queue is full.

• The position of element to be inserted is calculated as :

rear = (rear + 1) % maxsize

queue[rear] = value .

• The new position after every deletion should be :

front = (front + 1) % maxsize

DOUBLE ENDED QUEUES  (DEQUEUE)

It is a homogenous list of elements in which insertion and deletion operation are performed from both ends thus referred to be as dequeue.

There are two types of dequeues. These two types are due to restrictions put to perform either the insertions or deletions only at one end.

1. Input-restricted dequeue
2. Output-restricted dequeue

Priority Queue

It is a collection of elements such that each element has been assigned a priority and the order in which elements are deleted and processed comes from the following rules:

ü    An element of higher priority is processed first .

ü    Two element with same priority are processed according to the order in which they were added to the queue.

Multiple Queues

• We can maintain two queues in the same array which is possible if one grows from position1 of array and other grows from last position.
• There should be two front and two rear of the two queues.
• Both queues can grow up to any extent from position1 to maximum. Hence there must be check to keep track of total values stored.