Stack & Queue

On this page

The Idea
Build It
Know It
Break It
Use It

Quick reference

Stack push	O(1) amortized (array) / O(1) (DLL)
Stack pop / peek	O(1)
Queue enqueue/dequeue — naive array (removeFirst shifts)	O(1) enqueue / O(n) dequeue
Queue enqueue/dequeue — Doubly Linked List backed	O(1) / O(1)
Queue enqueue/dequeue — two stacks	O(1) amortized / O(1) amortized

The Idea

A stack is a cafeteria tray pile. Trays go on top, and the only tray you can ever grab is the one on top — you can't pull one from the middle without lifting off everything stacked above it first. That's Last In, First Out (LIFO): whatever was added most recently is the first thing to come off.

A queue is a checkout line. New people join at the back, but the person served next is whoever has been waiting longest — the front of the line. That's First In, First Out (FIFO): whatever was added first is the first thing to leave.

Same two operations — add something, remove something — but the two structures disagree about which end removal happens on. A stack removes from the same end it adds to, so pushing 1, 2, 3 and then popping three times hands them back 3, 2, 1: the order is reversed. A queue removes from the opposite end it adds to, so enqueuing 1, 2, 3 and then dequeuing three times hands them back 1, 2, 3: the order is preserved. That single difference — same-end vs. opposite-end removal — is the entire distinction between the two structures.

Stack reverses order (LIFO), queue preserves it (FIFO) — same two operations, opposite choice of which end you remove from.

Build It

Two structures, two disciplines

structure Stack:
    // built on an array, OR on a Doubly Linked List's head — either works
    items         // top of stack is items[length - 1], or list.head

structure Queue:
    // built on a Doubly Linked List — head is the front, tail is the back
    list          // -> DoublyLinkedList from Phase 2, empty when list.head is NULL

Stack via array — push/pop/peek, O(1) amortized

function push(stack, value):
    stack.items.append(value)          // grow the array by one slot at the end

function pop(stack):
    if stack.items is empty:
        error "stack underflow"
    return stack.items.removeLast()    // shrink the array by one slot at the end

function peek(stack):
    if stack.items is empty:
        error "stack underflow"
    return stack.items[length - 1]     // look, don't remove

Appending and removing at an array's end is O(1) amortized — recall Arrays & Strings Fundamentals: most appends just write into open capacity, and the occasional resize-and-copy averages out to O(1) per operation over a long run.

Stack via a doubly linked list — push/pop at the head, O(1) worst case

function push(stack, value):
    insertAtHead(stack.list, value)    // Phase 2's operation, verbatim

function pop(stack):
    if stack.list.head is NULL:
        error "stack underflow"
    value = stack.list.head.value
    deleteNode(stack.list, stack.list.head)   // O(1) — no walk needed
    return value

This is Doubly Linked List's insertAtHead and deleteNode doing double duty as push and pop. No amortized asterisk here — every single push and pop is O(1), not just O(1) on average, because there's never a resize to pay for.

Queue via a doubly linked list — enqueue at tail, dequeue at head, both O(1)

function enqueue(queue, value):
    insertAtTail(queue.list, value)    // Phase 2's operation — O(1) thanks to the tail pointer

function dequeue(queue):
    if queue.list.head is NULL:
        error "queue underflow"
    value = queue.list.head.value
    deleteNode(queue.list, queue.list.head)   // O(1) — no walk needed
    return value

This is exactly why Doubly Linked List built a tail pointer and an O(1) deleteNode: a queue needs to add at one end and remove at the other, fast, forever. Try this on a plain array instead and dequeue means removeFirst — every remaining element has to shift down one slot to fill the gap, which is O(n) per dequeue. The DLL sidesteps that shifting entirely because removing the head never touches any other node.

Queue via two stacks — O(1) amortized per operation, no linked list needed

structure TwoStackQueue:
    inStack       // absorbs every enqueue
    outStack      // supplies every dequeue

function enqueue(queue, value):
    push(queue.inStack, value)

function dequeue(queue):
    if queue.outStack is empty:
        while queue.inStack is not empty:      // pour everything across, once
            push(queue.outStack, pop(queue.inStack))
    if queue.outStack is empty:                // still empty after pouring — inStack was empty too
        error "queue underflow"
    return pop(queue.outStack)

Pouring inStack into outStack reverses the order twice: inStack held newest-on-top, outStack ends up with oldest-on-top — exactly FIFO order, popped from outStack. The pour only happens when outStack runs dry, and each value is poured at most once between the moment it's enqueued and the moment it's dequeued — that's the amortized argument from Big-O Notation: individual dequeues vary between O(1) and O(n), but summed over any sequence of operations the total pouring work is bounded by the total number of enqueues, so the average per operation is O(1).

Know It

Stack push/pop/peek are O(1), full stop — no walk, no search, whichever way you build it. Queue is where the choice of structure matters: a plain array's removeFirst shifts every remaining element down one slot, which is O(n) per dequeue. Swap the array for the Phase 2 doubly linked list — or use the two-stack trick — and dequeue drops to O(1).

Operation	Time	Space	Why
Stack push	O(1) amortized (array) / O(1) (DLL)	O(1)	Array: one write, occasional resize-and-copy averages out. DLL: rewrite a couple pointers around the new head, no resize ever.
Stack pop / peek	O(1)	O(1)	Only the top is ever touched — array's last slot or the list's head, no walk either way.
Queue enqueue/dequeue — naive array (removeFirst shifts)	O(1) enqueue / O(n) dequeue	O(1)	Removing the front slot leaves a gap; every remaining element must shift down one index to close it.
Queue enqueue/dequeue — Doubly Linked List backed	O(1) / O(1)	O(1)	insertAtTail and deleteNode(head) from Phase 2 — the tail pointer and the node's own prev/next mean neither end ever needs a walk.
Queue enqueue/dequeue — two stacks	O(1) amortized / O(1) amortized	O(1) extra (two stacks holding the queue's own elements)	Every value is pushed onto inStack once and poured to outStack at most once — total pouring work across n operations is O(n), so O(1) per operation on average, even though a single dequeue can occasionally cost O(n) mid-pour.

Break It

Underflow — pop or dequeue from empty

the stack's items are empty, or the queue's list.head is NULL

Popping or dequeuing without checking for empty first dereferences a value that isn't there — a crash, or worse, silently returning garbage. Every pop/dequeue must check emptiness before it touches anything, the same discipline as checking head is NULL before deleting from an empty linked list.

Fixed-size array stack overflowing, or a resizing one hiding an O(n) cost

push exceeds a fixed-capacity array's length, or triggers a growth resize

A stack backed by a fixed-size array can silently overflow — writing past the allocated end — if push never checks capacity first. A resizing array stack avoids that, but only by occasionally copying every existing element into a bigger array: that single push is O(n), not O(1). It's still O(1) amortized over many pushes, but treating every individual push as cheap is wrong if you're reasoning about worst-case latency for one specific operation, not the long-run average.

Naive array queue degrading to O(n) per operation

dequeue is implemented as removeFirst on a plain array

It's tempting to reach for the same array that worked fine for a stack, but a queue removes from the opposite end it adds to — and removing index 0 from an array means shifting every other element down by one to close the gap. Do that on every dequeue and a queue that looks O(1) at a glance is actually O(n) per operation, O(n²) over a full run. The fix is the DLL-backed queue or the two-stack trick above, not a plain array with removeFirst.

Two-stack queue implemented wrong — pouring when outStack isn't empty

dequeue pours inStack into outStack unconditionally, instead of only when outStack is empty

outStack's order only stays correct — oldest on top — if it's never disturbed by a fresh pour while it still holds older, not-yet-dequeued values. Pour into it while it's non-empty and the older values that were already correctly ordered on top get buried under a fresh reversed batch, corrupting the FIFO order: a later dequeue can return a value that was actually enqueued more recently than one still sitting underneath. The guard "only pour when outStack is empty" is not an optimization — it's what makes the algorithm correct at all.

Use It

Valid Parentheses

Push every opening bracket. On a closing bracket, pop and check it matches — an empty stack when a closer arrives, or a leftover stack at the end, both mean invalid.

Easy

Implement Queue using Stacks

The two-stack queue from Build It, directly: push straight onto inStack, pour to outStack only when outStack is empty.

Easy

Implement Stack using Queues

Mirror image of the two-stack trick: after enqueuing a new value, rotate the queue by dequeuing and re-enqueuing everything that came before it, so the newest value ends up at the front.

Easy

Min Stack

A second stack tracks the running minimum alongside the first: push the new min (or repeat the current min) every time the main stack pushes, pop both together — O(1) getMin with no scan.

Medium

Baseball Game

A running score history is exactly a stack: each new op either pushes a computed value or pops/reads recent entries ('+' needs the top two, 'C' removes the top, 'D' doubles the top).

Easy

Backspace String Compare

Revisit from Two Pointers: there you may have scanned in place. Now build each string with an explicit stack — push each letter, and let '#' pop — then compare the two resulting stacks.

Easy

Remove All Adjacent Duplicates In String

Push each character; if it matches the top of the stack, pop instead of pushing. What remains on the stack at the end, read bottom to top, is the answer.

Easy

Evaluate Reverse Polish Notation

Push numbers. On an operator, pop the top two, apply the operator, push the result back — the stack always holds exactly the operands still waiting to be combined.

Medium

Time Needed to Buy Tickets

Simulate the checkout line directly: it's a queue where each person re-joins the back if they still need more tickets, and you're counting seconds until your specific position is served for the last time.

Easy

Number of Recent Calls

A queue holding a sliding time window — callback to Sliding Window's variable-size shape: enqueue every new call, then dequeue from the front while it's more than 3000ms behind the newest call.

Easy