Circular queue in Data Structure

If rear=max and front is not equal to 0 then insertion cannot be made even if there is sufficient space in the Queue. So there are two solutions.

Solution I: When an element is removed from the queue, then entire queue is shifted to the starting of the queue. But if queue contains many elements so this method is inefficient and it is time consuming process.

Solution II: Convert linear queue into Circular Queue. This queue uses complete space of an array and it is fast process.

Algorithm to insert an element into Circular queue

CIRENQUE (QUEUE, N, FRONT, REAR, ITEM)

This procedure inserts an element item into a Circular queue having maximum N elements.

Step 1: [ Check if queue is full ]

If FRONT = 1 and REAR = N, then

Write (‘Overflow! Queue is full’)

and return.

[ End of If structure ]

Step 2: [ Find the new value for rear ]

If REAR = 0, then

FRONT := 1

REAR := 1

Else

If REAR = N then

REAR := 1

Else

REAR := REAR + 1

[ End of If structure ]

Step 3: [ Insert new element ]

QUEUE[REAR] := ITEM

Step 4: Return.

Algorithm to delete an element from Circular queue

DEQUEUE (QUEUE, N, FRONT, REAR, ITEM)

This procedure deletes an element item from a Circular queue and assigns it to the variable ITEM.

Step 1: [ Check if queue is empty ]

If FRONT = 0, then

Write (‘Underflow! Queue is empty’)

and return.

[ End of If structure ]

Step 2: [ Remove the element ]

ITEM := QUEUE[FRONT]

Step 3: [ Find the new value for rear ]

If FRONT = REAR, then              [ Only one element in queue ]

FRONT := 0

REAR := 0

Else

If FRONT = N, then

FRONT = 1

Else

FRONT := FRONT +1

[ End of If structure ]

Step 4: Return.

PRIORITY QUEUE

A Priority queue is a collection of elements such that each element has been assigned a priority and such that the order in which elements are deleted and processed is according to following rules:

• An element of higher priority is processed before any element of lower
• Two elements with the same priority are processed according to the order in which they were added to the queue.

A prototype of a priority queue is a timesharing system: Programs of high priority are processed first, and programs with the same priority from a standard queue.

Dequeue (Double-Ended queue)

A Dequeue is an ordered set of items from which items may be deleted at either end and into which items may be inserted at either end. The two ends of a queue are called left and right.

Operations on Dequeue are:

Rmvleft, rmvright, insertleft, insertright

To remove and insert elements at the left and right ends of a dequeue. There are two types of Dequeue:

1. Input Restricted Dequeue: Insertion can be made from only one end, whereas deletion can be made from both the ends.

2. Output Restricted Dequeue: Deletions can be made from only one end, whereas insertion can be made from both the ends.