Preview

The whole resource, exactly as a class sees it. Answers and marking are held back.

Stacks

OCR H446 references: 1.4.1(a), 1.4.1(b) and 2.2.1(f)

Some tasks must be revisited in the reverse order from which they arrived. A game may undo the player's latest move first, a browser may return to the most recently visited page, and a program must finish the most recently started function call before returning to an earlier one.

A stack models this pattern. In this worksheet, you will first build a clear mental model of the operations, then trace and implement a fixed-capacity stack in Python.

By the end, you should be able to:

explain LIFO, push, pop and peek
detect overflow and underflow
interpret the pointer convention stated in a question
implement and test a stack without using advanced Python

A structure for reversing the order of work

Imagine a pile of equipment cases. You can place a new case on top, and you can remove the top case, but reaching a lower case first would require moving the cases above it. A stack uses the same access rule.

The last item added is the first item removed. This is called last in, first out, or LIFO.

The three main operations

push(item) adds an item to the top of the stack.
pop() removes and returns the top item.
peek() returns the top item without removing it.

If the stack contains ["menu", "settings", "audio"], then "audio" is at the top. A pop returns "audio", leaving "settings" as the new top.

Error conditions

A stack implemented with a fixed number of positions cannot grow forever.

Overflow occurs when the program attempts to push onto a full stack.
Underflow occurs when the program attempts to pop or peek from an empty stack.

A robust implementation checks the condition before reading or writing the array.

Read the pointer convention before tracing

Questions may define the stack pointer in different ways:

It may identify the current top item.
It may identify the next free position.

Both conventions are valid. The boundary tests and pointer updates differ, so never assume which one is being used.

This worksheet uses next free position. An empty stack has pointer = 0. If three items occupy indices 0, 1 and 2, the pointer is 3.

OCR-style pseudocode

procedure push(value)
    if pointer = length(stack) then
        return false
    endif
    stack[pointer] = value
    pointer = pointer + 1
    return true
endprocedure

function pop()
    if pointer = 0 then
        return null
    endif
    pointer = pointer - 1
    return stack[pointer]
endfunction

For a push, the value is stored before the pointer advances. For a pop, the pointer moves back before the value is read.

Python equivalent

def push(value):
    global pointer
    if pointer == len(stack):
        return False
    stack[pointer] = value
    pointer += 1
    return True

In programming answers, use Python. Use the pseudocode to recognise the intended operations and pointer behaviour.

Worked example

stack = [None, None, None, None]
pointer = 0  # next free position


def push(value):
    global pointer
    if pointer == len(stack):
        return False
    stack[pointer] = value
    pointer += 1
    return True


def pop():
    global pointer
    if pointer == 0:
        return None
    pointer -= 1
    value = stack[pointer]
    stack[pointer] = None
    return value


push("A")
push("B")
print(pop())
print(stack, pointer)

Fill in the blanks

Ordering rule used by a stack: ______. Operation that adds a top item: ______. Operation that removes the top item: ______. Attempt to add to a full fixed stack: ______. Attempt to remove from an empty stack: ______.

LIFO
push
pop
overflow
underflow

Multiple choice1 mark

A stack uses a pointer to the next free position. It contains three items. What value should the pointer hold?

A2, because array positions start at zero
B3, because positions 0, 1 and 2 are occupied
C0, because the bottom item is at position zero
D4, because one spare position must remain

Checkpoint and task guidance

For each trace, record both the logical contents and the pointer after every operation. Do not rely on a picture alone.

Guided trace

Run the supplied program. Predict each printed value before changing the operations. Then try one underflow and one overflow.

Independent reversal task

You will use a Python list as a stack:

Push each character with append().
Pop characters until the stack is empty.
Join the popped characters.
Store the result in reversed_word.

The required result is "LEVEL" for "LEVEL" and your function must also work for an empty string.

Starter code

items = []

items.append(4)
items.append(7)
items.append(9)

print(items.pop())  # Predict before running.
print(items[-1])    # This peeks without removing.
print(items)

# Add operations that empty the stack.
# Before another pop, explain why it would cause underflow.
# Then create a capacity variable and guard pushes to demonstrate overflow.

Coding task3 marks

def reverse_with_stack(text):
    stack = []

    # Push every character onto stack.
    # Then pop until empty and build the reversed result.

    return ""


reversed_word = reverse_with_stack("LEVEL")

Written answer3 marks

Explain why a stack is suitable for an undo feature. Include the ordering rule and what a push and a pop would represent.

Apply each stack term to the scenario rather than only defining it.

Students type their answer here.

Independent task: fixed-capacity Stack class

Implement a stack whose pointer identifies the next free position. The internal list is fixed at the requested capacity.

push(value) returns False without changing the stack when it is full.
Otherwise it stores the value, advances the pointer and returns True.
pop() returns None when empty.
Otherwise it moves the pointer back and returns the removed value.

The supplied test operations deliberately check normal use, overflow and underflow. Complete the class; do not remove the test code.

Coding task4 marks

class Stack:
    def __init__(self, capacity):
        self.items = [None] * capacity
        self.pointer = 0

    def push(self, value):
        pass

    def pop(self):
        pass


test_stack = Stack(2)
first_push = test_stack.push(5)
second_push = test_stack.push(8)
overflow_result = test_stack.push(13)
first_pop = test_stack.pop()
second_pop = test_stack.pop()
underflow_result = test_stack.pop()

Written answer3 marks

Define stack overflow and underflow. Then state why you must check the pointer convention given in an exam question.

Give brief, precise definitions and refer to what the pointer identifies.

Students type their answer here.