Basic Operations on a Stack

Push and pop are both O(1) — but why? A stack only ever touches one end, so there’s no shifting, no searching, no traversal. The entire implementation comes down to moving a single top marker up and down. Watch for that and the code below holds no surprises.

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

Predict first

Run this in your head: push 5, push 9, push 2, peek, pop, push 7, then pop, pop, pop. After everything, is the stack empty — and which value is the VERY LAST one popped?

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.

Recall: it’s all in the `top` marker

Both operations are just moving top. Fill in the two lines that move it:

python · fill in the blanks0/2 hints

def push(self, val):
  if self.is_full():
      return
  # ??? move the top marker
  self.data[self.top] = val
 
def pop(self):
  if self.is_empty():
      return None
  val = self.data[self.top]
  # ??? move the top marker
  return val

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.

Quick check

Why are both push and pop O(1) on a stack, regardless of how many elements it holds?

You can now build a stack two ways and know why each op is O(1). Next: stack applications — balanced parentheses, expression evaluation, and the monotonic stack — where this humble structure does surprisingly heavy lifting.

Introduction Applications

Finished this page?