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

Before you can read the Stack topic note, you need to be fluent in a handful of tiny ideas: what a "collection" is, what an index means, what a pointer is, what $O(1)$ is trying to tell you, and the exact meaning of the sentinel -1. This page builds every one of them from nothing, in an order where each idea leans on the one before it.

0. What is a "collection" / "data structure"?

The picture: think of a physical container. A shelf, a queue at a shop, a pile of plates. Each is a "box of things", but they differ in how you are allowed to reach in. A stack is the "pile of plates" container: top only.

Why the topic needs it: the whole point of a stack is a restriction on access. You cannot appreciate the restriction until you know that other collections allow more (a shelf lets you grab any book). The stack deliberately gives that freedom up.

1. An index — naming slots with numbers

Look at the figure. Six slots drawn as boxes. The cyan number under each box is its index — 0,1,2,3,4,5. The value inside the box (like 1, 2, 3) is what is stored. Index and value are two different things: the index is the address, the value is the cargo.

Why the topic needs it: the array stack finds "the top" by remembering a single index. No index, no way to say where the top lives.

2. An array — a fixed row of numbered slots

The picture is exactly the row of boxes from Figure 1. "Contiguous" means the boxes are physically glued in a line — box 3 sits right after box 2. Because of that, jumping straight to arr[top] takes the same tiny effort no matter how big the array is.

Why the topic needs it: Implementation 1 of the stack is an array plus one index variable.

3. The variable top and the sentinel -1

Trace the figure left to right:

• Empty: top = -1, pointing into the void below slot 0.
• After push(1): top moved up to 0; slot 0 holds 1.
• After push(2): top moved up to 1; slot 1 holds 2.

Notice the pattern: push moves top up by one, then stores. The amber arrow always points at the current top element.

Why the topic needs it: every array-stack test (is_empty, is_full, push, pop) is arithmetic on this one number.

4. A pointer / reference — an arrow to a thing

The figure shows three boxes chained by arrows. Each box is a node: it holds a data part (the value) and a next part (an arrow to the box beneath it). The last box's next points to None — the amber "ground" symbol meaning "chain ends here".

• head is a pointer to the topmost box.
• head.next follows one arrow down.
• None is the sentinel for "no box".

Why the topic needs it: Implementation 2 (linked list) has no indices at all — it navigates purely by following these arrows. head plays the role that top played in the array.

5. None — the "nothing" value

The picture: the amber ground symbol in Figure 3, and the empty grey boxes in Figure 1. Both say "no real value lives here."

Why the topic needs it: is_empty for the linked stack is literally head is None.

6. Big-O notation: $O(1)$ vs $O(n)$

The picture: touching the top plate of a pile takes the same flick whether the pile is 3 plates or 3000 → that is $O(1)$. Searching every plate to find a red one takes longer as the pile grows → that is $O(n)$.

Why the topic needs it: the entire selling point of a stack is that its operations are $O(1)$. The letters $O$, the number $1$, and the symbol $n$ all appear in the parent's cost tables — now they mean something.

Prerequisite map

Every arrow reads "feeds into". The array path and the pointer path are two independent routes to the same idea — the two implementations in the parent note.

Where these lead

Once solid here, you are ready for the Stack topic itself, and these neighbours reuse the same tools:

• Linked List — singly linked — the exact node-and-pointer machinery from §4.
• Dynamic Array / Amortized Analysis — what happens when the fixed array in §2 fills up.
• Queue — FIFO semantics — the opposite promise to LIFO (First In, First Out).
• Recursion and the Call Stack, Expression Evaluation — infix to postfix, Depth-First Search — all use a stack once you have built one.

Equipment checklist

Cover the right-hand side; say the answer aloud before revealing.