Data Structures & Algorithms Cheatsheet

Stacks and Queues

Use this Data Structures & Algorithms reference while you build software engineering projects, review code, or refresh the syntax you reach for most.

Complexity

Both are O(1) for their defining operations. The difference is which end you take from.

Operation	Stack (LIFO)	Queue (FIFO)	Deque
push or append at end	O(1)	O(1)	O(1)
pop from end	O(1)	O(n)	O(1)
pop from front	O(n)	O(1)	O(1)
peek	O(1)	O(1)	O(1)
search	O(n)	O(n)	O(n)
space	O(n)	O(n)	O(n)

A Python list is a fine stack. It is a bad queue, because pop(0) shifts every element. Use collections.deque.

Python Implementations

# stack: a plain list
st = []
st.append(x)          # push
st.pop()              # pop, IndexError if empty
st[-1]                # peek
if not st: ...        # empty check

# queue and deque: collections.deque, O(1) at both ends
from collections import deque
q = deque()
q.append(x)           # push right
q.popleft()           # pop left, IndexError if empty
q.appendleft(x)
q.pop()
q[0], q[-1]           # peek either end
deque(maxlen=5)       # bounded, drops from the far end automatically
q.rotate(1)           # rotate right by 1
q.extendleft([1, 2])  # note: reverses the order of the argument

Deque<Integer> st = new ArrayDeque<>();   // use for BOTH stack and queue
st.push(1); st.pop(); st.peek();          // stack ends
st.addLast(1); st.pollFirst();            // queue ends
st.isEmpty(); st.size();
// Legacy java.util.Stack is synchronized and iterates bottom-up. Avoid it.
// java.util.LinkedList works but allocates a node per element.

stack<int> st;  st.push(1); st.top(); st.pop();   // pop returns void
queue<int> q;   q.push(1); q.front(); q.pop();
deque<int> dq;  dq.push_back(1); dq.pop_front();

C++ stack::pop() returns void. Read top() first, then pop(). Popping an empty stack or queue is undefined behavior, not an exception.

Matching And Nesting

Any problem about balanced pairs, nesting depth, or "undo the last thing" is a stack.

def is_valid(s):
    """Valid Parentheses. O(n) time, O(n) space."""
    pairs = {")": "(", "]": "[", "}": "{"}
    st = []
    for ch in s:
        if ch in pairs:
            if not st or st.pop() != pairs[ch]:
                return False
        else:
            st.append(ch)
    return not st

def min_remove_to_valid(s):
    """Drop the minimum number of parentheses to balance."""
    chars = list(s)
    st = []
    for i, ch in enumerate(chars):
        if ch == "(":
            st.append(i)
        elif ch == ")":
            if st:
                st.pop()
            else:
                chars[i] = ""       # unmatched closer
    for i in st:
        chars[i] = ""               # unmatched openers
    return "".join(chars)

def simplify_path(path):
    """Unix path canonicalization."""
    st = []
    for part in path.split("/"):
        if part == "..":
            if st:
                st.pop()
        elif part and part != ".":
            st.append(part)
    return "/" + "/".join(st)

def decode_string(s):
    """"3[a2[c]]" -> "accaccacc". Two stacks, one for counts."""
    counts, parts = [], [""]
    num = 0
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch == "[":
            counts.append(num)
            parts.append("")
            num = 0
        elif ch == "]":
            done = parts.pop() * counts.pop()
            parts[-1] += done
        else:
            parts[-1] += ch
    return parts[0]

Monotonic Stack

A stack whose values stay sorted. It answers "next greater" and "previous smaller" questions in O(n) total, because each index is pushed and popped at most once.

Question	Stack order	Pop while
next greater element	decreasing	`a[st[-1]] < a[i]`
next smaller element	increasing	`a[st[-1]] > a[i]`
previous greater	decreasing	pop before pushing, peek is the answer
previous smaller	increasing	same, peek before push

def next_greater(a):
    """For each index, the next strictly greater value, or -1."""
    res = [-1] * len(a)
    st = []                         # indices, values decreasing
    for i, x in enumerate(a):
        while st and a[st[-1]] < x:
            res[st.pop()] = x
        st.append(i)
    return res

def daily_temperatures(t):
    """Days until a warmer temperature."""
    res = [0] * len(t)
    st = []
    for i, x in enumerate(t):
        while st and t[st[-1]] < x:
            j = st.pop()
            res[j] = i - j
        st.append(i)
    return res

def largest_rectangle(heights):
    """Largest Rectangle in Histogram. O(n)."""
    st = []                         # indices, heights increasing
    best = 0
    for i, h in enumerate(heights + [0]):   # sentinel flushes the stack
        while st and heights[st[-1]] >= h:
            height = heights[st.pop()]
            left = st[-1] + 1 if st else 0
            best = max(best, height * (i - left))
        st.append(i)
    return best

The sentinel trick (appending a 0 or inf) drains the stack at the end so no bar is left unmeasured. Without it the tallest trailing run is missed.

Queues For Level Order

BFS is the queue's main use. Snapshot the queue length at the top of each round to process one level at a time.

from collections import deque

def level_order(root):
    if not root:
        return []
    out, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):     # freeze the level size first
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        out.append(level)
    return out

A monotonic deque extends this to sliding-window extremes in O(n), covered under sliding window.

Building One From The Other

A classic follow-up question. Both directions rely on amortized reversal.

class QueueFromStacks:
    """Amortized O(1) per operation, worst case O(n) on one pop."""
    def __init__(self):
        self.inbox, self.outbox = [], []

    def push(self, x):
        self.inbox.append(x)

    def _shift(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self):
        self._shift()
        return self.outbox.pop()

    def peek(self):
        self._shift()
        return self.outbox[-1]

class MinStack:
    """push, pop, top, getMin all O(1). Store the running min per level."""
    def __init__(self):
        self.st = []                # (value, min so far)

    def push(self, x):
        cur = x if not self.st else min(x, self.st[-1][1])
        self.st.append((x, cur))

    def pop(self):
        return self.st.pop()[0]

    def top(self):
        return self.st[-1][0]

    def get_min(self):
        return self.st[-1][1]

Gotchas

Never use list.pop(0) as a queue. It is O(n), which turns an O(V + E) BFS into O(V²).
Push indices, not values, in monotonic stacks whenever the answer needs a distance or a width.
Strict versus non-strict pops. < versus <= decides how ties are handled. For histogram widths and "count of equal elements" problems it changes the answer.
Check empty before peeking. st[-1] on an empty list raises IndexError, and st and st[-1] < x short-circuits correctly only in that order.
Freeze len(q) in BFS before the inner loop. Reading it live mixes levels together.
java.util.Stack iterates bottom to top, the reverse of what most people expect. ArrayDeque iterates top to bottom.
deque.extendleft reverses. deque().extendleft([1, 2, 3]) yields 3, 2, 1.
Recursion is a stack. Any explicit stack solution can be written recursively and vice versa. Convert to explicit when depth risks a stack overflow.