Basic Operations on a Stack

There are two natural ways to build a stack: backed by an array or backed by a linked list. The API is the same — the trade-offs differ.

We’ll implement both. Pick whichever feels more comfortable; the operations are identical from the outside.

In real code you almost never write your own stack — your language already has one. Python uses list, Java has Deque / ArrayDeque, C++ has std::stack. But implementing it once teaches you exactly why push and pop are O(1).

Part 1 — Stack using an Array

The array version uses an index variable called top that points to the most recently pushed element. We push by incrementing top; we pop by decrementing it.

Push (insert an element)

The plan: bump top by one, write the value into stack[top]. If top is already at the end of the array, we have overflow.

ALGORITHM push(val)
    if top == MAX - 1
        report Overflow; return
    top = top + 1
    stack[top] = val

Pop (remove the top element)

Read stack[top], then decrement top. If top is -1, the stack is already empty — that’s underflow.

ALGORITHM pop()
    if top == -1
        report Underflow; return
    val = stack[top]
    top = top - 1
    return val

⚠️

Notice we don’t actually erase the old value — we just move top down. The next push will overwrite it. Languages with garbage collectors (Python, Java) sometimes prefer to null the slot out so the old object can be collected.

Peek (look at the top without removing)

Return stack[top]. Don’t move top. If empty, underflow again.

ALGORITHM peek()
    if top == -1
        report Underflow
    return stack[top]

Walk through it

Trace exactly what top does as we run the operations below:

Trace on an array-backed stack

Step 0 / 9 — (idle)

── top ──

(empty)

size: 0 / 6

Part 2 — Stack using a Linked List

In the linked-list version, top is a pointer to the head node. Push means prepending a new head; pop means moving the head pointer to the next node. There’s no fixed capacity, so no overflow (unless you literally run out of memory).

Push (insert at the head)

Allocate a new node, point its next at the current head, then make the new node the head.

ALGORITHM push(val)
    newNode = new Node(val)
    newNode.next = top
    top = newNode

Pop (remove the head)

Save the head’s value, move top to top.next, free the old head if you’re in a manual-memory language.

ALGORITHM pop()
    if top == NULL
        report Underflow; return
    val = top.data
    temp = top
    top = top.next
    free temp
    return val

Peek

Return the head’s value. Don’t touch the pointer.

Part 3 — Just use the built-in

Real-world advice: unless you’re learning, don’t write your own. Every modern language has one ready to go.

⚠️

Java has a legacy java.util.Stack class, but the official docs recommend ArrayDeque — it’s faster and doesn’t carry synchronization overhead from the 1990s.

Summary

	Array-backed	Linked-list-backed
Push / Pop	O(1)	O(1)
Memory	One block, cache-friendly	Scattered nodes, pointer overhead
Capacity	Fixed (or amortized O(1) with resize)	Unbounded
Overflow?	Yes, if fixed	Only on out-of-memory

The array version wins for almost all real use cases — better cache behavior, lower memory overhead per element. The linked-list version is mainly interesting for teaching, and useful when you genuinely need true O(1) push without amortization.

Up next: the practice problems where stacks really earn their keep.

Introduction Applications