[DS1] Queue

1. What is Queue

A queue is a useful data structure in programming. Queue follows the First in First Out(FIFO) rule - the item that goes in first is the item that comes out first.

In programming terms, putting items in the queue is called enqueue, and removing items from the queue is called dequeue.

 

2. Basic Operations of Queue

• Enqueue : Add an element to the end of queue
• Dequeue : Remove an element form the front of the queue.
• IsEmpty : Check if the queue is empty
• IsFull : Check if the queue is full
• Peek : Get the value of the front of the queue without removing it

 

3. Working of Queue

3.1 Class Workflow

• Two pointers FRONT and REAR
• FRONT track the first element of the queue
• REAR track the last element of the queue
• initially, set value of FRONT and REAR to -1

3.2 Enqueue Operation

• check if the queue is full
• for the first element, set the value of FRONT to 0
• increase the REAR index by 1
• add the new element in the position pointed to by REAR

3.3 Dequeue Operation

• check if the queue is empty
• return the value pointed by FRONT
• increase the FRONT index by 1
• for the last element, reset the values of FRONT and REAR to -1

 

4. Queue Implementation

class Queue: 
    def __init__(self): 
        self.queue = []
        
    def enqueue(self, item): 
        self.queue.append(item) 
        
    def dequeue(self): 
        if len(self.queue) < 1 : 
            return None 
        return self.queue.pop(0) 
        
    def display(self):
        print(self.queue)
    
    def size(self):
        return len(self.queue)

 

5. Limitation of Queue

After a bit of enqueuing and dequeuing, the size of the queue has been reduced. And we can only add indexes 0 and 1 only when the queue is reset (when all the elements have been dequeued).

 

After REAR reaches the last index, if we can store extra elements in the empty spaces (0 and 1), we can make use of the empty spaces. This is implemented by a modified queue called the circular queue.