Stacks

Abstract Data Type

A stack is a last-in, first-out (LIFO) collection. The element most recently added (pushed) is the first one removed (popped). Operations:

Operation	Description
PUSH(S, x)	Add element $x$ to the top of the stack
POP(S)	Remove and return the top element
TOP(S) / PEEK(S)	Return the top element without removing it
IS-EMPTY(S)	Return true iff stack contains no elements

Array Implementation

Maintain an array A[1..n] of maximum capacity $n$ and a variable top that tracks the current top position. Two conventions exist:

Convention 1: top is the index of the current top element (0 means empty).

• PUSH: top = top + 1; A[top] = x
• POP: x = A[top]; top = top - 1; return x

Convention 2: top is the index of the first free slot (1 means empty).

• PUSH: A[top] = x; top = top + 1
• POP: top = top - 1; return A[top]

All operations are $\Theta(1)$. Overflow occurs when pushing onto a full stack ($\texttt{top} = n$ or $\texttt{top} = n+1$, depending on convention).

Linked List Implementation

Push adds a new node at the head; pop removes the head node. Both are $\Theta(1)$. No capacity limit (until memory exhaustion).

PUSH(S, x):
    node = new Node(value=x, next=S.head)
    S.head = node

POP(S):
    if S.head == NIL: error "empty"
    x = S.head.value
    S.head = S.head.next
    return x

Additional Operations (Challenge)

Design a stack supporting AVERAGE(S) in $\Theta(1)$:

Maintain a running sum total and count size alongside the stack. On push: total += x; size += 1. On pop: total -= popped_value; size -= 1. AVERAGE returns total / size in $\Theta(1)$.

For MIN(S) in $\Theta(1)$, maintain a second stack of minimums: on push, also push $\min(x, \text{current min})$ onto the min-stack; on pop, pop both stacks. MIN reads the top of the min-stack.

Applications

Application	How the stack is used
Function call stack	Return addresses and local variables are pushed on call, popped on return
Expression evaluation (postfix/RPN)	Push operands; on operator, pop operands, evaluate, push result
Undo functionality	Each action is pushed; undo pops and reverses
Bracket matching	Push opening brackets; on closing bracket, pop and check match
Depth-first search	Implicit via recursion, or explicit with a stack of vertices to visit

Summary

Property	Array	Linked List
PUSH	$\Theta(1)$	$\Theta(1)$
POP	$\Theta(1)$	$\Theta(1)$
TOP	$\Theta(1)$	$\Theta(1)$
IS-EMPTY	$\Theta(1)$	$\Theta(1)$
Max capacity	Fixed ($n$)	Unbounded
Space	$\Theta(n)$ pre-allocated	Proportional to number of elements
Principle	LIFO