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())
| 
| 
