[DS1] Types of Queue

1. Types of Queues

There are four different types of queues :

• Simple Queue
• Circular Queue
• Priority Queue
• Double Ended Queue

In a simple queue, insertion takes place at the rear and removal occurs at the front. It strictly follows the FIFO(First in First out) rule.

 

In a circular queue, the last element points to the first element making a circular link. The main advantage of a circular queue over a simple queue is better memory utilization. If the last position is full and the first position is empty, we can insert an element in the first position.

 

A pirority queue is a special type of queue in which each element is associated with a prority and is served according to its priority.

 

In a double ended queue(Deque), insertion and removal of elements can be performed from either from the front or rear. Thus, it does not follow the FIFO rule.

 

2. Circular Queue

A circular queue is the extended versio nof a regular queue where the last element is connected to the first element.

The circular queue solves the major limitation of the normal queue. In a normal queue, after a bit of insertion and deletion, there will be non-usable empty space.

 

Circular Queue works by the process of circular increment, when we try to increment the pointer and we reach the end of the queue, we start from the beginning of the queue.

 

2.1 Circular Queue Operation

1. Enqueue Operation
   1. check if the queue is full
   2. for the first element, set value of FRONT to 0
   3. circularly increase the REAR index by 1 (if the REAR reaches the end, next it would be at the start of the queue)
   4. add the new element in the position pointed to by REAR
2. Dequeue Operation
   1. check if the queue is empty
   2. return the value pointed by FRONT
   3. circularly increase the FRONT index by 1
   4. for the last element reset the values of FRONT and REAR to -1

We need to check full queue in additional case :

1. FRONT = 0 & REAR == SIZE - 1
2. FRONT = REAR + 1

2.2 Circular Queue Implementation

class MyCircularQueue(): 
    def __init__(self, k): 
        self.k = k
        self.queue = [None] * k 
        self.head = self.tail = -1
        
    def enqueue(self, data): 
        if (self.tail + 1) % self.k == self.head : 
            print("The circular queue is full")
        elif self.head == -1 : 
            self.head = 0
            self.tail = 0
            self.queue[self.tail] = data
        else : 
            self.tail = (self.tail + 1) % self.k
            self.queue[self.tail] = data 
            
    def dequeue(self): 
        if self.head == -1 : 
            print("The circular queue is empty") 
        elif self.head == self.tail : 
            temp = self.queue[self.head] 
            self.haed = -1 
            self.tail = -1 
            return temp 
        else : 
            temp = self.queue[self.head]
            self.head = (self.head + 1) % self.k 
            return temp 
            
     def printCQueue(self):
        if(self.head == -1):
            print("No element in the circular queue")

        elif (self.tail >= self.head):
            for i in range(self.head, self.tail + 1):
                print(self.queue[i], end=" ")
            print()
        else:
            for i in range(self.head, self.k):
                print(self.queue[i], end=" ")
            for i in range(0, self.tail + 1):
                print(self.queue[i], end=" ")
            print()

 

3. Priority Queue

A priority queue is a special type of queue in which each element is associated with a proirity value. And, elements are served on the basis of their priority. However, if elements with the same priority occur, they are served according to their order in the queue.

 

Generally, the value of the element itself is considered for assigning the priority. For example, the element with the highest value is considered the highest priority element. However, in other cases, we can assume the element with the lowest value as the highest priority element. We can also set priorities according to our needs.

 

Priority queue can be implemented using an array, a linked list, a heap data structure, or a binary search tree. Basic operations of a priority queue are inserting, removing, and peeking elements.

 

3.1 Inserting an element

Inserting an element into a priority queue (max-heap) is done by the following steps. For Min Heap, the above algorithm is modified so that parentNode is always smaller than newNode.

1. Insert the new element at the end of the tree.
2. Heapify the tree.

If there is no node, 
  create a newNode.
else (a node is already present)
  insert the newNode at the end (last node from left to right.)
  
heapify the array

 

3.2 Deleting an element

Deleting an element from a priority queue (max-heap) is done as follows:

1. Select the element to be deleted.
2. Swap it with the last element.
3. Remove the last element.
4. Heapify the tree.

If nodeToBeDeleted is the leafNode
  remove the node
Else swap nodeToBeDeleted with the lastLeafNode
  remove noteToBeDeleted
   
heapify the array

 

3.3 Peeking from the queue

Peek operation returns the maximum element from Max Heap or minimum element from Min Heap without deleting the node.

 

3.4 Extract - Max/Min from the queue

Extract-Max returns the node with maximum value after removing it from a Max Heap whereas Extract-Min returns the node with minimum value after removing it from Min Heap.

 

3.5 Priority Queue Implementation

class PriorityQueue: 
    def __init__(self): 
        self.queue = [] 
        
    def _heapify(self, n, i): 
        largest = i
        l = 2 * i + 1
        r = 2 * i + 2 
        
        if l < n and self.queue[i] < self.queue[l]:
            largest = l
        if r < n and self.queue[largest] < self.queue[r]: 
            largest = r 
            
        if largest != i: 
            self.queue[i], self.queue[largest] = self.queue[largest], self.queue[i]
            self._heapify(n, largest)
            
    def insert(self, new):
        size = len(self.queue)
        if size == 0 : 
            self.queue.append(new) 
        else : 
            self.queue.append(new)
            for i in range((size // 2) - 1, -1, -1): 
                self._heapify(size, i) 
                
    def deleteNode(self, num):
        size = len(self.queue)
        i = 0
        for i in range(0, size):
            if num == self.queue[i]:
                break
        self.queue[i], self.queue[size - 1] = self.queue[size - 1], self.queue[i]
        self.queue.remove(size - 1)
        for i in range((len(self.queue) // 2) - 1, -1, -1):
            self._heapify(len(self.queue), i)

 

4. Dequeue

Deque or Double Ended Queue is a type of queue in which insertion and removal of elements can eigher be performed from the front or the rear. Thus, it does not follow FIFO rule. There are two types of Deque below :

1. Input Restricted Deque : input is restricted at a single end but allows deletion at both the ends.
2. Output Restricted Deque : output is restricted at a single end but allows insertion at both the ends.

4.1 Operations on a Deque

Before performing operations, these steps are followed.

• Take an array (deque) of size n.
• Set two pointers at the first position and set first = -1 and rear = 0.

 

1. Insert at the Front
   1. Check the position of front
   2. If front < 1, reinitialize front = n -1 (last index).
   3. Else, decrease front by 1.
   4. Add the new key into array[front].
2. Insert at the Rear
   1. Check if the array is full.
   2. If the deque is full, reinitialize rear = 0.
   3. Else increase rear by 1.
   4. Add the key into array[rear].
3. Delete from the Front
   1. Check if the dequeue is empty
   2. If the deque is empty (front = -1), deletion cannot be performed.
   3. If the deque has only one element, set front = -1 and rear = -1.
   4. Else if front is at the end (front = n - 1), set go to the front front = 0. (front > rear)
   5. Else, front = front + 1
4. Deletion from the Rear
   1. Check if the deque is empty.
   2. If the deque is empty (front = -1), deletion cannot be performed.
   3. If the deque has only one element (front = rear), set front = -1 and rear = -1, else follow the steps below.
   4. If rear is at the front (rear = 0), set got to the front rear = n - 1.
   5. Else, rear = rear - 1.
5. Check Empty : If front = -1, then the deque is empty.
6. Check Full : If front = 0 and rear = n - 1 | front = rear + 1, the deque is full.

4.3 Deque Inplementation

class Deque: 
    def __init__(self): 
        self.deque = [] 
    
    def isEmpty(self): 
        return self.deque == [] 
        
    def addRear(self, item): 
        self.deque.append(item)
    
    def addFront(self, item):
        self.deque.insert(0, item)
        
    def removeFront(self): 
        return self.deque.pop(0)
        
    def removeRear(self):
        return self.deque.pop()

 

5. Source of contents

5.1 Types of Queue

https://www.programiz.com/dsa/types-of-queue

Types of Queues

5.2 Circular Queue

https://www.programiz.com/dsa/circular-queue

Circular Queue Data Structure

5.3 Priority Queue

https://www.programiz.com/dsa/priority-queue

Priority Queue Data Structure

5.4 Dequeue

https://www.programiz.com/dsa/deque

Deque Data Structure