Stacks and Queues — The Two Data Structures You'll Use Everywhere

Stacks and queues are deceptively simple. You learn them early, maybe implement one with an array, and move on. Then six months later you're staring at a medium-difficulty interview problem and the entire solution hinges on knowing when to reach for a stack versus a queue. Worth understanding properly.

The Core Difference

A stack is last-in, first-out (LIFO). Think of a stack of plates — you grab the one on top. The last thing you added is the first thing you remove.

A queue is first-in, first-out (FIFO). Think of a line at a coffee shop. First person in line gets served first.

That's genuinely it. Every stack and queue problem reduces to this distinction.

Implementation

You don't need a linked list for most cases. An array works fine.

Stack with an array:

stack = []
stack.append(10)   # push
stack.append(20)
top = stack.pop()  # 20 — last in, first out

push and pop are both O(1) with a dynamic array. Done. Queue with an array (careful here):

from collections import deque
queue = deque()
queue.append(10)      # enqueue
queue.append(20)
front = queue.popleft()  # 10 — first in, first out

If you use a plain list and pop(0), you're paying O(n) because every element shifts. Use a deque or a linked list. In Java, LinkedList implements Queue. In JavaScript, there's no built-in efficient queue — you'd roll your own or use a library if performance matters.

Where Stacks Show Up

The call stack. Every function call pushes a frame. When the function returns, it pops. This is why infinite recursion causes a stack overflow — you ran out of stack space. Undo/redo. Each action pushes onto an undo stack. When you undo, pop the action and push it onto a redo stack. Clean and elegant. Expression evaluation. Compilers use stacks to parse expressions, match brackets, convert between infix and postfix notation. DFS (depth-first search). The recursive version uses the call stack implicitly. The iterative version uses an explicit stack.

Where Queues Show Up

BFS (breadth-first search). You process nodes level by level. Queue ensures you visit all neighbors at the current depth before going deeper. This is the classic use case. Task scheduling. Print queues, message queues, job queues in distributed systems — anything where order of arrival matters. Rate limiting and buffering. Requests come in, get queued, get processed in order.

The Interview Problems That Keep Coming Back

Valid Parentheses

Given a string of brackets like ({[]}), determine if it's valid. Classic stack problem.

Push opening brackets. When you hit a closing bracket, pop and check if it matches. If the stack is empty at the end, it's valid.

def is_valid(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in '([{':
            stack.append(char)
        elif not stack or stack.pop() != pairs[char]:
            return False
    return len(stack) == 0

Short, clean, O(n). This one appears in real interviews constantly.

Min Stack

Design a stack that supports push, pop, top, and getMin — all in O(1).

The trick: maintain a second stack that tracks the current minimum. Every time you push, also push the current min onto the min stack. When you pop, pop from both.

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

def push(self, val):
        self.stack.append(val)
        current_min = min(val, self.min_stack[-1] if self.min_stack else val)
        self.min_stack.append(current_min)

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

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

BFS with a Queue (Level Order Traversal)

Traverse a binary tree level by level. Queue-based BFS is the textbook approach.

def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

The for _ in range(len(queue)) pattern processes one level at a time. Memorize this — it appears in a surprising number of tree and graph problems.

Priority Queues (Quick Mention)

A priority queue isn't a regular queue — elements come out by priority, not insertion order. Under the hood it's usually a heap. Different data structure, but worth knowing that it exists because interviewers sometimes ask you to "optimize" a queue-based solution with a priority queue for problems like merging k sorted lists or finding the kth largest element.

When to Use Which

Stack when you need to process things in reverse order, match nested structures, or simulate recursion iteratively. Queue when you need to process things in the order they arrived, or explore something level by level.

If you want to practice these patterns hands-on with real problems, CodeUp has an interactive DSA environment where you can step through stack and queue operations visually. Seeing the push/pop happen in real time makes the mental model stick faster than reading about it.

Stacks and queues aren't glamorous. But they're the backbone of half the algorithms you'll encounter. Get comfortable reaching for them instinctively — that's what separates someone who solves problems from someone who stares at them.