Abstract data types and stacks

ADTs, static and dynamic structures, and a stack with a top pointer: an undo stack for the robot's moves.

A3.2Data structuresA level20 min

When you press undo, the last thing you did is the first thing to be taken back. That rule, last in first out, is a stack, and it is the first abstract data type in this module. In this lesson BugBot keeps a stack of its moves, so it can undo them one at a time and drive home.

Abstract data types

An abstract data type (ADT) is a data type described only by the operations you can do on it and what those operations do, not by how it is stored. A stack is "something you can push onto, pop from, peek at, and ask whether it is empty or full". Whether it is built from an array or from linked nodes is hidden from the program that uses it.

That separation is information hiding: code that uses the stack only calls its operations, so the storage can be changed later without breaking anything. The ADTs on the A level specifications are stacks, queues, lists, linked lists, hash tables, dictionaries, graphs, trees and vectors.

Static and dynamic structures

Each ADT can be built on a static or a dynamic data structure.

	Static (for example an array)	Dynamic (for example a linked list)
Size	fixed when it is created	grows and shrinks while the program runs
Memory	set aside in advance, may be wasted if not all used	taken from the heap as needed, so none is wasted on empty space
Full?	can become full (overflow) even if memory is free	only full when the heap runs out
Access	direct: any element by index, same time for all	usually by following pointers from the start
Overhead	none beyond the data	each item also stores one or more pointers

A static structure suits data whose maximum size is known, such as the 64 readings in a depth grid. A dynamic structure suits data whose size cannot be predicted, such as messages arriving over the radio.

The stack

A stack is a last in, first out (LIFO) structure. Items are added and removed at the same end, the top. Its operations:

Operation	What it does
`push(item)`	add an item to the top
`pop()`	remove the top item and return it
`peek()` (or `top()`)	return the top item without removing it
`is_empty()`	true if there are no items
`is_full()`	true if there is no room for another item (static stacks only)

A static stack is an array plus one integer, the top pointer, holding the index of the top item. With indexes from 0, an empty stack has top = -1.

Push: check the stack is not full, add 1 to top, then store the item at stack[top]. Pushing onto a full stack is stack overflow.
Pop: check the stack is not empty, read stack[top], then subtract 1 from top. Popping an empty stack is stack underflow.

Popping does not wipe the element. The old value stays in the array, but it is above the top pointer, so it is no longer part of the stack and will be overwritten by the next push.

Two moves pushed: the top pointer holds 1, the index of the most recent move

Tracing a stack

A stack of size 4 starts empty. Follow the top pointer through five operations:

Operation	top afterwards	stack[0]	stack[1]	Returned
(start)	-1
push forward 30	0	forward 30
push right 25	1	forward 30	right 25
pop	0	forward 30	right 25	right 25
push left 15	1	forward 30	left 15
peek	1	forward 30	left 15	left 15

After the pop, right 25 is still in stack[1], but it is not in the stack because top is 0. The next push overwrites it.

Undoing moves

Here the robot drives a short route, pushing each move. To undo, it pops the moves and does the opposite of each. Python's own list has append and pop, which make it a ready-made dynamic stack:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

OPPOSITE = {"forward": "backward", "backward": "forward", "left": "right", "right": "left"}

def do(move, cm):
    if move == "forward":
        forward(50, distance=cm)
    elif move == "backward":
        backward(50, distance=cm)
    elif move == "left":
        left(50, distance=cm)
    else:
        right(50, distance=cm)

undo = []                            # a Python list used as a dynamic stack
for move, cm in [("forward", 25), ("right", 20), ("forward", 15)]:
    do(move, cm)
    undo.append((move, cm))          # push

print("at", position())
while len(undo) > 0:
    move, cm = undo.pop()            # pop: the last move comes off first
    print("undoing", move, cm)
    do(OPPOSITE[move], cm)
print("back at", position())

Run this in the simulator

Because the last move comes off first, the reverse route retraces the path exactly. A queue would undo the moves in the wrong order and the robot would end up somewhere else.

Where stacks are used

Undo in editors, and the back button in a browser.
The call stack: each subroutine call pushes a stack frame holding the return address, parameters and local variables, popped when the subroutine returns (lesson A2 looks at this in detail).
Reversing a sequence, and backtracking out of a dead end in a maze.
Evaluating Reverse Polish expressions, and depth-first traversal of a graph (module A4).

In the exam

Questions ask you to explain LIFO, to describe push and pop including the checks for full and empty, to show a stack's contents and pointer after a sequence of operations, and to write push or pop in pseudocode. Say what happens to the pointer, and in which order: with top holding the index of the top item, push moves the pointer before storing, and pop reads the item before moving the pointer. Some papers use a pointer to the next free slot instead, which swaps that order, so read the question's definition.

OCR A level 1.4.2

OCR expects you to know how to create, traverse, add data to and remove data from a stack. In the exam reference language:

procedure push(item)
    if top == MAX - 1 then
        print("Stack overflow")
    else
        top = top + 1
        stack[top] = item
    endif
endprocedure

AQA A level 4.2.1.4 4.2.3.1

AQA asks you to be familiar with the concept and uses of stacks, to distinguish static from dynamic structures and compare their advantages and disadvantages, and to apply push, pop, peek or top, test for empty stack and test for stack full. In pseudo-code:

SUBROUTINE Pop()
    IF Top = -1 THEN
        OUTPUT 'Stack underflow'
    ELSE
        Item ← Stack[Top]
        Top ← Top - 1
        RETURN Item
    ENDIF
ENDSUBROUTINE

Eduqas A level 1.1

Eduqas asks you to describe and manipulate stacks, and to explain the difference between static and dynamic data structures.

Task: undo back home

Build a static stack the way exam pseudocode does: an array stack of SIZE elements (here 4) and a top pointer that starts at -1, both at the top level of the program. Do not use the list's own append or pop.

Write push(item): if the stack is full, print overflow and return False; otherwise add the item and return True.
Write pop(): if the stack is empty, print underflow and return None; otherwise remove the top item and return it.

Both change top, so each needs global top as its first line. Then:

For each (move, cm) in route, push the tuple, and make the move with do(move, cm) only if the push worked. The fifth move will not fit, so it is never made.
Undo: while the stack is not empty, pop a move, print undo <move> <cm> (for example undo left 15), and make the opposite move with do(OPPOSITE[move], cm).
Call pop() once more, so the empty stack prints underflow.

The robot should finish within 6 cm of where it started.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

OPPOSITE = {"forward": "backward", "backward": "forward", "left": "right", "right": "left"}

def do(move, cm):
    """move is "forward", "backward", "left" or "right"; cm is how far."""
    if move == "forward":
        forward(50, distance=cm)
    elif move == "backward":
        backward(50, distance=cm)
    elif move == "left":
        left(50, distance=cm)
    elif move == "right":
        right(50, distance=cm)

SIZE = 4
stack = [None] * SIZE
top = -1

def push(item):
    global top

def pop():
    global top

route = [("forward", 30), ("right", 25), ("forward", 20), ("left", 15), ("forward", 10)]

Challenges

Add peek(), is_empty() and is_full(), and use them so push and pop read more clearly.
Write a function that uses a stack to reverse a string, one character at a time.
Explain why a stack built on a linked list never overflows until memory runs out, but pays for it on every push.