__Different types of queue__

**Double ended queue or dequeue **

This is a special kind of queue in which insertion or deletion can take place at both ends.

It means we can insert any item at rear end as well as at front end.

In similar way, the item can be deleted from front end as well as from rear end. This is why it is known as double ended queue.

**Input Restricted Queue**

**Output Restricted Queue **

__Priority Queue __

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

An element of higher priority is processed before any element of lower priority.

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

**For** **example**:

We have seen the importance of priority in case of print applications .

Sometimes many users give print command to the printer. At that time if we want quick output for our document . Then, we can set high priority to that document.

**Implementation of structure of a Priority Queue**

There are various ways of implementing the structure of a priority queue and they are:

- Using a simple/circular array
- Multi-queue implementation
- Using a double linked list
- Using a heap tree

**Using a simple/circular array**

a) Starting from the front pointer, traverse the array for an element of the highest priority . Delete this element from the queue.

b) Add the elements at the rear end as earlier using a stable sorting algorithm, sort the elements of the queue, so that the highest priority element is at the front end. When the deletion is required , delete it from the front end only.

**Multi-queue implementation:**

This implementation assumes n different priority values. For each priority Pi there are two pointers Fi and Ri corresponding to front and rear pointers respectively. The elements between Fi and Ri are all of equal priority value Pi.

**Using double linked list**

- It assumes the node structure.
- Elements will be in sorted order according to the priority values.

**Circular Queue **

A circular Queue is having its FRONT and REAR variables as we have in linear queues with their usual meaning.

In this, first element comes first after the last element.

In other words, we can say that if the last location of queue is full then, coming element will be inserted at first position.

So in that case, we can fully utilize memory space of a queue to store elements.

__Algorithm for insertion in circular queue __

CQINSERT(QUEUE, MAX, FRONT, REAR, ITEM)

This algorithm inserts an element ITEM into a QUEUE.

*Step1: (QUEUE already filled?)*

*If FRONT=0 and REAR=MAX-1, or if*

*FRONT=REAR+1, then*

*Write:’Overflow’, and Return.*

*Step2: (Find new value of REAR)*

*If FRONT=-1, then: (Queue initially empty)*

*Set FRONT=0 and REAR=0*

*Else if REAR=MAX, then*

*Set REAR=0*

*Else*

*Set REAR=REAR+1*

*(end of if structure)*

*Step3: Set QUEUE(REAR) =ITEM(this insert new elements)*

*Step4:Return*

__Algorithm for deletion in Circular Queue__

CQINSERT(QUEUE, MAX, FRONT, REAR, ITEM)

This algorithm deletes an element ITEM from a QUEUE.

*Step1: (QUEUE already filled?)*

*If FRONT=-1 , then*

*Write:’Overflow’, and Return.*

*Step2: Set ITEM=QUEUE[FRONT][value assigned to ITEM]*

*Step3: (Find new value of FRONT)*

*If FRONT=-REAR, then: (Queue has only one element to start)*

*Set FRONT=-1 and REAR=-1*

*Else if FRONT=MAX-1, then*

*Set FRONT=0*

*Else*

*Set FRONT=FRONT+1*

*(end of if structure)*

*Step4:Return*

**Program to perform different operations with queue i. e. circular queue such Insert, Delete, size of queue in python**

class circular queue:

#constructor

def_init_(self) :

self. queue=list()

self. head=0

self tail=0

self . maxSize=8

Adding elements to the queue

def en-q(self, data) :

if self. size() ==self.maxsize-1:

return("queue full! ")

self. queue. append(data)

self. tail=self.tail+1) %self.maxsize

return True

Removing elements from the queue

def d-q(self) :

if self. size() ==0:

return(" queue empty! ")

data=self.queue[self.head]

self. head=(self.head+1) %self.maxsize

return data

Calculating the size of the queue.

def size(self) :

if self. tail>=self.head:

return(self.tail-self.head)

return(self.maxsize-(self.head-self.tail))

q=circular queue()

**Output:**

print(q.en-q(1))

print(q.en-q(7))

print(q.d-q(8))

print(q.d-q())