Books Online Courses
Free Tutorials  Go to Your University  Placement Preparation 
Latest:- Important tips to get an Off Campus Placements
0 like 0 dislike
1.1k views
in Examples, Exercises and Projects by (562 points)
retagged by

In this article you will get to know about 

  1. circular queue, priority queue, double ended queue with its types
  2. Program to perform different operations with queue. 

1 Answer

0 like 0 dislike
by (562 points)
edited by
 
Best answer

Different types of queue

  1. 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.

  • There are two types of Dequeue

  • Input Restricted Queue

  • Output Restricted Queue

Input Restricted Queue

input restricted queue

  • It is a dequeue in which insertions allows only at one end whereas deletion from both ends i. e. front end as well as rear end.

Output Restricted Queue

output restricted queue

  • It is a dequeue in which deletions allows only from one end whereas insertion allows from both ends.

  1. Priority 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.
  1. Circular Queue

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

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

3.3k questions

7.1k answers

395 comments

4.6k users

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 
...