Imagine you are paginating an undo history. Every action the user takes pushes onto something; every Ctrl-Z pops off the top. Now imagine you are processing a job queue: workers grab the oldest task first, add new tasks to the back. The first thing is a stack. The second is a queue. The shape of the access pattern decides the data structure, and that decision drives almost every interactive system you have ever used.

This is a cheat sheet, written from the perspective of someone who has shipped both well and shipped both badly. The good news is that there are only a few rules and a few footguns. The bad news is that the footguns are buried inside the standard library of every popular language, so you have to know which method maps to which performance.

Definitions, in two sentences

A stack is a Last-In-First-Out (LIFO) container. The two operations are push (add to the top) and pop (remove from the top). Both should be O(1).

A queue is a First-In-First-Out (FIFO) container. The two operations are enqueue (add to the back) and dequeue (remove from the front). Both should be O(1).

A deque (double-ended queue) supports push and pop at both ends in O(1). It is a strict superset of stacks and queues, which is why most modern languages give you a deque and call it a day.

The four operations and their costs by language

This is the table that catches everyone at least once. Notice the columns: in plain JS arrays and Python lists, pop-from-front is O(n), because every remaining element has to shift down by one slot. If you build a queue out of Array.shift() or list.pop(0), you have just written an O(n) operation in a hot loop and you will not notice until production scales.

Stacks: just push and pop

For a stack, you can use almost anything that supports push/pop at one end. JS arrays work fine: arr.push(x) and arr.pop() are both O(1). Python lists work fine: lst.append(x) and lst.pop() are both O(1). Java Stack is a thing in the standard library, but it is synchronized and ancient, and the modern recommendation is Deque<T> stack = new ArrayDeque<>() with push/pop. Go does not have a built-in stack, but a slice with append and shrinking the last element is the idiomatic version.

// Balanced parentheses, the canonical stack interview problem
function isBalanced(str) {
    const stack = [];
    const pairs = { ')': '(', ']': '[', '}': '{' };
    for (const ch of str) {
        if (ch === '(' || ch === '[' || ch === '{') stack.push(ch);
        else if (ch in pairs) {
            if (stack.pop() !== pairs[ch]) return false;
        }
    }
    return stack.length === 0;
}

Stack patterns are everywhere once you start looking. Recursive function calls (the call stack itself), expression evaluation, undo/redo, browser back button, depth-first traversal of a tree without recursion. Whenever you find yourself thinking "I want to remember this and come back to it later, in reverse order", you want a stack.

Queues: this is where the footguns live

Queues are where the language differences bite. The naive implementation in JS or Python is wrong, and I have shipped the wrong version. Here is what not to do:

# Wrong: O(n) per dequeue
queue = []
queue.append("task1")
queue.append("task2")
first = queue.pop(0)   # shifts every remaining element

At 1,000 tasks the average dequeue does 500 shifts. At 100,000 tasks it does 50,000 shifts per dequeue and the loop becomes O(n^2). The fix in Python is to use collections.deque, which is a doubly-linked list of small arrays under the hood:

from collections import deque

queue = deque()
queue.append("task1")
queue.append("task2")
first = queue.popleft()    # O(1)

In JavaScript, the analogous fix is harder because the standard library does not ship a deque. The two real options are: (1) use a small library (@datastructures-js/queue or similar), (2) implement a circular-buffer queue yourself if performance matters and you do not want a dependency, or (3) use an array with a head pointer that just increments on dequeue, and only periodically compact (this is the hack I have shipped most often). For tiny queues with under a few hundred items the Array.shift cost is negligible and you can ignore the issue. For anything that grows past a thousand entries, switch.

In Java, Queue<T> q = new ArrayDeque<>() gives you O(1) offer and poll. There is also LinkedList, which implements Queue, but ArrayDeque is faster in practice because of cache behaviour.

Real use-cases I have actually shipped

A few patterns from production that I want to name explicitly because they are not the textbook examples.

Browser-history stack. A stack of URLs the user has visited, with push on navigation and pop on the back button. The forward button needs a second stack, and you have to clear it when the user navigates fresh. This is two stacks plus a small state machine and that is the entire feature.

BFS frontier in graph traversal. A queue of nodes to visit. Enqueue the start, then loop: dequeue, visit, enqueue all unvisited neighbours. The fact that BFS uses a queue (and DFS uses a stack) is the entire structural difference between the two algorithms. Same code, different container, different traversal order.

Job processing. A queue of pending tasks consumed by N workers. The producer pushes; workers pull. In a single process this is a deque plus a lock, in a distributed system this is Redis or RabbitMQ or SQS, but the API shape is identical.

Print spool. Old-school but still relevant. The OS keeps a FIFO of jobs, the printer pulls in order. The fact that everyone implicitly accepts "first to submit, first to print" is a queue contract baked into our intuition.

Where to dig deeper

If you want to keep learning past the cheat-sheet level, three resources have actually paid back time for me. CLRS (Introduction to Algorithms) chapter 10 walks through stack and queue implementations with the kind of precision that exposes invariants you might miss. The CPython source for collections.deque (Modules/_collectionsmodule.c) is genuinely readable C, and reading it will teach you why a doubly-linked list of small arrays beats both the textbook linked list and a single dynamic array. For JavaScript, the V8 blog posts on Array internals explain why push and pop are fast and shift and unshift are not, in terms of the holey-vs-packed array states the engine tracks.

The takeaway from all three is the same: stacks and queues look like simple structures, but in real code you choose between them not on access patterns alone, but on which language primitive gives you the right operations at the right cost. Pick the wrong primitive and you have written O(n^2) by accident. Pick the right one and the code is small, fast, and obvious.