Stacks

A stack is a last-in, first-out (LIFO) collection: the only item you can ever see or remove is the one most recently added. That deliberate restriction — access at one end only — is not a limitation but the source of its power. It makes stacks the natural model for anything that must be undone in reverse order, from nested function calls to backtracking searches.

---

Spec Mapping

This lesson addresses the H446 1.4.2 Data Structures content on stacks:

• Define a stack as a LIFO abstract data type and state its operations: push, pop, peek/top, isEmpty, isFull, size.
• Implement a stack using both a static array with a top pointer and a dynamic linked list, and trace sequences of operations.
• Recognise and handle stack overflow and stack underflow error conditions.
• Explain real applications — the call stack for procedure/recursion management, expression evaluation (postfix/RPN), bracket matching and backtracking — and connect the stack to the fetch-decode-execute and recursion topics.

(Phrasing here paraphrases the specification content; it is not a verbatim quote.)

---

What is a Stack?

A stack is a linear abstract data type that obeys the LIFO principle: the last item pushed on is the first popped off. All activity happens at one end, called the top; the other end, the base, is never touched directly. Think of a spring-loaded stack of cafeteria plates — you add and take only from the top, so the plate you put down most recently is the one you pick up first.

Because every operation acts on the top alone, and the top is always known, the four core operations run in constant time regardless of how many items the stack holds. That $O(1)$O(1) guarantee is the property to remember and to justify in the exam.

It is worth being precise about the word abstract here. A stack is an abstract data type (ADT): it is defined by its behaviour — the LIFO contract and the set of operations — not by any particular implementation. That separation matters, because the very same stack behaviour can be realised in completely different ways (an array with a top pointer, or a linked list with a head pointer) and a program that only ever calls push, pop and peek cannot tell which is underneath. This is the principle of abstraction: the interface (what operations exist and how they behave) is fixed and visible, while the implementation (how the data is stored) is hidden and interchangeable. Whenever a question asks why a stack is an ADT, this interface-versus-implementation distinction is the answer the marks reward — and it is exactly why this lesson presents two different implementations of the identical operation set below.

Real-world analogies

• A pile of plates — add to the top, take from the top.
• A browser's Back button — returns to the most recently visited page first.
• An undo feature — reverses the most recent action first.

---

Stack Operations

Operation	Description	Complexity
push(item)	Add an item to the top	$O(1)$O(1)
pop()	Remove and return the top item	$O(1)$O(1)
peek() / top()	Return the top item without removing it	$O(1)$O(1)
isEmpty()	True if the stack holds no items	$O(1)$O(1)
isFull()	True if a fixed-size (array) stack is full	$O(1)$O(1)
size()	Number of items currently held	$O(1)$O(1)

The distinction between pop and peek is a reliable mark: pop removes and returns the top; peek reads it and leaves the stack unchanged. Mixing them up is one of the commonest slips in trace questions.

Notice that every operation in the table is $O(1)$O(1) — and that this is a direct consequence of the LIFO restriction, not a happy accident. Because the only accessible item is the top, no operation ever has to search for a position or shuffle other elements aside; each acts on a single, already-known location and does a fixed amount of work. Contrast this with a general list, where inserting or deleting in the middle is $O(n)$O(n) precisely because other elements must move. The lesson — and a point worth making in an evaluation answer — is that deliberately restricting what a structure can do is often what makes it fast: a stack trades away random access in exchange for guaranteed constant-time ends.

---

Array-Based Implementation

The classic implementation is "an array plus an integer top pointer" that holds the index of the current top element. A value of $-1$−1 conventionally marks an empty stack (no valid index yet). The array supplies the storage; the single integer top is all the extra state a stack needs, because LIFO means we only ever care about one position. This is a beautiful illustration of how a restrictive ADT can be implemented very cheaply: a general-purpose list needs to track far more, but a stack — precisely because it forbids middle access — gets away with one index. Each push moves top up by one and writes; each pop reads and moves top down by one; nothing else in the array is ever disturbed, which is the whole reason both are $O(1)$O(1).

Pseudocode (OCR-style)

const MAX_SIZE = 10
array stack[MAX_SIZE]
top = -1                       // -1 means empty

function push(item)
    if top == MAX_SIZE - 1 then
        print("Stack Overflow") // no room
    else
        top = top + 1           // move the pointer up first
        stack[top] = item       // then store
    endif
endfunction

function pop()
    if top == -1 then
        print("Stack Underflow")
        return null
    else
        item = stack[top]       // read before moving
        top = top - 1           // logically discard the top
        return item
    endif
endfunction

function peek()
    if top == -1 then
        return null
    else
        return stack[top]       // read, do not move the pointer
    endif
endfunction

function isEmpty()
    return top == -1
endfunction

The order of the two lines inside push and pop matters. On push you increment top then write, so top always names a valid item; on pop you read then decrement, so you never read a slot that has just been logically removed. Note also that pop does not literally erase the old value — it simply moves top below it, so the slot is "stale" and will be overwritten by the next push. That is why a stack's pop is $O(1)$O(1): no shifting, no clearing, just one pointer change.

Python implementation

class ArrayStack:
    def __init__(self, max_size):
        self.stack = [None] * max_size
        self.max_size = max_size
        self.top = -1

    def push(self, item):
        if self.top == self.max_size - 1:
            raise OverflowError("Stack Overflow")
        self.top += 1
        self.stack[self.top] = item

    def pop(self):
        if self.top == -1:
            raise IndexError("Stack Underflow")
        item = self.stack[self.top]
        self.top -= 1
        return item

    def peek(self):
        if self.top == -1:
            return None
        return self.stack[self.top]

    def is_empty(self):
        return self.top == -1

    def size(self):
        return self.top + 1

---

Pointer-Based (Linked List) Implementation

A stack can instead be built on a linked list, with the top of the stack = the head of the list. This is a perfect fit, and seeing why cements the link to the previous lesson. Pushing a value is an insert-at-front — create a node, point it at the old top, make it the new top — which is $O(1)$O(1) on a linked list. Popping is a remove-from-front — read the head's data, move top to the next node — again $O(1)$O(1). The two operations a stack needs are precisely the two operations a linked list does most cheaply, which is no coincidence: a stack is "a linked list with all access forced to one end". The pay-off over the array version is that the stack grows and shrinks dynamically and can never overflow except by exhausting the whole heap; the cost is one pointer of memory per item and slightly slower access due to scattered nodes.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedStack:
    def __init__(self):
        self.top = None          # head of the list = top of the stack
        self._size = 0

    def push(self, item):
        new_node = Node(item)
        new_node.next = self.top # point at old top first
        self.top = new_node      # new node becomes the top
        self._size += 1

    def pop(self):
        if self.top is None:
            raise IndexError("Stack Underflow")
        item = self.top.data
        self.top = self.top.next # unlink the old top
        self._size -= 1
        return item

    def peek(self):
        if self.top is None:
            return None
        return self.top.data

    def is_empty(self):
        return self.top is None

Comparing the two implementations

Feature	Array-based	Linked-list-based
Size	Fixed — can overflow	Dynamic — only the heap limits it
Memory	One pre-allocated block (may be under-filled)	One node per item + a pointer each
Speed (constant factor)	Faster — contiguous, cache-friendly	Slower — scattered nodes
Complexity of code	Simpler (one array + index)	More pointer book-keeping
push / pop order	$O(1)$O(1)	$O(1)$O(1)

Both give $O(1)$O(1) push and pop; the choice is the familiar static-vs-dynamic trade-off from the arrays and linked-lists lessons. Use the array when the maximum depth is known and predictable (so overflow can be designed out) and you want top speed; use the linked list when the depth is unbounded or wildly variable.

A subtle but examinable point is that the two implementations have the same asymptotic complexity yet different practical behaviour. The array version touches contiguous memory, so it is cache-friendly and typically faster by a constant factor; it also has zero per-item overhead. Its weaknesses are the fixed ceiling (risk of overflow) and possible wasted space if the array is allocated large but rarely filled. The linked version never wastes capacity and never overflows short of the whole heap, but pays one pointer per item and suffers cache misses as it hops between scattered nodes. Big-O treats both as $O(1)$O(1) because it ignores these constant factors and hardware effects — which is exactly why a good evaluation answer goes beyond the order and weighs predictability of depth, memory budget and raw speed. There is, as ever, no universally correct choice; there is only the choice that best fits the workload the question describes.

---

Worked Example: Tracing Stack Operations

Trace tables are a near-certain exam task. Start from an empty array-based stack (top = -1) and show the contents (base → top), the top pointer, and any value returned.

Operation	Contents (base → top)	top	Returns
push(10)	[10]	0	—
push(20)	[10, 20]	1	—
push(30)	[10, 20, 30]	2	—
peek()	[10, 20, 30]	2	30
pop()	[10, 20]	1	30
pop()	[10]	0	20
isEmpty()	[10]	0	false
pop()	[]	-1	10
isEmpty()	[]	-1	true

Notice that peek returned 30 but left top at 2 — the stack was unchanged — whereas the next pop returned 30 and lowered top to 1. That contrast is exactly what trace-table marks test. Notice too the final pop() returned 10 and set top back to $-1$−1, the empty sentinel, after which isEmpty() correctly reports true. Walking a trace right to the empty state is good discipline because it confirms your pointer arithmetic closes the loop cleanly.

If the question used a linked-list stack instead, the trace would track the head pointer rather than a numeric top index, but the returned values and the order of removal would be identical — a useful check that the two implementations really do realise the same ADT. The only visible difference is bookkeeping (a head reference vs an integer index); the LIFO behaviour the marks reward is the same either way.

Exam Tip: In a trace table, always show the top pointer value explicitly, not just the contents. A correct contents column with a wrong/absent pointer column routinely loses marks.

---

Applications of Stacks

1. The call stack (procedure and recursion management)

When a subroutine is called, a stack frame — the return address, parameters and local variables — is pushed onto the call stack; when the routine returns, its frame is popped, restoring the caller. LIFO is exactly right because the most recently called routine is always the first to finish.

flowchart TB
    M["main() frame"] --> A["functionA() frame"] --> B["functionB() frame (TOP)"]

Here main called functionA, which called functionB. functionB is on top and must return first (pop), then functionA, then control returns to main. The return address stored in each frame is what lets execution resume at exactly the right instruction in the caller once a routine finishes — the stack remembers where to go back to even through arbitrarily deep nesting.

This is also precisely how recursion works. Each recursive call pushes a fresh frame holding that call's own parameters and local variables, so each "copy" of the function has its own private state; the calls then unwind in reverse order as base cases are reached and frames are popped. Consider factorial(3): it pushes frames for factorial(3), factorial(2), factorial(1) and factorial(0); the base case factorial(0)=1 returns first (pop), then factorial(1), then factorial(2), then factorial(3) — strict LIFO. This is exactly why uncontrolled recursion causes a literal stack overflow: a missing or unreachable base case pushes frame after frame without ever popping, until the call stack's memory is exhausted. Understanding this connects the data structure (stack) to the programming technique (recursion) and to the hardware (the stack pointer register), and is a frequent synoptic exam theme.

2. Undo operations