Stack

Picture a stack of plates: you add a new plate on top, and when you need one, you take from the top too. The plate at the bottom, placed first, is the last one you'd ever get to. That single rule, add and remove only from the top, is exactly what a stack data structure is.

LIFO: Last In, First Out

If you push 10, then 20, then 30, then 40 onto a stack, the order they come back out is the reverse: 40, then 30, then 20, then 10. There is no way to reach 10 without first removing everything stacked above it, exactly like the bottom plate in the stack of plates.

Stack ADT: the core operations

As an abstract data type, a stack exposes four operations, without saying anything about how it's actually stored underneath (that's a separate implementation choice, covered next):

PUSH(x)   → insert element x on top of the stack
POP()     → remove and return the top element
PEEK()    → return the top element without removing it
isEmpty() → return true if the stack has no elements

The element at the top, 40 here, is the only one directly accessible. To reach 30, you'd first have to POP 40 off. Removal always happens in this order: 40, then 30, then 20, then 10.

Array representation of a stack

The simplest way to implement a stack is with an array plus a single variable, TOP, that tracks the index of the current top element.

The box at index 3 (highlighted) holds the current top element, so TOP = 3. Index 4 is still empty, unused space the array has reserved but the stack hasn't grown into yet.

By convention, TOP = -1 marks an empty stack, since there's no valid index yet for a top element.

PUSH and POP

PUSH: inserting an element

To push a new item onto the stack:

1. Check whether the stack is full. If it is, print OVERFLOW and stop.
2. Increment TOP.
3. Store the item at stack[TOP].

Pushing 40 onto [10, 20, 30, _] (capacity 4, TOP currently at index 2) moves TOP to index 3 and writes 40 there:

Checking for a full stack first matters because writing past the array's last valid index would silently corrupt memory outside the array, which is exactly what the overflow check exists to prevent.

PUSH(S, item)
 
1. If TOP == MAX - 1
       Print "OVERFLOW"
2. Else
       TOP = TOP + 1
       S[TOP] = item
3. Stop

POP: removing the top element

To pop the top item off:

1. Check whether the stack is empty. If it is, print UNDERFLOW and stop.
2. Read S[TOP].
3. Decrease TOP.
4. Return the deleted element.

Notice POP doesn't actually erase the value at S[TOP], it just moves TOP down by one. The old value is still sitting in the array, but it's no longer considered part of the stack, since nothing above the new TOP is "in" the stack anymore. A future PUSH will simply overwrite it.

POP(S)
 
1. If TOP == -1
       Print "UNDERFLOW"
2. Else
       item = S[TOP]
       TOP = TOP - 1
       return item

PEEK: reading without removing

PEEK is the read-only version of POP, it looks at the top element but leaves the stack unchanged:

If TOP == -1
    stack is empty
Else
    return S[TOP]

Overflow and underflow

Both PUSH and POP check for their respective failure condition first, before touching TOP or the array, which is why the overflow/underflow checks appear as step 1 in both algorithms above, not as an afterthought.

Stack complexity

Every core stack operation touches only the top, regardless of how many elements are below it, so all four run in constant time:

Applications

LIFO ordering shows up anywhere "undo the most recent thing first" is the natural behavior:

• Function calls and recursion: every time a function calls another, the call stack pushes a new frame (local variables, return address); when a function returns, its frame pops off, so control resumes in the function that called it last, exactly LIFO.
• Undo in editors: each action gets pushed onto an undo stack; pressing undo pops the most recent action first, then the one before it, and so on.
• Expression evaluation: converting infix expressions to postfix and evaluating postfix expressions both use a stack to hold operators or operands until they're needed, covered in a later section of this module.
• Backtracking: algorithms that explore a path and need to "step back" when it fails (maze solving, syntax parsing, browser back button) push each step taken so they can pop back to the last decision point.

Quick recall

• A stack allows insertion and deletion only at one end (the top), giving LIFO ordering: last in, first out.
• The Stack ADT exposes PUSH, POP, PEEK, and isEmpty, without specifying how the stack is stored.
• The array-based implementation uses an array plus a TOP index, starting at -1 for an empty stack.
• PUSH checks for overflow (TOP == MAX - 1) before writing; POP checks for underflow (TOP == -1) before reading.
• Every stack operation is O(1), since each one only ever touches the top element.
• Stacks show up wherever LIFO is the natural order: function calls, undo history, expression evaluation, and backtracking.