ADT from ADT (Cambridge (CIE) A Level Computer Science): Revision Note

ADT from ADT

What does it mean?

• You should be able to explain or demonstrate how you can build one abstract data type on top of another

• For example:

  • A stack can be implemented using a linked list

  • A queue can be implemented using two stacks

  • A dictionary can be implemented using a binary search tree

• You’re not just limited to built-in types like arrays, you can compose ADTs out of each other

What is an ADT?

• If you are unsure what an ADT is, read our ADT overview page

How are ADTs implemented?

Using built-in types (e.g. arrays, lists)

Using other ADTs

Example: Implementing a Queue using Two Stacks

Idea:

• Use two stacks (let’s say inStack and outStack) to simulate a queue

How it works:

• enqueue(x) → push x onto inStack

• dequeue() → if outStack is empty, pop all items from inStack and push onto outStack, then pop from outStack

• This simulates FIFO behaviour using LIFO operations from stacks