Cambridge Notes, Past Papers, Revision Questions

Cambridge A-Level CS 9618 – 10.4 Introduction to Abstract Data Types (ADT)

Introduction to Abstract Data Types (ADT)

An Abstract Data Type (ADT) is a formal description of a set of data values together with a set of operations that can be performed on those values. The ADT specifies what operations are available and the behaviour of those operations, but not how they are implemented.

Key Concepts

Data Set – the collection of values that the ADT can hold.

Operations – functions or methods that manipulate the data set.

Specification – the contract that defines the behaviour of operations.

Implementation – a concrete data structure that satisfies the specification.

Examples of ADTs

Stack – LIFO (Last In, First Out) structure.

Queue – FIFO (First In, First Out) structure.

List – ordered collection with indexed access.

Set – unordered collection of unique elements.

Map (Dictionary) – key–value pairs with unique keys.

Operations on ADTs

Operations are defined by the ADT specification. For a Stack ADT the typical operations are:

Operation	Parameters	Returns	Description
push	value	void	Adds value to the top of the stack.
pop	none	value	Removes and returns the top element.
peek	none	value	Returns the top element without removing it.
isEmpty	none	boolean	Checks whether the stack contains no elements.

The behaviour of these operations can be expressed mathematically. For example, if S denotes the stack state and v a value, then:

\$\text{push}(S, v) = S \cup \{v\}\$ (with v at the top)

\$\text{pop}(S) = (v, S')\$ where v is the top element and S' is the remaining stack.

ADT vs Concrete Implementation

ADT	Concrete Implementation	Typical Operations	Key Properties
Stack	Array, Linked List, Dynamic Array	push, pop, peek, isEmpty	Last In, First Out; O(1) amortised for array implementation.
Queue	Array, Circular Buffer, Linked List	enqueue, dequeue, front, isEmpty	First In, First Out; O(1) for circular buffer.
Set	Hash Table, Binary Search Tree	add, remove, contains, size	Unique elements; average O(1) for hash table.
Map	Hash Table, Binary Search Tree	put, get, remove, containsKey, size	Key–value pairs; average O(1) for hash table.

Suggested Diagram

Suggested diagram: Flow of operations on a Stack ADT – showing push, pop, and peek actions relative to the stack top.