Queue

What is Queue Data Structure?

• A Queue is a FIFO (First In First Out) data structure

• The first element that is placed in a queue is the first one out

• Elements can be inserted only from one side of the list called rear, and the elements can be deleted only from the other side called the front

• Think of queues as a queue of people waiting for something. The first person to queue up is the first person served

• The insertion of an element in a queue is called an enqueue operation

• The deletion of an element is called a dequeue operation

• For queues, two pointers are maintained

  • Front pointer: points to the element which was inserted at the first and still present in the list.

  • Rear pointer: points to the element inserted last

• Dequeuing the first element or enqueuing an element takes O(1) time complexity

Limitations of Regular Queue Data Structure

Types of Queues

Normal Queue

Circular Queue

• A circular queue is the extended version of a regular queue where the last element is connected to the first element. Thus forming a circle-like structure. Also called "Ring Buffer"

• It handles the drawback of the regular queue; in the normal queue after a bit of insertion and deletion, there will be non-usable empty space. A circular queue takes care of it

Priority Queue

• A priority queue is a special type of queue in which each element is associated with a priority value

• Elements are served on the basis of their priority. That is, higher priority elements are served first

• If elements with the same priority occur, they are served according to their order in the queue

• Not a FIFO operation, but priority is the basis. In case of equal priority, FIFO is followed

Deque (Double Ended Queue)

• In a double-ended queue, element insertion and removal can be performed either from the front or rear, it does not follow the FIFO (First In First Out) rule

• It is simply like a doubly-linked list, performing both FIFO and FILO

• We will ignore this queue type for now

Basic Operations in Queue

• Enqueue:

  • Enqueue is like pushing or adding an item to the queue

  • Enqueue is done at the rear of the queue

• Dequeue:

  • It is removing an item from the queue

  • Removing or popping is done at the front end of the queue

• Display:

  • Move from front to rear and print all the elements

• Size:

  • Get the number of elements in the queue

Implementation

Normal Queue

1. Two pointers are maintained;

   • 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

2. enqueue(value)

   • 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. dequeue()

   • 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

Regular Queue - Implementation using List

• dequeue(0) and enqueue(0) operations using list will require O(n) time complexity for input of size n

• Hence. it is not used for queue purpose rather collection dequeue is used

class Queue:
    def __init__(self, queue=[]):
        self.queue = queue

    def enqueue(self, item):
        self.queue.insert(0, item)
        return True
    
    def is_empty(self) -> bool:
        return not bool(self.queue)

    def dequeue(self) -> bool:
        if not self.is_empty():
            x = self.queue.pop(0)
            return x
        return '-infi'
    
    def size(self) -> int:
        return len(self.queue)
    
    def display(self) -> list:
        print(self.queue)

Regular Queue - Implementation using collections.deque

dequeue is based on doubly linkedlist, which makes the time complexity of O(1) for below operations

Regular Queue - Implementation using List using two pointers

class Queue:
    def __init__(self, queue=[], max_size=10):
        self.queue = queue
        self.max_size = max_size
        self.front = -1
        self.rear = -1
        
    def enqueue(self, data):
        if self.is_empty():
            self.queue.append(data)
            self.rear = 0
            self.front = 0
        elif self.rear == self.max_size-1:
            print('list is full, waiting for reset, it is done when all the elements are dequeued')
        else:
            self.rear += 1
            self.queue.append(data)
        
    def dequeue(self):
        if self.front == self.max_size - 1:
            self.front = -1
            self.end = -1
        elif self.front == -1:
            print('empty!!!')
        else:
            self.front += 1
        
    def is_empty(self):
        return (self.front == -1 and self.rear == -1)
        
    def size(self):
        if self.is_empty():
            return 0
        else:
            return self.rear - self.front + 1
        
    def display(self):
        point = self.front
        if not self.is_empty():
            while point <= self.rear:
                print(self.queue[point], end=' ')
                point += 1

Regular Queue - Implementation using doubly LinkedList

• This implementation should be done after going through LinkedList
• For queue, element should be added to end node pointer and removed from start node pointer

• For stack, element should be removed from front node and removed from front node

• hence stack can be implemented using single pointer

class QueueNode:
    def __init__(self, data, prev_node= None, next_node= None):
        self.data = data
        self.prev = prev_node
        self.next = next_node
        
class Queue:
    def __init__(self, start=None, end=None):
        self.start = start
        self.end = end
        
    def enqueue(self, data):
        new_node = QueueNode(data)
        new_node.prev = self.end
        
        if self.end == None:
            self.start = new_node
            self.end = new_node
        else:
            self.end.next = new_node
            self.end = self.end.next
        
    def dequeue(self):
        if not self.is_empty():
            if self.start == self.end:
                self.start = None
                self.end = None

            else:
                self.start = self.start.next
                self.start.prev = None
            
            return True
        return False
    
    def size(self):
        this_node = self.start
        if self.is_empty():
            return 0
        elif self.start == self.end:
            return 1
        else:
            count = 1
            while this_node.next:
                count+=1
                this_node = this_node.next
            return count
            
    def is_empty(self):
        return not bool(self.start and self.end)
        
    def display(self):
        this_node = self.start
        while this_node:
            print(this_node.data, end=' ')
            this_node = this_node.next

Circular Queue

• We have front and rear items marked in the queue and their values are market as -1 initially

• The Tail and Head can point to the same location - this means the Queue is empty

• enQueue(value) This function is used to insert an element into the circular queue, done at the rear

  1. Check whether queue is Full – Check ((rear == SIZE-1 && front == 0) || (rear == front-1))

     Meaning: if (rear is at the end and front at start) or (rear is just one behind to the front)

  2. If queue is not full then, check if (rear == SIZE – 1 && front != 0) if it is true then set rear=0 and insert element.

     Meaning: When queue is not full insert at the rear end and increase the rear count. If rear is at the end then next rear position will at the start of the queue

• deQueue() This function is used to delete an element from the circular queue. In a circular queue, the element is always deleted from front position.

  1. Check whether queue is Empty means check (front==-1),

  2. If not empty then, check if (front==rear). if it is true then set front=rear= -1 else check if (front==size-1), if it is true then set front=0 and return the element.

Circular Queue: Implementation using List (Two pointers)

class CircularQueue:
    def __init__(self, max_size=10):
        self.queue = [None]*max_size
        self.max_size = max_size
        self.front = -1
        self.rear = -1
        
    def enqueue(self, data):
        if (self.rear + 1) % self.max_size == self.front:
                print('queue is full!!!')
                
        elif self.is_empty():
            self.rear = 0
            self.front = 0
            self.queue[(self.rear % self.max_size)] = data
        
        else:
            self.rear = (self.rear + 1) % self.max_size
            self.queue[(self.rear % self.max_size)] = data
            

    def dequeue(self):
        if self.is_empty():
            print("Nothing in here in the queue!!")
        else:
            if self.front + 1 == self.rear:
                self.rear, self.front = -1, -1
                self.queue.pop()
            else:
                self.front = (self.front + 1) % self.max_size
                
    def is_empty(self):
        return (self.front == -1 and self.rear == -1)
        
        
    def display(self):
        if(self.front == -1):
            print("No element in the circular queue")

        elif (self.rear >= self.front):
            for i in range(self.front, self.rear + 1):
                print(self.queue[i], end=" ")
            print()
        else:
            for i in range(self.front, self.max_size):
                print(self.queue[i], end=" ")
            for i in range(0, self.rear + 1):
                print(self.queue[i], end=" ")
            print()
            
    def size(self):
        if self.rear >= self.front:
            print(self.rear - self.front + 1)
        else:
            print(self.rear + self.max_size - self.front + 1)

Priority Queue

• Can be implemented using:

  • an array

  • a linked list

  • a heap data structure

  • a binary search tree

• Heap data structure provides an efficient implementation of priority queues

• Follow Heap data structure first for priority queue implementation. Link to be updated....

Where to Use Queue Data Structure

• API response: For asynchronous jobs in the microservice architecture, when an application receives multiple requests (which is beyond the server capacity), then requests are queued and generally served based on a first come first serve basis (FIFO)

• Cache Management: Rotation of cache data in RAM memory is important to keep the data of the latest users in the cache. Out of many algorithms for cache expiration, one of the most important is based on first in first out basis. Easy to implement using circular queue

• Call Center phone systems use Queues to hold people calling them in order.

• In Trees and Graph Data Structure -

  • Stacks and Queues are commonly used when implementing Breadth-First-Search (BFS) or Depth-First-Search (DFS) for trees and graphs

  • Queues are commonly used for BFS

  • Stacks are commonly used for DFS

• Celery Task Processing:

  • Implemented using a combination of the normal queue and priority queue

  • If each task is associated with a priority, then served according to its priority.

  • If elements with the same priority occur, they are served according to their order in the queue.

Reference For Further Reading

Queue Data Structure and Implementation in Java, Python and C/C++

Excellent Resource, Must Read!!

Circular Queue: An implementation tutorial | Python CentralPython Central

Circular Queue Implementation