Stacks and Queues
LIFO and FIFO containers, the call stack, monotonic stacks, deques and circular buffers, with implementations and their costs.
beginner40 min#stack#queue#deque#circular-buffer#monotonic-stack
Prerequisites: Arrays and Dynamic Arrays, Linked Lists
Why it matters
Stacks and queues are not about storage; they are about order of removal. A stack gives you the most recent thing first (undo history, function calls, matching brackets, depth-first search). A queue gives you the oldest thing first (task schedulers, print jobs, breadth-first search, message buffers). Restricting yourself to two operations makes algorithms easier to reason about, and the restriction is what lets implementations be O(1).
Intuition
A stack is a pile of plates. You add to the top and take from the top, so the last plate in is the first out (LIFO). A queue is a line at a shop. People join at the back and are served from the front, so first in is first out (FIFO).
Stack (top on the right) Queue (front on the left)
push 1, push 2, push 3 enqueue 1, 2, 3
[1][2][3] <- pop gives 3 [1][2][3] <- dequeue gives 1
Step through each one. Notice that only one end ever changes for the stack, while the queue uses both ends.
A stack (LIFO): all the action happens at the top.
A queue (FIFO): add at the back, remove from the front. (Here the list is redrawn after each removal to show order; a real queue avoids shifting, as the ring buffer below shows.)
A deque (double-ended queue, pronounced "deck") allows adds and removes at both ends, so it can act as either one.
How it works
Stack. Use a dynamic array and treat the end as the top. push is append and pop removes the last item, both O(1) amortized. The language's call stack is the same idea: each function call pushes a frame holding its local variables and return address, and returning pops it. That is why very deep recursion causes a stack overflow.
Here is what the call stack looks like when main calls f, and f calls g.
Queue. An array is a poor fit if you remove from the front, because every remaining item must shift (O(n)). Two good options exist:
- Linked list with head and tail pointers: enqueue at the tail and dequeue at the head, both O(1).
- Circular buffer (ring buffer): a fixed array plus a
headindex and asize. The next free slot is(head + size) % capacity. Dequeue movesheadforward by one, wrapping around with the modulo. No shifting ever happens, and memory is reused.
capacity 5, head = 3, size = 3 items sit in slots 3, 4, 0
index: 0 1 2 3 4
[ c ][ ][ ][ a ][ b ] next free slot = (3 + 3) % 5 = 1
Step through the RingQueue from the code below, with capacity 3. The next free pointer is (head + size) % capacity; when the buffer is full it equals head, so only one arrow is drawn.
The ring buffer reuses freed slots by wrapping with modulo; nothing is ever shifted.
Ring buffers are everywhere: network packet buffers, audio streams, and bounded logs. Their weakness is the fixed capacity; you either reject new items, overwrite the oldest, or grow and re-copy.
Standard library tools. Use collections.deque in Python (O(1) at both ends). In JavaScript an array's push and pop are fast, but shift can be O(n) on large arrays in the worst case, so for heavy queue use keep a moving head index or write a small ring buffer.
Monotonic stack. A stack whose values are kept in sorted order by popping items that break the order. It solves "next greater element", "daily temperatures" and "largest rectangle in a histogram" in O(n), because each index is pushed once and popped at most once.
| Operation | Time | Notes |
|---|---|---|
| Stack push / pop / peek | O(1) | Array end; amortized for push |
| Queue enqueue / dequeue | O(1) | Linked list or ring buffer |
| Deque push / pop at both ends | O(1) | collections.deque |
| Dequeue using array.pop(0) or shift | O(n) | Shifts remaining items |
| Search for an arbitrary item | O(n) | Not what these are for |
Code: brackets, next greater element and a ring queue
class RingQueue:
"""Fixed-capacity FIFO queue on a circular buffer."""
def __init__(self, capacity):
self._buf = [None] * capacity
self._head = 0 # index of the oldest item
self._size = 0
def __len__(self):
return self._size
def enqueue(self, x):
if self._size == len(self._buf):
raise OverflowError("queue is full")
tail = (self._head + self._size) % len(self._buf)
self._buf[tail] = x
self._size += 1
def dequeue(self):
if self._size == 0:
raise IndexError("queue is empty")
x = self._buf[self._head]
self._buf[self._head] = None
self._head = (self._head + 1) % len(self._buf)
self._size -= 1
return x
def balanced(text):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in text:
if ch in "([{":
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
def next_greater(nums):
"""For each item, the next larger value to its right (or -1)."""
result = [-1] * len(nums)
stack = [] # indexes whose answer is still unknown, values decreasing
for i, x in enumerate(nums):
while stack and nums[stack[-1]] < x:
result[stack.pop()] = x
stack.append(i)
return result
print(balanced("{[()]}"), balanced("(]"), balanced("(("))
print(next_greater([2, 1, 5, 3, 4]))
q = RingQueue(3)
q.enqueue("a"); q.enqueue("b"); q.enqueue("c")
print(q.dequeue(), q.dequeue())
q.enqueue("d"); q.enqueue("e") # tail wraps around to the front of the buffer
print(len(q), q.dequeue(), q.dequeue(), q.dequeue())class RingQueue {
// Fixed-capacity FIFO queue on a circular buffer.
constructor(capacity) {
this.buf = new Array(capacity).fill(null);
this.head = 0; // index of the oldest item
this.size = 0;
}
enqueue(x) {
if (this.size === this.buf.length) throw new RangeError("queue is full");
const tail = (this.head + this.size) % this.buf.length;
this.buf[tail] = x;
this.size++;
}
dequeue() {
if (this.size === 0) throw new RangeError("queue is empty");
const x = this.buf[this.head];
this.buf[this.head] = null;
this.head = (this.head + 1) % this.buf.length;
this.size--;
return x;
}
}
function balanced(text) {
const pairs = { ")": "(", "]": "[", "}": "{" };
const stack = [];
for (const ch of text) {
if ("([{".includes(ch)) {
stack.push(ch);
} else if (ch in pairs) {
if (stack.length === 0 || stack.pop() !== pairs[ch]) return false;
}
}
return stack.length === 0;
}
// For each item, the next larger value to its right (or -1).
function nextGreater(nums) {
const result = new Array(nums.length).fill(-1);
const stack = []; // indexes whose answer is still unknown, values decreasing
nums.forEach((x, i) => {
while (stack.length && nums[stack[stack.length - 1]] < x) {
result[stack.pop()] = x;
}
stack.push(i);
});
return result;
}
const py = (b) => (b ? "True" : "False");
console.log(py(balanced("{[()]}")), py(balanced("(]")), py(balanced("((")));
console.log("[" + nextGreater([2, 1, 5, 3, 4]).join(", ") + "]");
const q = new RingQueue(3);
q.enqueue("a"); q.enqueue("b"); q.enqueue("c");
console.log(q.dequeue(), q.dequeue());
q.enqueue("d"); q.enqueue("e"); // tail wraps around to the front of the buffer
console.log(q.size, q.dequeue(), q.dequeue(), q.dequeue());Both versions print:
True False False
[5, 5, -1, 4, -1]
a b
3 c d e
The last two lines show the wrap-around: after two dequeues, d and e are written into slots 0 and 1, yet items still come out in order c, d, e.
Common pitfalls
- Popping from an empty stack or queue: decide on the behavior (raise, return null) and check emptiness first. In bracket matching, a closing bracket with an empty stack means the input is unbalanced.
- Forgetting leftovers:
"(("never pops anything wrong, but it is still unbalanced. Check that the stack is empty at the end. - Using a list as a queue:
list.pop(0)andarray.shift()look innocent but can turn a linear algorithm into a quadratic one. - Ring buffer full vs empty: if you only track head and tail indexes, both states look the same. Track a
sizecounter (as above) or sacrifice one slot. - Modulo of negative numbers: moving backwards with
(i - 1) % nis negative in JavaScript wheniis 0. Use(i - 1 + n) % n.
Practice
Valid parentheses easy
Hint
Which opener must be closed first? That is the most recently opened one.
Show solution
Push each opener. For each closer, the stack must be non-empty and its top must be the matching opener, otherwise return false. After scanning, the stack must be empty. O(n) time, O(n) space.
Queue using two stacks medium
Hint
Reversing a stack twice restores the original order.
Show solution
Keep an inbox and an outbox stack. Enqueue pushes onto inbox. To dequeue, if outbox is empty, pop everything from inbox into outbox (which reverses the order), then pop from outbox. Each item moves at most once, so dequeue is amortized O(1).
Daily temperatures medium
Hint
For each day you want the distance to the next warmer day. A monotonic stack of indexes helps.
Show solution
Keep a stack of indexes with decreasing temperatures. For day i, while the top day is colder than today, pop it and set its answer to i - top. Then push i. Days left on the stack get 0. O(n) because each index is pushed and popped once.
Sliding window maximum hard
Hint
Keep a deque of indexes whose values decrease from front to back. What should happen at each end?
Show solution
For each index i, pop from the back while the back value is not larger than a[i], then push i. If the front index is outside the window (front <= i - k), pop it from the front. Once i >= k - 1, the front holds the window's maximum. Each index enters and leaves once, so the whole thing is O(n).
Interview questions
- Where does the call stack show up in real programs? Every function call pushes a frame; deep or infinite recursion exhausts the stack. Any recursive algorithm can be rewritten with an explicit stack.
- Why is a circular buffer better than shifting an array? Dequeue only moves an index, so it is O(1) and memory is reused without copying.
- How do you implement a stack that returns its minimum in O(1)? Store each pushed value together with the minimum so far, or keep a second stack of minimums.
- When would you choose a queue over a stack for search? When you need the shortest path by number of edges (BFS) or fair first-come-first-served processing.
Interviewers look for: choosing the right structure from the order requirement, handling empty cases, and knowing why pop(0) or shift is a trap.
Quick check
You push 1, 2, 3 onto a stack, pop once, push 4, then pop twice. What was popped, in order?
Finished this lesson?
Further resources
- Stack (abstract data type) (Wikipedia) (article)
- Queue (abstract data type) (Wikipedia) (article)
- Circular buffer (Wikipedia) (article)
- Python docs: collections.deque (docs)