Show how it is possible for ADTs to be implemented from another ADT

19.1 Algorithms – Implementing an ADT from Another ADT

1. What is an ADT?

An Abstract Data Type (ADT) defines a set of values and a collection of operations that can be performed on those values, without specifying how the data is stored or how the operations are carried out.

Typical ADTs studied at A‑Level include:

• Stack
• Queue
• List
• Priority Queue
• Dictionary (Map)

2. Why implement one ADT using another?

Implementing an ADT in terms of another ADT has several benefits:

1. Re‑use of existing, well‑tested code.
2. Simplifies reasoning about correctness – if the underlying ADT is correct, the derived ADT inherits that correctness.
3. Allows optimisation by choosing an underlying ADT that gives the best performance for the required operations.

3. General Strategy

To implement ADT \$A\$ using ADT \$B\$ we follow these steps:

1. Identify the operations required by \$A\$.
2. Map each operation of \$A\$ to one or more operations of \$B\$.
3. Write wrapper algorithms that translate calls to \$A\$ into calls to \$B\$.
4. Prove (informally) that the wrapper preserves the semantics of \$A\$.

4. Example Implementations

4.1 Stack using a List

A stack supports push(x), pop() and top(). If we have a dynamic array‑based list \$L\$, we can implement a stack as follows:

push(x):
L.append(x)               // add at the end of the list
pop():
if L.isEmpty() then error
return L.removeLast()     // remove the last element
top():
if L.isEmpty() then error
return L.get(L.size()‑1)  // read the last element without removing

All stack operations run in \$O(1)\$ amortised time because list append and removeLast are constant‑time for an array‑list.

4.2 Queue using Two Stacks

A queue requires enqueue(x) and dequeue(). Using two stacks \$S1\$ and \$S2\$ we obtain:

enqueue(x):
S1.push(x)
dequeue():
if S2.isEmpty() then
while not S1.isEmpty() do
S2.push(S1.pop())
if S2.isEmpty() then error
return S2.pop()

This implementation guarantees \$O(1)\$ amortised time for both operations.

4.3 Priority Queue using a Binary Heap (which itself can be viewed as an array‑based ADT)

The binary heap provides insert, deleteMin (or deleteMax) and peek. The priority‑queue ADT can be directly mapped to these heap operations.

5. Comparative Table of Operation Complexities

6. Correctness Argument (Sketch)

For each wrapper algorithm we must show that the sequence of underlying operations preserves the abstract specification of the target ADT.

• Stack from List: The list’s last element always corresponds to the top of the stack. push adds an element at that position, and pop removes it, matching the LIFO property.
• Queue from Two Stacks: Elements are first pushed onto \$S1\$ in arrival order. When \$S2\$ is empty, all elements are transferred, reversing their order, so the oldest element ends up on top of \$S_2\$ and is the next to be dequeued. This enforces FIFO behaviour.
• Priority Queue from Heap: The heap invariant (parent ≤ children for a min‑heap) guarantees that the smallest element is always at the root, which peek and deleteMin expose directly.

7. Summary

Implementing an ADT using another ADT is a powerful design technique. By carefully mapping operations and analysing the resulting algorithms, we can:

• Leverage existing, reliable code.
• Achieve desired performance characteristics.
• Maintain clear, modular designs that are easier to test and verify.