# What are different types of queue in data structure and algorithm?

0 like 0 dislike
1.3k views

retagged

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

0 like 0 dislike
by (562 points)
edited

# 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

• 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

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

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

• It assumes the node structure.
• Elements will be in sorted order according to the priority values.
1. ## 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.

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.

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 tail=0

self . maxSize=8

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! ")

return data

Calculating the size of the queue.

def size(self) :

q=circular queue()

Output:

print(q.en-q(1))

print(q.en-q(7))

print(q.d-q(8))

print(q.d-q())

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.