Stack — LIFO semantics, push - pop - peek, array and linked list implementations: Visual walkthrough

We build ONE object across all figures: a row of numbered boxes (an array) and a single red pointer (the top). Red is always the pointer — nothing else is ever red.

Step 1 — Draw the boxes and name them

WHAT. An array is just a fixed row of storage slots laid side by side. We number them starting at $0$ : slot $0$ , slot $1$ , slot $2$ , and so on up to slot $n - 1$ for an array of size $n$ .

WHY number from 0 and not 1? Because the position of a slot is its distance from the start. Slot $0$ is zero steps from the front. This matches how memory addresses work and makes the arithmetic below clean.

PICTURE. Below: five empty boxes, their index written underneath. Nothing is stored yet.

Figure — Stack — LIFO semantics, push - pop - peek, array and linked list implementations

Step 2 — Where does `top` point when the stack is empty?

WHAT. With no elements at all, top cannot point at a real box, because every real box index is $0$ or higher. We need a value that means "nothing here yet". We choose: $top = - 1$ Here $- 1$ is a sentinel: a made-up value chosen precisely because it is one step below the first real index $0$ .

WHY $- 1$ specifically? Watch what the first push will need. The very first element must land in box $0$ . If pushing always does "move up by one, then store", then starting one below $0$ — at $- 1$ — puts the first element exactly at $- 1 + 1 = 0$ . The sentinel is chosen so the same push rule works even for the first element. No special case.

PICTURE. The red pointer sits to the left of box $0$ , hanging in empty space at position $- 1$ .

Step 3 — The push rule, born from one question

WHAT. To push(x) we ask: which box is the next free one? The highest filled box is top, so the next free box is $top + 1$ . We do two things in this exact order: $(1) climb to the next free box top \leftarrow top + 1, (2) drop x into it arr [top] \leftarrow x$

$top \leftarrow top + 1$ — the arrow $\leftarrow$ means "becomes". We raise the pointer by one so it now names the box that was free.
$arr [top] \leftarrow x$ — we write the value $x$ into the box the pointer now names.

WHY increment FIRST, store SECOND? Because top must always name a filled box. If we stored first at top+1 and then moved, there'd be a moment where top names an empty box — the invariant breaks. Climb, then place.

PICTURE. push(7) on the empty stack: red pointer climbs from $- 1$ to $0$ , then $7$ appears inside box $0$ .

Step 4 — Push again, and watch the pile grow upward

WHAT. Now push(4) then push(9). Each time: climb the red pointer one box, drop the value in.

$push (4) : top : 0 \to 1, arr [1] \leftarrow 4 push (9) : top : 1 \to 2, arr [2] \leftarrow 9$

WHY does this stay $O (1)$ ? Notice we never touch boxes $0$ or $1$ when pushing $9$ . We only ever look at the single box the pointer names. No shifting, no scanning — one step of work regardless of how tall the stack is.

PICTURE. Boxes $0, 1, 2$ hold $7, 4, 9$ . Red pointer sits at box $2$ . The "top" is $9$ — the last one in.

Recall Why is

$9$ the top and not $7$ ? Because $9$ was pushed last, and the red pointer always tracks the most recently placed box. Last-In sits highest ::: that is LIFO made physical.

Step 5 — The pop rule: read first, shrink second

WHAT. To pop() we return the top value and forget its box: $(1) read the top box x \leftarrow arr [top], (2) move pointer down top \leftarrow top - 1$

$x \leftarrow arr [top]$ — grab the value the red pointer names while it still names it.
$top \leftarrow top - 1$ — drop the pointer one box, so the box we just read is now "below the top" and will be overwritten by the next push.

WHY read BEFORE decrement? This is the mirror image of push. If we decremented first, top would name box $1$ (holding $4$ ), and we'd return $4$ — the wrong element — while the real top $9$ leaks away untouched. Order = (read, shrink).

PICTURE. pop() on $[7, 4, 9]$ : value $9$ is read out (arrow leaving box $2$ ), then red pointer slides down to box $1$ . The $9$ is now "forgotten" (greyed) even though the bytes may linger.

Step 6 — Edge case: popping down to empty

WHAT. Keep popping. pop() returns $4$ (top: $1 \to 0$ ), then pop() returns $7$ (top: $0 \to - 1$ ). Now top is back at $- 1$ .

WHY does $- 1$ reappear? The pop rule subtracts one each time. Starting from the last real element in box $0$ , one more decrement lands on $- 1$ — the very sentinel we defined in Step 2. The empty-state and the "just emptied" state are literally the same value, so isEmpty() needs no extra bookkeeping.

PICTURE. Pointer walks $2 \to 1 \to 0 \to - 1$ ; boxes empty one by one until red hangs left of box $0$ again — identical to Step 2.

Step 7 — Degenerate cases: empty pop and full push

WHAT. Two ways the naive rules would misbehave, and how the sentinel + capacity guard them:

Pop when empty ( $top = - 1$ ): reading $arr [- 1]$ is nonsense (in Python it silently wraps to the last box — a bug). So we test first: if $top = - 1$ , raise "pop from empty".
Push when full (fixed size $n$ ): the top box is $n - 1$ . If $top = n - 1$ already, then $top + 1 = n$ is outside the array. So we test: if $top = n - 1$ , raise "stack full" — this is overflow.

$isEmpty ⟺ top = - 1 isFull ⟺ top = n - 1$

WHY these two exact boundaries? The valid box indices are the whole numbers $0, 1, \dots, n - 1$ . top is legal only inside this range. Fall one below and you're empty; sit at the top end and there's no room to climb.

PICTURE. Two side-by-side error states: left, red pointer at $- 1$ with a blocked pop-arrow; right, pointer at box $n - 1$ (all boxes full) with a blocked push-arrow.

The one-picture summary

Everything collapses to one number line for top and two arrows. Push slides top right (+1, then store). Pop slides top left (read, then −1). The two walls at $- 1$ (empty) and $n - 1$ (full) are the only forbidden moves.

Recall Feynman: tell the whole walkthrough to a friend

Picture a row of numbered mail slots and one red flag that points at "the current top slot". When there's nothing, the flag rests just left of slot 0 — we call that position $- 1$ so the very first push works with no special rule. To push, the flag hops one slot to the right and we drop the value where it lands; that's why push is raise then store. To pop, we grab whatever the flag points at first, then let the flag drop one slot to the left — read then shrink, because grabbing after dropping would grab the wrong slot. Keep popping and the flag walks back to $- 1$ , exactly where it began — empty is empty is empty. Only two moves are illegal: dropping the flag below $- 1$ (popping an empty stack) or pushing past the last slot $n - 1$ (overflow). That's the entire array stack: one integer, two $\pm 1$ moves, two walls. Every operation touches exactly one slot, so it's all $O (1)$ . See Dynamic Array / Amortized Analysis for how the right wall can be pushed outward when the array is allowed to grow, and Recursion and the Call Stack for the same flag-and-slots picture running your program's function calls.

Recall Related builds

Linked List — singly linked — the other implementation, where the "top" is the head pointer instead of an integer index.
Expression Evaluation — infix to postfix and Depth-First Search — two algorithms that are just this push/pop dance in disguise.
Queue — FIFO semantics — the mirror-image structure where you take from the other end.