DevPath
Tracks

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
0
top
push A. The stack holds one item.
step 1 / 6

A stack (LIFO): all the action happens at the top.

A
0
front, back
enqueue A. It is both the front and the back.
step 1 / 6

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.

g()top: running now, pops first
f()waiting for g to return
main()bottom: waiting for f to return

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 head index and a size. The next free slot is (head + size) % capacity. Dequeue moves head forward 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.

0
head
1
2
Empty buffer. head is 0 and the next free slot is also 0.
step 1 / 9

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.

OperationTimeNotes
Stack push / pop / peekO(1)Array end; amortized for push
Queue enqueue / dequeueO(1)Linked list or ring buffer
Deque push / pop at both endsO(1)collections.deque
Dequeue using array.pop(0) or shiftO(n)Shifts remaining items
Search for an arbitrary itemO(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())

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) and array.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 size counter (as above) or sacrifice one slot.
  • Modulo of negative numbers: moving backwards with (i - 1) % n is negative in JavaScript when i is 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

  1. 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.
  2. 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.
  3. 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.
  4. 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

Related lessons