Understand the stack abstract data type, LIFO behaviour, the push, pop and peek operations using a stack pointer, and the use of stacks for subroutine calls and recursion.

What this dot point is asking

AQA wants you to describe a stack as an abstract data type with last-in first-out behaviour, trace the push, pop and peek operations using a stack pointer, explain overflow and underflow, and explain why the call stack is used for subroutine calls and recursion.

The stack abstract data type

The operations are push (add an item to the top and increment the pointer), pop (remove and return the top item and decrement the pointer), peek (read the top item without removing it), isEmpty and isFull. Because every operation works on the top, all of them are constant time $O(1)$, which is part of why stacks are so widely used.

PUSH(item):
  IF NOT isFull THEN
    top = top + 1
    stack[top] = item

POP():
  IF NOT isEmpty THEN
    item = stack[top]
    top = top - 1
    RETURN item

Overflow and underflow

The call stack, calls and recursion

Stacks appear in many other places once you recognise the pattern: the undo feature in an editor pushes each action so the most recent can be undone first; a web browser's back button pops the most recently visited page; and depth-first traversal of a graph uses a stack (or the call stack via recursion) to remember where to backtrack to. In every case the defining feature is that the item you most recently set aside is the one you need back first.

A stack can be implemented either statically, in a fixed-size array with an integer stack pointer as shown above, or dynamically, as a linked list where pushing adds a node at the head and popping removes it. The array version is simple and fast but has a fixed capacity, so it can overflow; the linked version grows as needed but uses extra memory for pointers. Either way the abstract behaviour (LIFO, with push, pop and peek) is identical, which is exactly what it means to call a stack an abstract data type: the specification describes what it does, and a programmer chooses how to build it.

Expression evaluation is a classic exam application. To evaluate a reverse Polish (postfix) expression, operands are pushed onto a stack; when an operator is read, the top two operands are popped, the operation is applied, and the result is pushed back. This works precisely because the most recently seen operands are the ones the operator needs, matching the LIFO order, and it is the reason compilers and calculators convert infix expressions to postfix and evaluate them with a stack.