Stacks

This lesson covers the stack — a fundamental abstract data type (ADT) that obeys the Last-In, First-Out (LIFO) rule. Stacks are among the most pervasive structures in computing: the processor uses one to manage every function call you ever make, compilers use them to evaluate expressions, and editors use them to power undo. The examiner's favourite stack task is tracing a sequence of push/pop operations and the stack pointer.

Spec Mapping

This lesson addresses AQA A-Level Computer Science (7517), section 4.2.4 (Stacks). It covers the LIFO model, the operations push, pop, peek/top, isEmpty, isFull, and size, the array-based implementation with a stack pointer, overflow and underflow conditions, and the major applications — most importantly the call stack that underlies recursion (§4.1.1) and the use of a stack in depth-first search. Wording below is original and does not reproduce AQA specification text.

---

What is a Stack?

A stack is an ordered collection of elements in which:

• Items are added (pushed) to the top of the stack.
• Items are removed (popped) from the top of the stack.
• The most recently added item is always the first to be removed — LIFO.

The classic analogy is a stack of plates: you add to the top and remove from the top; you cannot take a plate from the middle without first removing the ones above it. A stack therefore exposes only its top element — there is deliberately no random access.

flowchart TB
    TOP["TOP -> 30"]
    M["20"]
    BOTTOM["BOTTOM -> 10"]
    TOP --> M --> BOTTOM

---

Stack Operations

Operation	Description	Time complexity
push(item)	Add an item to the top of the stack	$O(1)$O(1)
pop()	Remove and return the top item	$O(1)$O(1)
peek() / top()	Read the top item without removing it	$O(1)$O(1)
isEmpty()	Test whether the stack is empty	$O(1)$O(1)
isFull()	Test whether the stack is full (array-based only)	$O(1)$O(1)
size()	Return the number of items	$O(1)$O(1)

Every core operation is $O(1)$O(1) because all activity happens at the top — there is never any traversal. This constant-time guarantee is exactly why stacks are used for performance-critical jobs such as managing the call stack.

---

The Stack Pointer

An array-based stack tracks the index of the top element with a stack pointer, conventionally initialised to -1 to denote an empty stack (no valid top index yet). The pointer is the heart of the implementation:

• push increments the pointer first, then writes the item at the new top.
• pop reads the item at the current top first, then decrements the pointer.

Getting this order right is essential and is a common source of marks (and of bugs).

---

Array-Based Stack Implementation

Pseudocode

CONSTANT MAX_SIZE = 100
DECLARE stack : ARRAY[0..MAX_SIZE-1] OF INTEGER
DECLARE top : INTEGER = -1            // -1 means empty

PROCEDURE push(item : INTEGER)
    IF top = MAX_SIZE - 1 THEN
        OUTPUT "Stack overflow"       // no room
    ELSE
        top = top + 1                 // move pointer up first
        stack[top] = item             // then store
    ENDIF
ENDPROCEDURE

FUNCTION pop() RETURNS INTEGER
    IF top = -1 THEN
        OUTPUT "Stack underflow"      // nothing to remove
        RETURN -1
    ELSE
        item = stack[top]             // read first
        top = top - 1                 // then move pointer down
        RETURN item
    ENDIF
ENDFUNCTION

FUNCTION peek() RETURNS INTEGER
    IF top = -1 THEN
        OUTPUT "Stack is empty"
        RETURN -1
    ELSE
        RETURN stack[top]             // read without moving pointer
    ENDIF
ENDFUNCTION

FUNCTION isEmpty() RETURNS BOOLEAN
    RETURN top = -1
ENDFUNCTION

Python Implementation

class Stack:
    def __init__(self, max_size: int = 100):
        self.__stack = [None] * max_size
        self.__top = -1
        self.__max_size = max_size

    def push(self, item):
        if self.__top == self.__max_size - 1:
            raise OverflowError("Stack overflow")
        self.__top += 1                 # increment pointer first
        self.__stack[self.__top] = item # then store

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack underflow")
        item = self.__stack[self.__top] # read first
        self.__top -= 1                 # then decrement
        return item

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.__stack[self.__top]

    def is_empty(self) -> bool:
        return self.__top == -1

    def is_full(self) -> bool:
        return self.__top == self.__max_size - 1

    def size(self) -> int:
        return self.__top + 1

Traced Example: A Sequence of Operations

Start with an empty stack (top = -1) and perform: push(10), push(20), push(30), pop(), push(40), peek(). The table shows top and the stack contents after each step.

Operation	top after	Stack contents (bottom → top)	Returned
push(10)	0	[10]	—
push(20)	1	[10, 20]	—
push(30)	2	[10, 20, 30]	—
pop()	1	[10, 20]	30
push(40)	2	[10, 20, 40]	—
peek()	2	[10, 20, 40]	40

Notice pop() returned 30 (the most recent push) and peek() returned 40 without changing top — the defining LIFO behaviour.

Exam Tip: When asked to trace push/pop operations, draw the stack after each step and label the top pointer. Remember the ordering: push moves the pointer up then stores; pop reads then moves the pointer down. Muddling this order is the most common error.

---

Stack Overflow and Underflow

Error	Cause
Stack overflow	Attempting to push onto a full stack (array-based, when top = MAX_SIZE - 1).
Stack underflow	Attempting to pop from an empty stack (when top = -1).

In a linked-list-based stack, overflow occurs only when the whole system runs out of heap memory, because the stack grows node-by-node rather than within a fixed array. This is the trade-off: a linked stack removes the fixed ceiling at the cost of pointer overhead. The term stack overflow is also why uncontrolled recursion crashes — each call adds a frame to the call stack until it is exhausted.

Array vs Linked Implementation of a Stack

Aspect	Array-based stack	Linked-list-based stack
Capacity	Fixed at allocation; can overflow	Grows until heap exhausted
Memory per item	One slot, no overhead	Item plus a pointer
Push / pop cost	$O(1)$O(1)	$O(1)$O(1)
Cache performance	Good (contiguous)	Poorer (scattered nodes)
Wasted memory	Possible if over-sized	None — exact fit

Both give $O(1)$O(1) push and pop; the decision is the familiar static-vs-dynamic one. Choose the array when a tight upper bound is known and performance matters; choose the linked list when the maximum depth is unpredictable and overflow must be avoided.

---

The Call Stack and Recursion

The most important application of a stack is the call stack the processor maintains for subroutine calls. Each call pushes a stack frame containing the function's parameters, local variables, and the return address (where execution resumes after the function ends). When the function returns, its frame is popped and control jumps back to the saved return address. Because frames are popped in reverse order of pushing, nested calls unwind LIFO — exactly a stack.

This is precisely why recursion works: each recursive call pushes a new frame, the base case stops the pushing, and the frames then pop one by one as each call returns its result. Infinite or excessively deep recursion exhausts the stack and raises a stack overflow error.

Traced Example: The Call Stack for factorial(3)

Consider factorial(n) defined as n * factorial(n-1) with base case factorial(0) = 1. Calling factorial(3) pushes frames as the recursion descends, then pops them as it returns. The stack (top at the right) evolves:

Event	Call stack (bottom → top)	Action
call factorial(3)	[f(3)]	needs f(2)
call factorial(2)	[f(3), f(2)]	needs f(1)
call factorial(1)	[f(3), f(2), f(1)]	needs f(0)
call factorial(0)	[f(3), f(2), f(1), f(0)]	base case → returns 1
return 1	[f(3), f(2), f(1)]	f(1) computes 1 × 1 = 1
return 1	[f(3), f(2)]	f(2) computes 2 × 1 = 2
return 2	[f(3)]	f(3) computes 3 × 2 = 6
return 6	[]	final result 6

The frames pop in the exact reverse of the order they were pushed — pure LIFO — and each frame's return address is what lets execution resume the multiplication that was waiting. If the base case were missing, the stack would grow without bound until it overflowed. This trace is the canonical way to show why recursion and stacks are inseparable, and questions frequently ask for exactly this kind of frame-by-frame diagram.

def factorial(n):
    if n == 0:           # base case stops the recursion
        return 1
    return n * factorial(n - 1)   # each call waits on the one below it

---

Applications of Stacks

Application	How the stack is used
Function call stack	Each call pushes a frame (locals + return address); returning pops it.
Recursion	Recursive calls are managed by the call stack (see above).
Undo functionality	Each action is pushed; undo pops the most recent action.
Expression evaluation	A stack evaluates postfix (Reverse Polish) expressions.
Bracket matching	Opening brackets are pushed; a closing bracket pops and checks for a match.
Backtracking / DFS	Depth-first search uses a stack to remember the path and backtrack.
Browser back button	Visited pages are pushed; back pops the most recent page.

---

Bracket Matching Example

A stack elegantly checks whether brackets are balanced: push each opener, and on each closer pop and confirm it matches the most recent opener.

def is_balanced(expression: str) -> bool:
    stack = []
    matching = {')': '(', ']': '[', '}': '{'}
    for char in expression:
        if char in '([{':
            stack.append(char)                 # push opener
        elif char in ')]}':
            if not stack or stack[-1] != matching[char]:
                return False                   # mismatch or nothing to match
            stack.pop()                        # matched: discard opener
    return len(stack) == 0                     # balanced only if stack empty

print(is_balanced("((a+b)*(c-d))"))   # True
print(is_balanced("((a+b)*(c-d)"))    # False  -- one '(' left on stack
print(is_balanced("{[()]}"))          # True

The final len(stack) == 0 test is essential: an unmatched opener leaves an item on the stack even though no closer ever failed.

Traced Example: Matching {[()]}

Processing each character of {[()]} left to right shows the stack mirroring the nesting depth:

Char	Action	Stack (bottom → top)
{	push {	[{]
[	push [	[{, []
(	push (	[{, [, (]
)	top is ( — match, pop	[{, []
]	top is [ — match, pop	[{]
}	top is { — match, pop	[]

The stack ends empty, so the brackets are balanced. The structure works because the most recently opened bracket must be the next one closed — precisely LIFO behaviour. If a closer ever fails to match the current top (e.g. {(]}), or the stack is empty when a closer arrives (e.g. )(), or any opener remains at the end (e.g. {[}), the expression is unbalanced.

---

Evaluating Postfix Expressions

Postfix notation (Reverse Polish Notation, RPN) places each operator after its operands, which removes the need for brackets and precedence rules and makes stack-based evaluation trivial.

Infix	Postfix
3 + 4	3 4 +
(3 + 4) * 2	3 4 + 2 *
5 + 3 * 2	5 3 2 * +

Algorithm

1. Read each token left to right.
2. If it is a number, push it.
3. If it is an operator, pop the top two operands, apply the operator, and push the result.
4. When the input ends, the single value left on the stack is the answer.

Trace: Evaluate 3 4 + 2 *

Token	Action	Stack (bottom → top)
3	push 3	[3]
4	push 4	[3, 4]
+	pop 4, pop 3, compute $3+4=7$3+4=7, push 7	[7]
2	push 2	[7, 2]
*	pop 2, pop 7, compute $7 \times 2 = 14$7×2=14, push 14	[14]

Result: 14.

Trace: A Non-Commutative Case 8 2 -

Order matters for subtraction and division. The second operand popped is the left operand:

Token	Action	Stack
8	push 8	[8]
2	push 2	[8, 2]
-	pop 2 (right), pop 8 (left), compute $8 - 2 = 6$8−2=6	[6]

If you subtract in pop-order ($2 - 8 = -6$2−8=−6) you get the wrong sign — a classic exam trap.

Extended Trace: Evaluate 5 1 2 + 4 * + 3 -