Stacks — AQA A-Level Computer Science

A stack is a Last In, First Out (LIFO) abstract data type where elements are added and removed from the same end, known as the top. In AQA A-Level Computer Science, stacks are implemented using static arrays or dynamic linked lists and underpin critical operations such as subroutine call stacks, expression evaluation, and depth-first graph traversals.

Stacks explained

This statement asks you to do two things with stack operations: describe what each operation does, and apply it to a concrete sequence of actions.

Read the full explanation

A stack is a last-in, first-out (LIFO) structure, so the most recently added item is the first one removed. To describe an operation, state its effect on the stack and what it returns. To apply it, trace a sequence step by step, keeping a record of the stack contents after each step. For example, starting from an empty stack, push A, push B, then pop returns B and leaves A on the stack. Being able to both explain the rule and track the state accurately is what the statement is testing. The operations listed in the statement are specified separately, so this heading sets the expectation that you can work with them rather than only define them.

Your focus

Be able to describe and apply the following operations:

Which command word is this?

State the key characteristics or steps of a process clearly (e.g. describe how an item is pushed onto a stack) without needing detailed evaluation or justification.

Stacks exam tips

Topic Overview

A stack is a fundamental abstract data type characterised by the Last In, First Out (LIFO) protocol. All insertions (push) and deletions (pop) occur at a single access point termed the top of the stack. Stacks can be realised statically via fixed-size arrays or dynamically using linked lists.

Within the broader AQA A-Level specification, stacks are essential for understanding processor architecture and algorithm design. They underpin the call stack used by processors to handle return addresses and local variables during subroutine calls, provide the operational basis for Reverse Polish Notation (RPN) evaluation, and facilitate backtracking algorithms such as depth-first searches.

Key Concepts

→LIFO Principle: The most recently inserted element is always the first one to be removed.
→Core Primitive Operations: 'push' (adds an element to the top), 'pop' (removes and returns the top element), and 'peek' or 'top' (returns the top element without removing it).
→Boundary Conditions: 'Stack Overflow' occurs when attempting to push onto a full static stack; 'Stack Underflow' occurs when attempting to pop from an empty stack.
→Static vs Dynamic Implementation: Static implementations use fixed contiguous memory with a pointer index, while dynamic implementations use nodes with memory pointers, avoiding fixed size limits at the expense of memory overhead.

Marking Points

Explains that a stack operates on a last-in, first-out basis.
Describes the effect of each operation on the contents of the stack.
Traces a given sequence of operations and states the resulting stack contents accurately.
Identifies the value returned by an operation that returns data, such as pop or peek.
Recognises the state of the stack when an operation is attempted on an empty stack.

Examiner Tips

💡When asked to trace operations, draw the stack as a column and update it after every step.
💡Read the question for whether it asks you to describe, apply, or both, and answer each part.
💡Check your final stack state by reading it from top to bottom to confirm the last item added is at the top.
💡When tracing call stacks during recursive subroutine questions, draw each stack frame containing local variables, parameters, and return addresses to avoid losing marks on execution order.
💡Check your array pointer arithmetic: if 'top' starts at -1, increment before assigning during push ('top = top + 1' then 'stack[top] = item'); if popping, retrieve first, then decrement ('item = stack[top]' then 'top = top - 1').
💡In free-response pseudocode, always check 'isEmpty()' or 'isFull()' explicitly before executing pointer movements to capture structural defensive programming marks.

Common Mistakes

Treats a stack as first-in, first-out, so removes the oldest item instead of the newest. Correction: the most recently pushed item is always removed first.
Forgets to update the stack contents after each operation when tracing a sequence. Correction: write the stack state after every single step.
Confuses what an operation returns with what it changes. Correction: pop both removes and returns the top item, whereas peek returns the top item without removing it.
Students often assume that popping an element erases its value from physical memory; in an array implementation, the value remains stored at that index until overwritten, but it is rendered inaccessible because the top pointer has decremented.
Students confuse 0-indexed arrays with 1-indexed stacks, often claiming an empty 0-indexed stack has 'top = 0', which actually indicates a stack holding one item at index 0.
Students conflate stacks with queues, erroneously applying First In, First Out (FIFO) logic to stack operations.

Revision Plan

1Day 1-3: Master basic mechanics by tracing array-based stack operations, drawing state diagrams after multiple push, pop, and peek commands.
2Day 4-6: Write pseudocode implementations for push, pop, peek, isEmpty, and isFull with robust underflow and overflow validation.
3Day 7-9: Study practical applications, specifically the execution of call stacks in recursive functions and converting infix expressions to postfix (RPN).
4Day 10-14: Solve past AQA exam questions focusing on code completion, stack traces, and comparative evaluation between static and dynamic representations.

Exam Question Types

📋Trace Table Questions: Stepping through code to show the sequential contents of a stack array and the numerical index of the top pointer.
📋Algorithm Writing (Pseudocode): Writing complete push/pop procedures or functions that include conditional branch checks for underflow and overflow.
📋Application Analysis: Explaining how the stack data structure is used by the operating system or CPU to manage subroutine calls and recursion.

Command Word Expectations (AQA)

Describe

State the key characteristics or steps of a process clearly (e.g. describe how an item is pushed onto a stack) without needing detailed evaluation or justification.

Explain

Provide reasons why or how a mechanism operates, connecting cause and effect (e.g. explain why a stack overflow occurs in terms of memory allocation and pointer boundaries).

Write an algorithm

Produce logically sound, syntactically coherent pseudocode or program code that solves the defined problem, handling all edge cases such as empty or full states.

How Students Lose Marks (Examiner Pitfalls)

Pitfall: Confusing the condition for stack overflow when using 0-based indexing versus 1-based indexing in array implementations.

❌ Weak Answer (Loses Marks):The stack is full when the top pointer equals the maximum size of the array.

Example improved answer:For a 0-indexed array of size 'maxSize', stack overflow occurs when 'topPointer == maxSize - 1'. Attempting to push when this condition evaluates to True will cause an overflow error.

Examiner Tip: Always explicitly state your array indexing convention (e.g. 0-indexed with top initialised to -1, or 1-indexed with top initialised to 0) before writing push or pop algorithms.

Pitfall: Omitting the stack underflow check prior to decrementing the top pointer during a pop operation.

❌ Weak Answer (Loses Marks):function pop(): item = stack[top] top = top - 1 return item

Example improved answer:function pop(): if top < 0 then report 'Stack Underflow Error' return null else item = stack[top] top = top - 1 return item endif endfunction

Examiner Tip: Algorithms in exam papers require validation checks. You must check for underflow before popping and overflow before pushing to achieve full marks.

Step-by-Step Worked Solutions

Question: An array 's' of size 5 (indices 0 to 4) implements a stack. A variable 'top' tracks the index of the top item and is initialised to -1. Trace the contents of 's' and the value of 'top' after the following sequence of operations: push('A'), push('B'), pop(), push('C'), push('D'), push('E'), pop(), push('F'). State whether stack overflow or underflow occurs at any point.

1.Step 1: Initial state is top = -1, array is empty [ , , , , ].
2.Step 2: push('A') -> top increments to 0; s[0] = 'A'. Array: ['A', , , , ].
3.Step 3: push('B') -> top increments to 1; s[1] = 'B'. Array: ['A', 'B', , , ].
4.Step 4: pop() -> returns s[1] ('B'); top decrements to 0. Array conceptually: ['A', , , , ].
5.Step 5: push('C') -> top increments to 1; s[1] = 'C'. Array: ['A', 'C', , , ].
6.Step 6: push('D') -> top increments to 2; s[2] = 'D'. Array: ['A', 'C', 'D', , ].
7.Step 7: push('E') -> top increments to 3; s[3] = 'E'. Array: ['A', 'C', 'D', 'E', ].
8.Step 8: pop() -> returns s[3] ('E'); top decrements to 2. Array: ['A', 'C', 'D', , ].
9.Step 9: push('F') -> top increments to 3; s[3] = 'F'. Array: ['A', 'C', 'D', 'F', ].
10.Step 10: Check boundaries: 'top' ranged between -1 and 3 throughout. The maximum index is 4, so no overflow occurred. 'top' never decremented below -1, so no underflow occurred.

Final Answer: Final stack contents from index 0 to 3: ['A', 'C', 'D', 'F']. Final value of top = 3. Neither stack overflow nor stack underflow occurred.

Question: Write an algorithm in pseudocode for the 'push' operation on a statically sized stack named 'stackArray' of capacity 'MAX_SIZE', using a pointer variable 'topPointer' initialised to -1. The algorithm should take 'newItem' as a parameter and output an error message if the stack is full.

1.Step 1: Identify boundary condition for overflow in a 0-indexed array: topPointer == MAX_SIZE - 1.
2.Step 2: Construct selection statement to handle overflow condition.
3.Step 3: If not full, increment 'topPointer' by 1.
4.Step 4: Assign 'newItem' to 'stackArray[topPointer]'.

Final Answer: procedure push(newItem): if topPointer == MAX_SIZE - 1 then print('Error: Stack Overflow') else topPointer = topPointer + 1 stackArray[topPointer] = newItem endif endprocedure

Active Recall Memory Test

What data access protocol defines a stack?

Key Fact: Last In, First Out (LIFO).

What error condition arises when attempting to pop from an empty stack?

Key Fact: Stack Underflow.

In a 0-indexed array implementation of size N, what value of top indicates that the stack is full?

Key Fact: top == N - 1.

What three items are typically stored in a stack frame on the call stack during a subroutine call?

Key Fact: Return address, subroutine parameters, and local variables.

Frequently Asked Questions

What is the difference between a static stack and a dynamic stack?

A static stack is implemented using a fixed-size array allocated in contiguous memory at compile time. Its size cannot change during execution, which can lead to stack overflow if capacity is exceeded, though it has minimal memory overhead. A dynamic stack is built using linked list nodes allocated on the heap at runtime; it grows and shrinks as required, avoiding fixed overflow limits, but requires extra memory to store pointers.

Why does a subroutine call stack use a stack rather than a queue?

Subroutine calls follow a nested, Last In, First Out execution pattern. When function A calls function B, and function B calls function C, function C must complete and return before function B can resume, and B must finish before A can resume. A stack structure perfectly matches this requirement by placing each new activation record on top and popping it when the function terminates to retrieve the correct return address.

What is the time complexity of push and pop operations on a stack?

Both push and pop operations run in O(1) constant time. Because additions and removals always occur at the top of the stack, the algorithm only needs to update a pointer and access a single memory location. No element shifting or sequential traversal is required, regardless of how many elements are currently stored.

What causes a stack overflow error during recursion?

A stack overflow occurs during recursion when a function calls itself repeatedly without reaching a valid base case, or when the recursion depth is too large for the allocated call stack space. Each recursive call allocates a new stack frame containing return addresses and local variables. Eventually, the contiguous memory reserved for the call stack is exhausted, causing the operating system or runtime environment to throw an overflow exception.

Stacks explained

Your focus

Which command word is this?

Stacks exam tips

More AQA A-Level Computer Science topics

Cookies on MasteryMind