DSA: Queues
Learn queue implementations, variants like deque and priority queue, and classic queue-based algorithms.
Queue ADT
A queue is a First-In First-Out (FIFO) data structure. Elements are added at the rear (enqueue) and removed from the front (dequeue). Think of it as a line at a counter.
Core Queue Operations
All standard queue operations run in O(1) on both array and linked-list implementations.
- enqueue(x): add element x at the rear
- dequeue(): remove and return the front element
- front() / peek(): read the front element without removing it
- isEmpty(): returns true if the queue holds no elements
| Operation | Circular Array | Linked List |
|---|---|---|
| enqueue | O(1) | O(1) |
| dequeue | O(1) | O(1) |
| front | O(1) | O(1) |
| isEmpty | O(1) | O(1) |
| Memory | Fixed capacity, cache-friendly | Dynamic, extra pointer per node |
Array-Based Queue (Circular Queue)
A simple array queue wastes space as the front pointer advances and leaves empty slots at the beginning. A circular queue fixes this by wrapping both front and rear using modulo arithmetic.
Circular Queue
Use (index + 1) % capacity to wrap rear and front around the array, reusing freed front slots.
- rear = (rear + 1) % capacity before each enqueue
- front = (front + 1) % capacity after each dequeue
- Full condition: (rear + 1) % capacity == front
- Empty condition: front == -1
Circular Queue Using Array
C++Modulo wrapping reuses the slot freed by dequeue so the array never runs out of space prematurely.
Linked List-Based Queue
A linked-list queue maintains a head pointer for the front and a tail pointer for the rear. Both enqueue and dequeue are O(1) with no capacity limit.
Linked List Queue
head is the front (dequeue side); tail is the rear (enqueue side). Both operations touch only one pointer.
- enqueue: create a new node, tail->next = new node, move tail forward
- dequeue: save head->data, move head to head->next, delete old head
- No overflow, grows dynamically with heap allocation
- Extra memory per node compared to the circular array version
Linked List Queue
C++tail pointer makes enqueue O(1). head pointer makes dequeue O(1). Both are maintained after every operation.
Double-Ended Queue (Deque)
A deque allows insertion and deletion at both the front and the rear. It generalizes both a stack and a queue and is the building block for the sliding window maximum algorithm.
Deque Operations
All four operations run in O(1). std::deque in C++ provides this out of the box.
- push_front / push_back: insert at front or rear
- pop_front / pop_back: remove from front or rear
- front() / back(): peek at either end
- Used to implement both stacks (push/pop back) and queues (push back, pop front)
std::deque Basics
C++push_front and pop_front operate on the left end; push_back and pop_back operate on the right end.
Queue Using Two Stacks
Two stacks can simulate a queue. The inbox stack receives new elements; the outbox stack serves dequeue requests. When outbox is empty, the entire inbox is transferred to it, reversing the order to achieve FIFO.
Two-Stack Queue
Amortized O(1) dequeue: each element moves from inbox to outbox exactly once over its lifetime.
- enqueue: always push to inbox stack, O(1)
- dequeue: if outbox is empty, move all of inbox into outbox (reverses order), then pop outbox
- Lazy transfer means most dequeues are just a pop from outbox, O(1) amortized
- Worst case for a single dequeue is O(n), but amortized across n operations it is O(1)
Queue from Two Stacks
C++Inbox collects new elements. Outbox serves them in FIFO order. Transfer happens only when outbox runs dry.
Stack Using Two Queues
Two queues can simulate a stack. On each push, enqueue the new element into the empty queue, then move all elements from the other queue into it so the new element ends up at the front.
Two-Queue Stack
Keep one active queue where the front is always the stack top. Push is O(n); pop is O(1).
- push(x): enqueue x into the empty queue, then drain the active queue into it, swap roles
- pop(): dequeue from the active queue, O(1)
- After every push, the newest element is at the front of the active queue
- Trade-off: O(n) push cost for O(1) pop, opposite of the two-stack queue
Stack from Two Queues
C++After each push the new element is rotated to the front of q1, making it accessible as the stack top.
First Non-Repeating Character in a Stream
As characters arrive one by one, report the first character in the stream that has not repeated yet. A queue maintains the order of arrival; a frequency array tracks counts.
Stream + Queue Pattern
The queue holds candidates in arrival order. Stale candidates (those that became duplicates) are removed from the front before each report.
- Increment freq[c] for each arriving character
- If freq[c] == 1, enqueue c (first occurrence)
- Before reporting, pop the front while freq[front] > 1 (these became duplicates)
- The new front is the first non-repeating character, or report -1 if the queue empties
First Non-Repeating Character per Step
C++Queue maintains arrival order. Stale fronts are lazily removed when their frequency exceeds 1.
Sliding Window Maximum
Find the maximum element in every window of size k as it slides across the array. A monotonic decreasing deque of indices solves this in O(n) instead of O(n×k).
Monotonic Deque for Window Max
The deque front always holds the index of the current window maximum. Smaller candidates are pruned from the back because they can never be the maximum while a larger element is still in the window.
- Remove indices from the front when they fall outside the window (index <= i - k)
- Remove indices from the back while arr[back] <= arr[i], they are dominated
- Push current index i to the back
- After the first full window (i >= k-1), deque front is the window maximum index
Sliding Window Maximum (k=3)
C++Each element enters and leaves the deque once, giving O(n) total time across all windows.
Circular Tour Problem
Given petrol pumps arranged in a circle, each providing some petrol and requiring some to reach the next pump, find the starting pump from which a truck can complete the full circle.
Greedy Start-Point Strategy
If the running fuel balance ever drops below zero, the current start and every pump between the start and the current position are invalid. The next pump must be the new candidate start.
- Track running balance: balance += petrol[i] - cost[i]
- If balance drops below 0, reset balance to 0 and set start = i + 1
- Also track total surplus. If total >= 0, a solution exists.
- Time: O(n), Space: O(1). Only one pass needed.
Circular Tour (Petrol Pump)
C++When balance drops below zero, every pump from the old start to i is invalid. The reset to i+1 is the key insight.
Level Order Traversal (BFS)
Level order traversal visits all nodes of a binary tree level by level, left to right. A queue processes each node and enqueues its children so they are visited in the correct order.
BFS with a Queue
Enqueue the root. Then repeatedly dequeue a node, process it, and enqueue its left and right children.
- Enqueue the root to start
- While the queue is not empty: dequeue a node, print it, enqueue left child then right child
- To separate levels: track the queue size at the start of each level iteration
- Time: O(n), Space: O(w) where w is the maximum width of the tree
Level Order Traversal (BFS)
C++Snapshotting queue size at the start of each iteration cleanly separates one level from the next.
Knowledge Check
1. Which principle does a queue follow?
2. Why is a circular queue preferred over a simple array queue?
3. In a queue implemented with two stacks, which operation is costly?
4. A deque (double-ended queue) supports:
5. The sliding window maximum problem is solved in O(n) using:
6. Level-order traversal of a binary tree uses which data structure?
7. In the circular tour (petrol pump) problem, the greedy insight is:
8. What is the time complexity of enqueue and dequeue on a linked-list queue?