Types of Queues
In order to effectively solve common problems, data structures and algorithms are necessary. Of all the data structures, queues are the most basic and come in a variety of forms tailored to particular applications.
Definitions and Concepts
First-In, First-Out (FIFO) governs linear data structures, thus the first item in a queue is the first withdrawn. Like a service line, front-line clients are served first as newcomers wait behind.
Important tasks related to a queue consist of:
Enqueue: Enqueue is the basic process of adding to a queue. New items are always added to the “back” or “tail” of a queue. The first element added will be eliminated first, following the First-In, First-Out (FIFO) principle. An array enqueue action places elements at a computed accessible index, often utilising modular arithmetic to manage circular queue wrap-around.
Dequeue: The dequeue action is essential to queues, abstract data types (ADTs) that work on a First-In, First-Out (FIFO) basis. This signifies the longest-waiting item is eliminated. In particular, dequeue removes and returns the “front” or “head” of the queue. It resembles stack pop.
First / Peek: Data structures’ “First” and “Peek” methods let users inspect an element without removing it.
Peek or Top is used for stacks. It returns the stack’s top element. For instance, Stack Visualisation has a “Peek button”. Python’s peek() method for Stack classes returns the last member added, self.stack[-1], without removing it.
Is_empty:In many data structures, the is empty() method determines if a container contains any elements. Primary function is to return True if structure is empty, False otherwise. In a Binary Search Tree object, isEmpty() tests if the internal root reference is None, indicating an empty tree. Is empty() is often implemented by returning len(self.data) == 0, using Python built-in len() function to check if the internal list contains any entries. This operation usually takes O(1) time.
Len: Python’s built-in len() method counts items in iterable structures and collections. It works with strings, lists, tuples, sets, dictionaries, queues, priority queues, and maps.
Applications for queues are many and include operating systems for scheduling tasks and the implementation of Breadth-First Search (BFS) algorithms. Enqueue and dequeue are examples of basic queue operations that typically operate at O(1) (constant time) spee
Circular Queue
Often, the “shifty problem” arises when implementing a basic array-based queue. The front index may move away from index 0 if items are dequeued from the front of an array-based queue. Due to the lack of reuse of the initial array space, this can eventually result in a situation where the underlying array grows arbitrarily huge, even if the number of elements is now modest.
It handles this via a circular queue. Since the queue contents might “wrap around” the array end, this method treats the array as a circular buffer. To do this, advancing indices are done using modular arithmetic (%) (for example, (index + 1) % N, where N is the array capacity). This enables the queue to effectively reuse space at the array’s beginning following the dequeuing of elements from the front.
The size of the underlying array, the Q (list), and the head and tail pointers are all preserved in a Python implementation of an array-based circular queue. When head and tail are equal (both at index 1 or 0 initially), the queue is empty. When head and tail are one position apart (modulo size), it is full.
Example:
class CircularQueue:
def __init__(self, size):
self.size = size
self.queue = [None] * size
self.front = self.rear = -1
def enqueue(self, item):
if (self.rear + 1) % self.size == self.front:
print("Queue is full!")
elif self.front == -1:
self.front = self.rear = 0
self.queue[self.rear] = item
print(f"Enqueued: {item}")
else:
self.rear = (self.rear + 1) % self.size
self.queue[self.rear] = item
print(f"Enqueued: {item}")
def dequeue(self):
if self.front == -1:
print("Queue is empty!")
elif self.front == self.rear:
removed_item = self.queue[self.front]
self.front = self.rear = -1
print(f"Dequeued: {removed_item}")
else:
removed_item = self.queue[self.front]
self.front = (self.front + 1) % self.size
print(f"Dequeued: {removed_item}")
def display(self):
if self.front == -1:
print("Queue is empty!")
else:
index = self.front
items = []
while index != self.rear:
items.append(self.queue[index])
index = (index + 1) % self.size
items.append(self.queue[self.rear])
print("Circular Queue:", items)
# Example Usage
cq = CircularQueue(5)
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.dequeue()
cq.enqueue(40)
cq.display()Output:
Enqueued: 10
Enqueued: 20
Enqueued: 30
Dequeued: 10
Enqueued: 40
Circular Queue: [20, 30, 40]The circular queue’s is full and display logic implies a slightly different way to handle head and tail pointers (maybe by utilising a sentinel empty slot or identifying empty/full states by size counter). In the code above, head and tail wrapping at self.size and resetting to 1 are explicitly managed. The provided init, enqueue, dequeue, is empty, and is full are all translated.
Double-Ended Queue (Deque)
Mcore versatile than queues, double-ended queues (deques) allow front-and-back additions and deletions. In order to distinguish it from the dequeue procedure, it is pronounced “deck”. Both queues and normal stacks are less generic than the deque ADT.
The following are typical deque operations:
Add_first(e): The add first(e) procedure adds a new element e to the front of a data structure. Inserting a head element in a singly linked list is simple and efficient. E is stored in a new node. The next reference of this new node points to the list’s head (the first node before the insertion). Finally, the list’s head reference is modified to point to this new node, making it the first element. This new node becomes the tail if the list was empty. This O(1) operation usually expands the list.
Add_last(e):The add last(e) action is a basic way to add a new element e to the “back,” or end, of a sequence or data structure like a deque or linked list. Enqueue(e) adds an element to the tail of a queue. Add last(e) in a singly linked list creates a new node, sets its next reference to None, points the tail node’s next reference to it, and updates the tail reference. In an empty list, the new node becomes both the head and tail.
Delete_first(): The delete first() method in linked list data structures removes the first entry. This operation usually takes O(1) time, thus its performance doesn’t decline as the list size increases. Delete first() bypasses the first node in a singly linked list by making the head point to the next node. If the programming language allows garbage collection, the first node can be regained.
Delete_last(): Depending on the implementation, deleting the last piece from a data structure is difficult. Deleting the last node of a single linked list is inefficient. Maintaining a reference to the tail node does not provide direct access to the node before it. Traversing the list from the head to the second-to-last node takes O(N) time, where N is the number of entries.
First(): The first() method is used in many Python data structures to retrieve the “front” element or position without removing it. First() returns a reference to the first element in a queue or deque without removing it. First() will fail or throw an Empty exception if the queue or deque is empty.
Last(): In many data structures, the last() method is used to acquire information about the element or location at the “back” or “end” of the collection without destroying it. D.last() returns the final element of a Deque. This operation fails if the deque is empty.
Is_empty(): The is empty() method is essential for stacks, queues, deques, binary search trees, positional lists, general trees, and priority queues. Its main role is to determine if a data structure has elements. Conventionally, it returns True if the structure is empty and False otherwise.
len(): Python’s len() method is versatile and used to count things in data structures and sequences. This function is polymorphic, accepting strings, lists, tuples, sets, and dictionaries. Example: len(“hello”) returns 5, len() returns 8.
Deques, like circular queues, can be constructed with a circular array. The front index, for example, may need to be circularly decremented while adding to the front (self.front – 1) % len(self.data)). An array-based deque’s efficiency is amortised O(1) for every operation because of possible resizing.
An alternative method for implementing deques is to use a doubly linked list. The collections in Python.A hybrid method utilising circular arrays arranged into blocks that are connected in a doubly linked list is used by the deque module to implement a deque.
Example:
from collections import deque
class Deque:
def __init__(self):
self.deque = deque()
def add_front(self, item):
self.deque.appendleft(item)
print(f"Added {item} to the front")
def add_rear(self, item):
self.deque.append(item)
print(f"Added {item} to the rear")
def remove_front(self):
if self.is_empty():
print("Deque is empty!")
else:
removed_item = self.deque.popleft()
print(f"Removed {removed_item} from the front")
def remove_rear(self):
if self.is_empty():
print("Deque is empty!")
else:
removed_item = self.deque.pop()
print(f"Removed {removed_item} from the rear")
def is_empty(self):
return len(self.deque) == 0
def display(self):
print("Deque:", list(self.deque))
# Example Usage
dq = Deque()
dq.add_rear(10)
dq.add_rear(20)
dq.add_front(5)
dq.remove_front()
dq.display()Output:
Added 10 to the rear
Added 20 to the rear
Added 5 to the front
Removed 5 from the front
Deque: [10, 20]The base Doubly Linked Base class that controls the node structure is usually the ancestor of a Linked Deque class. Along with utility methods like insert between and delete node, this base class would manage the Node definition (using element, prev, and next). The deque would simplify edge cases for insertions and deletions by maintaining header and trailer sentinel nodes and guaranteeing that genuine elements are always between them.
Priority Queues
Standard queues follow the FIFO principle, however a priority queue is a unique kind of queue that does not. An assigned “priority” or “key” is used to order and access the entries in a priority queue instead. It is common practice to remove the element with the least key (in a “min-priority queue”) or maximum key (in a “max-priority queue”). Heaps are the most often utilised data structure for effectively implementing priority queues.