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

19.1 Algorithms – Implementing ADTs from Other ADTs

Abstract Data Types (ADTs) – Quick Recap

An ADT defines a data type by its behaviour rather than its implementation. For example, a Stack supports push, pop, peek and isEmpty.

Why Build One ADT from Another?

Sometimes we want to reuse existing code or we only have access to a basic data structure. By combining two simple ADTs we can create a more complex one. Think of it like building a LEGO model: you can create a spaceship (Queue) using only two boxes (Stacks).

Example 1: Queue Using Two Stacks

A Queue is FIFO (first‑in, first‑out). We can implement it with two Stacks (LIFO). The idea is to use one stack for enqueue and the other for dequeue operations.

1. Let stackIn be the stack where we push new elements.
2. Let stackOut be the stack from which we pop elements.
3. When dequeue() is called and stackOut is empty, move all elements from stackIn to stackOut (this reverses the order).
4. Pop from stackOut.

⚙️ Pseudocode:

enqueue(x):
    stackIn.push(x)

dequeue():
    if stackOut.isEmpty():
        while not stackIn.isEmpty():
            stackOut.push(stackIn.pop())
    return stackOut.pop()

This works because the transfer step reverses the order twice, restoring FIFO behaviour.

Example 2: Stack Using Two Queues

Conversely, we can build a Stack using two Queues. Here we keep all elements in queue1 and use queue2 as a temporary buffer.

1. For push(x), enqueue x into queue2.
2. Move all elements from queue1 to queue2 (preserving order).
3. Swap the names of queue1 and queue2.
4. For pop(), simply dequeue from queue1.

⚙️ Pseudocode:

push(x):
    queue2.enqueue(x)
    while not queue1.isEmpty():
        queue2.enqueue(queue1.dequeue())
    swap(queue1, queue2)

pop():
    return queue1.dequeue()

Example 3: Set Using a List

A Set contains unique elements. We can implement it with a simple List by checking for duplicates before insertion.

1. To add(x), first check if x already exists in the list.
2. If not, append x to the list.
3. To contains(x), search the list.

⚙️ Pseudocode:

add(x):
    if not contains(x):
        list.append(x)

contains(x):
    for element in list:
        if element == x:
            return true
    return false

Time Complexity Summary

Key Takeaways

• ADTs are defined by operations, not by how they are stored.
• Complex ADTs can be built from simpler ones, saving time and code.
• Understanding these constructions helps you think flexibly about data structures.
• Remember to analyse time complexity – some implementations may be slower (e.g., stack‑using‑queues has $O(n)$ push).

💡 Practice challenge: Try implementing a Deque (double‑ended queue) using two Stacks or two Queues. Think about how to maintain both ends efficiently.