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
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
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
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 += 1Regular 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.nextCircular 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
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)
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.
Check whether queue is Empty means check (front==-1),
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
Last updated
Was this helpful?