Stacks and
Queues

Abstract Data Type (ADT)

A mathematical model that defines a data type purely by its behaviour — the operations it supports and their semantics — without specifying how those operations are implemented.

• Specifies what operations exist and what they return
• Says nothing about memory layout, pointers, or arrays
• Language-independent — a contract, not code

ADT → Implementation

The ADT is the interface; the data structure is the implementation. A stack is not “an array” — it is an abstraction that can be backed by an array.

Core operations

Mental model

push(A)  push(B)  push(C)  pop()
                   ┌───┐
         ┌───┐    │ C │   ┌───┐
┌───┐   │ B │    │ B │   │ B │ ← top
│ A │   │ A │    │ A │   │ A │
└───┘   └───┘    └───┘   └───┘
                          returns C

What lives in a stack frame

Stack overflow

Unbounded recursion pushes frames without popping. When the call stack exceeds its allocated memory (typically 1–8 MB), the OS raises a stack overflow error.

def factorial(n):
    if n <= 1:         # base case
        return 1
    return n * factorial(n - 1)

Tail-call optimisation: some languages reuse the current frame for a recursive call in tail position, converting recursion to iteration. Supported in Scheme, Kotlin (tailrec). Not in Python or Java.

Algorithm

For each character c in the input:
  if c is '(' or '[' or '{':
      push(c)
  if c is ')' or ']' or '}':
      if stack is empty:
          return INVALID
      if top does not match c:
          return INVALID
      pop()
After all characters:
  return VALID if stack is empty

Trace: {[()]}

VALID — stack is empty after processing all characters.

Expression: 3 4 + 2 * 7 -   Result: 7

Algorithm

For each token:
  if token is a number:
      push(token)
  if token is an operator:
      b = pop()
      a = pop()
      push(a op b)
Return pop()

Used by HP calculators, Forth, PostScript, and the Java bytecode operand stack.

Rules

For each token:
  NUMBER   → output directly
  (        → push onto operator stack
  )        → pop & output until '('
  OPERATOR → while top has ≥ precedence:
                 pop & output
               push current operator
After all tokens:
  pop & output remaining operators

Trace: 3 + 4 * 2 - ( 1 + 5 )

Core operations

The queue is the natural structure for fairness — first come, first served. Every message broker, task runner, and print spooler is built on this principle.

Mental model

enqueue(A)  enqueue(B)  enqueue(C)

front                    front
  ↓                        ↓
┌───┐     ┌───┬───┐     ┌───┬───┬───┐
│ A │     │ A │ B │     │ A │ B │ C │
└───┘     └───┴───┘     └───┴───┴───┘
                                 rear

dequeue() → returns A

  front
    ↓
  ┌───┬───┐
  │ B │ C │
  └───┴───┘
       rear

How it works

Capacity: 5     head=0, tail=0 (empty)

enqueue(A): [A _ _ _ _]  h=0, t=1
enqueue(B): [A B _ _ _]  h=0, t=2
enqueue(C): [A B C _ _]  h=0, t=3
dequeue():  [_ B C _ _]  h=1, t=3  → A
enqueue(D): [_ B C D _]  h=1, t=4
enqueue(E): [_ B C D E]  h=1, t=0  ← wraps
enqueue(F): [F B C D E]  h=1, t=1  ← wraps

Key formulas

Why circular? A naive array queue wastes all space before the head pointer. Shifting elements on dequeue is O(n). The circular buffer solves both with modular arithmetic.

Operations

Implementations

A deque restricted to one end is a stack. Restricted to pushBack + popFront, it is a queue. Python's collections.deque is recommended for both.

Operations

A sorted array gives O(1) extract but O(n) insert. A heap gives O(log n) for both — the right trade-off for dynamic workloads.

Use cases

Array layout (min-heap)

Index:   0   1   2   3   4   5   6
Value: [10, 15, 20, 25, 30, 35, 40]

          10          Parent:  (i-1)/2
         /  \         Left:    2i + 1
       15    20       Right:   2i + 2
      / \    / \
    25  30  35  40

Heap operations

• Sift-up (after insert): place at end, swap with parent while smaller. O(log n)
• Sift-down (after extract): move last to root, swap with smallest child. O(log n)
• Heapify (build from array): sift-down on each non-leaf, bottom up. O(n)

Why O(n) heapify?

Most nodes are near the bottom and sift down only 1–2 levels. The sum forms a convergent geometric series:

This is why heapq.heapify() in Python and Arrays.sort() (Timsort) can build a heap in linear time — a non-obvious but critical result.

Pattern: Next Greater Element

def next_greater(nums):
    n = len(nums)
    result = [-1] * n
    stack = []    # indices; values decreasing
    for i in range(n):
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    return result

# nums   = [2, 1, 4, 3, 5]
# result = [4, 4, 5, 5, -1]

Each element is pushed once and popped at most once. Total: O(n) despite the nested loop.

Classic problems

Sliding window maximum

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()   # indices; values decreasing
    result = []
    for i, x in enumerate(nums):
        while dq and dq[0] < i - k + 1:
            dq.popleft()        # outside window
        while dq and nums[dq[-1]] <= x:
            dq.pop()            # maintain order
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

# nums=[1,3,-1,-3,5,3,6,7], k=3
# result=[3,3,5,5,6,7]

Complexity

A naive approach checks all k elements per window: O(nk). The monotonic deque eliminates redundant comparisons by discarding elements that can never be the maximum.

Auxiliary stack approach

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []  # parallel minimums

    def push(self, x):
        self.stack.append(x)
        m = min(x, self.min_stack[-1]) \
            if self.min_stack else x
        self.min_stack.append(m)

    def pop(self):
        self.min_stack.pop()
        return self.stack.pop()

    def getMin(self):
        return self.min_stack[-1]  # O(1)

All operations: O(1)

Alternative: encoded values

Store 2*x - current_min when x < current_min. On pop, decode the previous min. Uses O(1) extra space but risks integer overflow.

Strategy

• Stack IN — receives all enqueued elements
• Stack OUT — serves all dequeue requests
• When OUT is empty, pour all of IN into OUT (reversing order)

Trace

enqueue(1): IN=[1]     OUT=[]
enqueue(2): IN=[1,2]   OUT=[]
dequeue():  IN=[]      OUT=[2,1] ← pour
            IN=[]      OUT=[2]   → 1
enqueue(3): IN=[3]     OUT=[2]
dequeue():  IN=[3]     OUT=[]    → 2
dequeue():  IN=[]      OUT=[3]   ← pour
            IN=[]      OUT=[]    → 3

Amortised analysis

This is a popular interview question, but it also has real uses: functional languages without mutable arrays implement queues this way (e.g. Okasaki's persistent queue).

Lock-free queue (Michael & Scott, 1996)

Uses Compare-And-Swap (CAS) to atomically update head and tail pointers without locks.

CAS(addr, expected, new):
    atomically:
        if *addr == expected:
            *addr = new
            return true
        return false

• Enqueue: CAS tail's next from null to new node, then CAS tail forward
• Dequeue: CAS head from current to head.next
• If CAS fails, another thread succeeded — retry

Trade-offs

Standard library support

Key takeaways

• Stacks and queues are ADTs — define by operations and invariants, not implementation
• Array-backed implementations dominate due to cache locality
• The circular buffer solves the dequeue-shift problem with modular arithmetic
• Monotonic stacks/queues reduce common problems from O(n²) to O(n)
• A min-stack augments the stack ADT with O(1) minimum queries
• Two stacks make a queue with amortised O(1) — a foundational result
• Binary heaps power shortest-path and greedy algorithms
• Lock-free concurrent queues use CAS to avoid mutex bottlenecks

Recommended reading