A line that works both ends at once: new items join the back, the oldest leaves the front, so everything is handled in exactly the order it arrived.
A line that works both ends at once: new items join the back, the oldest leaves the front, so everything is handled in exactly the order it arrived.
Stacks fell out of arrays almost for free, because both of their operations live at the array's cheap end. But plenty of problems demand the opposite discipline. A printer takes jobs in the order they arrived. A web server answers the oldest waiting request first. For those, a structure has to work both ends at once: add at the back, remove from the front.
That structure is a queue: 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. The analogy has one leak: in a real line, people can give up and wander off from the middle. A queue only ever removes from the front. Queues show up anywhere work has to happen in arrival order: print jobs, data streams, and 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). Say three jobs arrived in the order 7, 12, 25. Then enqueue(31) lines 31 up behind 25, and dequeue() hands back 7, the job that has waited longest.
You might think a plain array handles this fine: append for enqueue, remove index 0 for dequeue. The append works. The removal is a trap: pulling out index 0 shifts every remaining element left, the same O(n) cost a front insert paid on the arrays page, except a queue would pay it on every single dequeue. The rest of this page is about the structures that dodge that shift, which is how every row below earns its O(1):
| 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) |
The first way to dodge the front-removal shift is to stop demanding contiguous memory at all. 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.
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 the array underneath never has to resize. The downside is they can't adapt when the size of your data varies.
A standard queue is a FIFO data structure in its plainest form: in at the back, out at the front, nothing else. 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. Recall from the linked lists page that deleting at the head and inserting at the tail both cost O(1) once you track a tail pointer, and those are exactly the two moves a queue needs. 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:
Sometimes a queue's front-only rule is too strict. Sliding window problems, for example, trim from one end while feeding the other. A 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).A deque is where the doubly linked list earns its extra pointer, because prev is exactly what makes removing from the rear cost constant time. We keep the same two pointers:
front: Points to the first element of the deque.rear: Points to the last element of the deque.With both pointers in place, all four operations run in constant time:
Circular queues are a variant of fixed queues, and they solve a puzzle worth pausing on. In an array-backed queue, every dequeue moves the front pointer forward and leaves a dead slot behind it. After enough traffic, the rear pointer hits the last slot while the first few slots sit empty. Is the queue full? It shouldn't be. The fix is to let the end connect back to the beginning, forming a circle, so the rear can wrap around and reuse those abandoned 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.
First, two checks from this page: why does dequeue cost O(n) on a plain array but O(1) on a linked list? And what problem does a circular queue's wrap-around solve? If both come back quickly, you're ready. Queues feel simple until you discover the monotonic deque. Once you do, 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 | |
|---|---|---|---|---|---|
standard_queue.py
# 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 valdeque.py
# 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 val