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 |
|---|---|---|
| Add Front | O(1)* | O(1) |
| Add Rear | O(1)* | O(1) |
| Remove Front | O(1) | O(1) |
| Remove Rear | O(1) | O(1) |
| Get Front | O(1) | O(1) |
| Get Rear | O(1) | O(1) |
| Is Empty | O(1) | O(1) |
| Size | O(1) | O(1) |
| Clear | O(1) | O(1) |
Dynamic queues are flexible data structures that can grow or shrink as needed. By implementing our queue with a linked list, we create a queue that stores elements noncontiguously in memory. Dynamic queues are efficient because they only use memory for existing elements. This makes them great for handling varying amounts of data without wasting space. Plus, they don't need to constantly move data around in memory as the queue grows or shrinks, which saves time.
Fixed queues are different from dynamic queues because they have a set size that doesn't change. Think of them like a bus with a fixed number of seats - they can only hold a certain amount of data at a time. These queues are useful when we know exactly how much data we need to handle. Their main advantage is simplicity - since their size doesn't change, they're often easier to manage and can be more efficient in certain situations. However, they're not as flexible as dynamic queues when it comes to handling varying amounts of data.
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 node
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 valA deque (double-ended queue) is a flexible data structure that allows insertion and removal of elements from both the front and the rear. Think of it like a chain where you can add or remove links from either end. In a deque, we have four main operations:
appendleft(): Adds an element to the left (front) of the dequeappend(): Adds an element to the right (rear) of the dequepopleft(): Removes and returns the element from the left (front) of the dequepop(): Removes and returns the element from the right (rear) of the deque
While deques can be implemented using various data structures, an efficient method is using a doubly linked list. This approach allows for instant operations at both ends. Using doubly linked lists, we maintain two pointers:
front: Points to the first element of the dequerear: Points to the last element of the deque
This structure allows us to efficiently add and remove elements from both ends. All these operations take constant time, making the deque a versatile and efficient data structure for scenarios where elements need to be processed from both ends:
Deque
# Definition of a doubly linked list node
class ListNode:
def __init__(self, val: int, prev = None, next = None):
self.val = val
self.prev = prev
self.next = next
class Deque:
def __init__(self):
self.front = None # Points to the first element
self.rear = None # Points to the last element
def appendleft(self, val: int) -> None:
# Create a new ListNode using the value
new_node = ListNode(val)
# Add the newly created ListNode to the front of the deque
if self.front is None:
self.front = self.rear = new_node
else:
new_node.next = self.front
self.front.prev = new_node
self.front = new_node
def append(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 deque
if self.rear is None:
self.front = self.rear = new_node
else:
self.rear.next = new_node
new_node.prev = self.rear
self.rear = new_node
def popleft(self) -> Optional[int]:
# Base case: If the deque is empty, return None
if self.front is None:
return None
# Remove the node from the front and return the value
val = self.front.val
self.front = self.front.next
if self.front is None:
self.rear = None # Deque is now empty
else:
self.front.prev = None
return val
def pop(self) -> Optional[int]:
# Base case: If the deque is empty, return None
if self.rear is None:
return None
# Remove the node from the end and return the value
val = self.rear.val
self.rear = self.rear.prev
if self.rear is None:
self.front = None # Deque is now empty
else:
self.rear.next = None
return valCircular queues are a variant of fixed queues. Imagine a queue where the end connects back to the beginning, forming a circle. This design is smart because it makes better use of space. In a standard queue, when you remove items from the front, you leave empty spaces. But in a circular queue, you can wrap around and use those empty spaces again. It's like the snake game that reappears on the opposite side of the screen when it reaches an edge.
A circular queue typically has a fixed maximum size and uses two pointers: front for the first item and rear for the last item. When you enqueue (add) an item, it goes to the rear. When you dequeue (remove) an item, it comes from the front. If the rear reaches the end of the allocated space, it wraps around to the beginning if there's room. This circular design is especially useful when you're working with a fixed amount of memory and need to use it efficiently.
Queues are the best data structure for managing data in a 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.