Data Structures Queues
Queues
FIFO data structure for ordered processing.
A queue is a linear data structure that follows the FIFO principle. It's like a line at a store: the first person to arrive is the first to be served. Queues are commonly used for managing tasks in chronological order, handling data streams, and implementing graph algorithms such as Breadth-First Search (BFS).
Queues offer several operations that make them an efficient. The main operations include enqueue (adding an element), dequeue (removing the front element), and peek (viewing the front element). Here is a comprehensive list of queue operations and their time complexities:
| Operations | Time | Space |
|---|---|---|
| Enqueue Front | O(1) | O(1) |
| Enqueue Rear | O(1) | O(1) |
| Dequeue Front | O(1) | O(1) |
| Dequeue Rear | O(1) | O(1) |
| Peek Front | O(1) | O(1) |
| Peek Rear | O(1) | O(1) |
| IsEmpty | O(1) | O(1) |
| Size | O(1) | O(1) |
Queues can be implemented using other data structures, but one efficient method is using a singly linked list. This approach allows for instant enqueue and dequeue operations. Using linked lists, we maintain two pointers:
front: Points to the first element of the queue (fordequeueoperations)rear: Points to the last element of the queue (forenqueueoperations)
This structure allows us to efficiently add elements to the rear and remove them from the front, adhering to the FIFO principle of queues.
A standard queue is a FIFO data structure. It works like a line at a store: the first person to join the line is the first to be served. In a standard queue, we have two main operations:
enqueue: Adds an element to the back of the queuedequeue: Removes and returns the element at the front of the queue
While queues can be implemented using various data structures, an efficient method is using a singly linked list. This approach allows for instant enqueue and dequeue operations. Using linked lists, we maintain two pointers:
front: Points to the first element of the queue (fordequeueoperations)rear: Points to the last element of the queue (forenqueueoperations)
This structure allows us to efficiently add elements to the rear and remove them from the front, following the FIFO principle. Both these operations take constant time making the queue efficient for managing data:
Standard Queue
# Definition of a singly linked list
class ListNode:
def __init__(self, val: int, next = None):
self.val = val
self.next = next
class StandardQueue:
def __init__(self):
self.front = None # Points to the first element
self.rear = None # Points to the last element
def enqueue(self, val: int) -> None:
# Create a new ListNode using the value
new_node = ListNode(val)
# Add the newly created ListNode to the end of the queue
if self.rear is None:
self.front = self.rear = new_node
else:
self.rear.next = new_node
self.rear = new_node
def dequeue(self) -> Optional[int]:
# Base case: If the queue is empty, return null
if self.front is None:
return None
# Remove the node in the front, and return the value
val = self.front.val
self.front = self.front.next
if self.front is None:
self.rear = None # Queue is now empty
return valDynamic queues are a type of queue that can grow and shrink, such as linked lists or dynamic arrays. Since we are implementing our queue using a linked list, it classifies as a dynamic queue meaning it is not stored contiguously in memory. Dynamic queues provide significant advantages in terms of memory utilization and scalability, since we don't need to frequently reallocate memory.
In contrast, fixed queues have a specified capacity, setting a limit on the number of elements they can hold. Fixed queues are useful in scenarios where the size of the queue is known in advance and remains constant, leading to a straightforward and efficient solution for managing data in a FIFO (First In, First Out) manner.
Circular queues are a variant of fixed queues where the last position is connected back to the first, creating a circular structure. This design is efficient for space utilization, allowing the queue to wrap around and use vacant positions created after dequeue operations:
The implementation above is a circular queue using a linked list structure, where the queue has a fixed maximum capacity. The main components are two pointers (left for the head and right for the tail of the queue) and a size counter to track the number of elements in the queue.
Deques (double-ended queues) allow insertion and removal of elements from both the front and the rear. This flexibility makes deques a versatile data structure for various scenarios where elements need to be processed from both ends.
The flexibility and efficiency of deques for operations at both ends, is powered by an underlying doubly linked list that allows bidirectional traversal and manipulation.
Queues are the best data structure for managing data in a first-in, first-out (FIFO) manner. They are useful for maintaining order and are the foundations for complex algorithms. Here are some essential tips and tricks for mastering queues:
enqueue (add), dequeue (remove), peek (view the front item without removal), and isEmpty.