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 useful for processing things in order, handling data streams, and powering graph algorithms like Breadth-First Search (BFS).
Queues have a small set of operations. The main ones are enqueue (add an element to the back), dequeue (remove the front element), and peek(look at the front without removing it). Here's the full list with 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 can grow or shrink as needed. By backing the queue with a linked list, we get a queue whose elements live noncontiguously in memory. Dynamic queues only use memory for the elements they currently hold, which makes them great when the size keeps changing. They also don't need to shuffle data around in memory as the queue grows or shrinks, which saves time.
Fixed queues are the opposite: they have a set size that doesn't change. Think of a bus with a fixed number of seats. They're useful when you know exactly how much data you need to handle. The upside is simplicity. A constant size is easier to manage and can be more efficient in some cases. The downside is they can't adapt when the size of your data varies.
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. There are two main operations:
enqueue(): Add an element to the back of the queue.dequeue(): Remove and return the element at the front of the queue.Queues can be backed by different data structures, but a singly linked list is one of the cleanest options. It lets enqueue and dequeue run in constant time. With a linked list, we keep two pointers:
front: Points to the first element of the queue (for dequeue operations).rear: Points to the last element of the queue (for enqueue operations).This structure lets us efficiently add elements to the rear and remove them from the front, just like FIFO requires. Both operations run in constant time:
# 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 (short for double-ended queue) is a flexible data structure that lets you insert and remove elements from both the front and the rear. Think of a chain where you can add or remove links from either end. A deque has four main operations:
appendleft(): Add an element to the left (front) of the deque.append(): Add an element to the right (rear) of the deque.popleft(): Remove and return the element from the left (front).pop(): Remove and return the element from the right (rear).Deques can be backed by different data structures, but a doubly linked list is one of the cleanest options. It lets every operation run in constant time. With a doubly linked list, we keep two pointers:
front: Points to the first element of the deque.rear: Points to the last element of the deque.This structure lets us add and remove elements from both ends in constant time. That makes deques great whenever you need to work with both ends of a sequence:
# 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. The trick is space reuse. In a standard queue, removing items from the front leaves empty spots behind. In a circular queue, you can wrap around and reuse those spots. It's like the snake game that reappears on the opposite side of the screen when it reaches an edge.
A circular queue has a fixed maximum size and uses two pointers: front for the first item and rear for the last item. enqueue adds an item to the rear, and dequeue removes it from the front. When the rear reaches the end of the allocated space, it wraps around to the beginning if there's room. This makes circular queues a good fit when you're working with a fixed amount of memory and want to use every slot.
Queues are the go-to whenever you need to process data in FIFO order, and they show up underneath a lot of more complex algorithms. Here are a few tips for working with them well:
collections.deque, Java's ArrayDeque, etc.), and know the core operations: enqueue (add), dequeue (remove), peek (look at the front without removing), and isEmpty.A technique using two pointers to traverse data structures efficiently.
A technique for processing contiguous subarrays or substrings efficiently.
A method where a function calls itself to solve smaller instances of the same problem.
An algorithmic technique for solving problems by exploring all possibilities.
An algorithm for traversing graphs by exploring as far as possible along each branch.
An algorithm for traversing graphs level by level.
Dynamic programming applied to two-dimensional problems.
A pattern using two heaps to efficiently track medians or extremes.
Queues feel simple until you discover the monotonic deque — then a whole class of sliding-window problems collapses to O(n). Work through these to internalize FIFO simulations, circular buffers, and the deque tricks that make hard window problems tractable:
Completed | Title | Status | Notes | Solution | |
|---|---|---|---|---|---|
Easy | |||||
Easy | |||||
Easy | |||||
Easy | |||||
Easy | |||||
Medium | |||||
Medium | |||||
Medium | |||||
Medium | |||||
Hard | |||||
Hard | |||||
Hard |