Cambridge Syllabus Notes

19.1 Algorithms – Understanding and Using Abstract Data Types (ADT)

1. What Is an Abstract Data Type?

An Abstract Data Type (ADT) defines a data structure solely by its behaviour – the operations that can be performed on it and the mathematical properties of those operations. The concrete way the data are stored in memory is deliberately hidden (information hiding).

2. Key Characteristics of an ADT

Encapsulation – only the operations listed in the specification are visible to the user.
Formal Specification – each operation is described by its pre‑conditions, post‑conditions and (usually) its time‑complexity.
Implementation Independence – the same ADT can be realised with different concrete structures (array, linked list, tree, …) without changing the client code.

3. Formal Specification of an ADT

When an ADT is specified we give:

Signature – name of the ADT and the type of each operation.
Pre‑conditions – what must be true before the operation is invoked.
Post‑conditions – the effect on the abstract state after the operation.
Complexity – expressed in Big‑O notation.

Example: Stack ADT (Cambridge style)

ADT Stack
    Operations:
        push(x)      – pre: true;
                      post: top = x, size = size + 1;               O(1)

        pop()        – pre: !isEmpty();
                      post: returns former top, size = size – 1;    O(1)

        top()        – pre: !isEmpty();
                      post: returns current top;                    O(1)

        isEmpty()    – pre: true;
                      post: returns true iff size = 0;              O(1)

    Abstract State:
        sequence S = ⟨⟩   (initially empty)

4. Common ADTs in the Cambridge A‑Level Syllabus

ADT	Typical Operations (signature)	Typical Implementations
Stack	`push(x)` – insert element `x` on the top `pop()` – remove and return the top element `top()` – view the top element without removing it `isEmpty()` – true iff the stack contains no elements	Fixed‑size array, dynamic array, singly linked list
Queue	`enqueue(x)` – insert element `x` at the rear `dequeue()` – remove and return the front element `front()` – view the front element without removing it `isEmpty()`	Circular array, doubly linked list
List (Sequence)	`insert(i, x)` – insert `x` at position `i` `delete(i)` – delete the element at position `i` `get(i)` – retrieve the element at position `i` `size()` – number of elements	Dynamic array (e.g., Python list), doubly linked list
Map (Associative Array)	`put(k, v)` – associate key `k` with value `v` `get(k)` – retrieve the value for key `k` `remove(k)` – delete the key‑value pair for `k` `containsKey(k)`	Hash table, binary search tree (BST), balanced tree (AVL/Red‑Black)
Set	`add(x)` – insert element `x` (no duplicates) `remove(x)` `contains(x)` `union(S)`, `intersection(S)`, `difference(S)`	Hash set, BST, bit‑vector
Priority Queue	`insert(x, p)` – insert element `x` with priority `p` `removeMin()` / `removeMax()` – delete element with highest/lowest priority `peek()` – view the element with highest/lowest priority	Binary heap, d‑ary heap, balanced BST

5. Implementing an ADT – Stack Using an Array

The pseudo‑code below follows the specification in Section 4 while using a fixed‑size array. It demonstrates information hiding – the client can only call the four public operations.

CONST MAX = 100

TYPE StackArray
    data: array[0..MAX‑1] of integer
    topIndex: integer ← -1          // -1 indicates an empty stack

PROCEDURE push(S: StackArray, x: integer)
    IF S.topIndex = MAX‑1 THEN
        ERROR "Stack overflow"
    END IF
    S.topIndex ← S.topIndex + 1
    S.data[S.topIndex] ← x
END PROCEDURE

FUNCTION pop(S: StackArray) RETURNS integer
    IF S.topIndex = -1 THEN
        ERROR "Stack underflow"
    END IF
    x ← S.data[S.topIndex]
    S.topIndex ← S.topIndex - 1
    RETURN x
END FUNCTION

FUNCTION top(S: StackArray) RETURNS integer
    IF S.topIndex = -1 THEN
        ERROR "Stack empty"
    END IF
    RETURN S.data[S.topIndex]
END FUNCTION

FUNCTION isEmpty(S: StackArray) RETURNS boolean
    RETURN S.topIndex = -1
END FUNCTION

6. Complexity Comparison – Array vs. Linked‑List Stack

Operation	Array Implementation	Linked‑List Implementation
push	O(1) (amortised O(1) if dynamic resizing)	O(1)
pop	O(1)	O(1)
top	O(1)	O(1)
isEmpty	O(1)	O(1)

7. Design Exercise – Using a Stack to Test Balanced Brackets

Problem: Given a string consisting of ( ) [ ] { }, determine whether the brackets are correctly balanced.

Required ADT: Stack

Read the input string s of length n.
Create an empty stack S.
For each character c in s:
- If c is an opening symbol (, [ or {, execute push(S, c).
- If c is a closing symbol:
  - If isEmpty(S) → string is unbalanced (stop).
  - Otherwise t ← pop(S) and check that t matches c (e.g. ( matches )). If not, the string is unbalanced (stop).
After the loop, the string is balanced iff isEmpty(S) is true.

Complexity analysis

Time: each character is examined once and each stack operation is O(1) → total O(n).
Space: at most the depth of nesting is stored on the stack → O(k) where k ≤ n. In the worst case (all opening symbols) the space is O(n).

8. Extending the Idea – Other ADTs in Algorithm Design

Queue – breadth‑first search, simulation of waiting lines, printer spooling.
Map – counting frequencies, symbol tables, memoisation in recursive algorithms.
Set – eliminating duplicates, membership testing, “visited” set in graph traversals.
Priority Queue – Dijkstra’s shortest‑path algorithm, event‑driven simulations, Huffman coding.

9. Quick‑Reference Checklist – How This Note Meets the 2026 Cambridge AS & A‑Level Computer Science Syllabus (9618)

Syllabus Requirement	Covered in These Notes?	Action Needed
Define an ADT and explain encapsulation	✅	–
Specify an ADT using signature, pre‑/post‑conditions and complexity	✅ (Stack example)	–
Provide at least three concrete implementations of the same ADT	✅ (array vs. linked‑list stack, table of implementations)	–
Analyse time and space complexity of each implementation	✅ (complexity table + exercise analysis)	–
Use an ADT in a non‑trivial algorithm and justify the choice	✅ (balanced‑brackets algorithm)	–
Discuss other ADTs (Queue, Map, Set, Priority Queue) and give example applications	✅ (Section 8)	–
Include a worked example of an ADT implementation in pseudo‑code	✅ (array‑based Stack)	–
Reference the Cambridge “formal specification” style	✅ (Section 4)	–

If any row shows a ❌, add the missing material before using these notes for revision.

10. Key Take‑aways

An ADT defines what a data structure does, not how it does it.
Formal specifications (signature, pre‑/post‑conditions, complexity) enable reasoning about correctness and performance.
Multiple concrete implementations can satisfy the same ADT; choose the one that best meets the algorithm’s time‑ and space‑requirements.
Selecting the appropriate ADT often leads to clearer design, simpler code, and easier analysis.

Show understanding of and use Abstract Data Types (ADT)