# 1.2 ADTs & Abstraction

> An Abstract Data Type says WHAT operations exist; a data structure says HOW they are built. Separating the two is the key idea of this course.

Chapter: Introduction to Data Structures · ~30 min · easy
URL: https://dsa.fetehadin.com/learn/adt-and-abstraction

## Mental model

Think of a **TV remote**. You know *what* the buttons do: power, volume up, next channel. You have no idea *how* the infrared signal is encoded, and you don't need to. If the manufacturer redesigns the circuit board, you keep pressing the same buttons.

**Abstraction** means showing only what matters to the user and hiding the rest.

### Abstract Data Type (ADT)

An **ADT** is the "remote control" view of a data type. It describes:

1. **the data** it holds (logically, e.g. "an ordered collection"),
2. **the operations** allowed on it (e.g. `push`, `pop`, `top`, `isEmpty`),
3. **the rules and error conditions** (e.g. "pop on an empty stack is an error").

It says nothing about arrays, pointers or memory.

### Data structure

A **data structure** is the *circuit board*: a concrete way to store the data so the ADT's operations work. The Stack ADT can be implemented with an array **or** a linked list. Both are valid data structures for the same ADT.

| | ADT | Data structure |
|---|---|---|
| Answers | *What* can I do? | *How* is it stored? |
| Level | Logical | Physical / implementation |
| Example | Stack, Queue, List | Array-based stack, linked list |

### In C++

A `class` makes this concrete: the **public** member functions are the ADT's interface, and the **private** members are the implementation. Hiding them is called **encapsulation**. Code that uses the class cannot break its internal rules.

## C++ code: a Stack ADT with two implementations

```cpp
#include <iostream>
using namespace std;

// The ADT: WHAT a stack does. Users only see these operations.
class Stack {
public:
    virtual void push(int x) = 0;
    virtual int pop() = 0;
    virtual int top() const = 0;
    virtual bool isEmpty() const = 0;
    virtual ~Stack() {}
};

// Implementation 1: array (fixed capacity)
class ArrayStack : public Stack {
    int a[100];
    int t = -1;
public:
    void push(int x) override { a[++t] = x; }
    int pop() override { return a[t--]; }
    int top() const override { return a[t]; }
    bool isEmpty() const override { return t == -1; }
};

// Implementation 2: linked list (grows as needed)
class ListStack : public Stack {
    struct Node { int data; Node* next; };
    Node* head = nullptr;
public:
    void push(int x) override { head = new Node{x, head}; }
    int pop() override {
        Node* old = head;
        int x = old->data;
        head = head->next;
        delete old;
        return x;
    }
    int top() const override { return head->data; }
    bool isEmpty() const override { return head == nullptr; }
    ~ListStack() { while (!isEmpty()) pop(); }
};

// Client code only knows the ADT, so it works with either implementation.
void demo(Stack& s, const char* name) {
    for (int i = 1; i <= 3; i++) s.push(i * 10);
    cout << name << ": ";
    while (!s.isEmpty()) cout << s.pop() << " ";
    cout << "\n";
}

int main() {
    ArrayStack a;
    ListStack l;
    demo(a, "array stack");
    demo(l, "list stack ");
}
```

Expected output:

```text
array stack: 30 20 10 
list stack : 30 20 10
```

## Complexity

| Case | Cost |
| --- | --- |
| push / pop / top (array implementation) | O(1) |
| push / pop / top (linked implementation) | O(1) |
| Maximum size | array: fixed · linked list: limited only by memory |


The ADT promises the operations; each implementation decides their cost. That is why we analyse implementations, not ADTs.

## Videos

- [Introduction to data structures](https://youtu.be/92S4zgXN17o) (mycodeschool): The second half explains ADTs with the list example, exactly the "interface vs implementation" split.
- [Introduction to stack](https://youtu.be/F1F2imiOJfk) (mycodeschool): Shows the stack as an ADT before any code. A preview of Chapter 5.

## Exam lens

Likely questions:

- Define Abstract Data Type (ADT). Give one example and list its operations.
- What is abstraction? Why is it useful in programming?
- Differentiate between an ADT and a data structure.
- Explain how a C++ class supports abstraction and encapsulation.

Common mistakes:

- Saying an ADT "is" an array. An ADT has no storage details at all; an array can only *implement* one.
- Listing implementation details (like `top` index) as part of the ADT's definition.
- Forgetting error conditions. "pop on an empty stack is an error" IS part of the ADT.

## Quick check

1. An Abstract Data Type specifies…
   A. the data and the operations, but not how they are implemented
   B. the exact memory layout
   C. the C++ code of each operation
   D. only the data, not the operations
   Answer: A. An ADT is a logical description, a "contract". Implementation is the data structure's job.

2. Which is an implementation (a data structure), not an ADT?
   A. Stack
   B. Queue
   C. List
   D. Singly linked list with a head pointer
   Answer: D. "Singly linked list with a head pointer" describes how the data is stored, so it is a data structure that can implement the List ADT.

3. In C++, which feature hides implementation details from users of a class?
   A. `public` members
   B. `private` members
   C. `#include`
   D. `cout`
   Answer: B. Private members can only be used inside the class. Users must go through the public interface; that is encapsulation.

4. You replace an array-based stack with a linked-list stack. What must change in code that only uses push/pop?
   A. Everything
   B. Only the type name it is created with
   C. All pop calls
   D. All push calls
   Answer: B. Because the client depends only on the ADT's operations, swapping implementations does not affect it.

## Practice

**Trace by hand.** Write the ADT specification (data + operations + error conditions) for a **Queue**, without writing any code.

Solution:

**Data:** an ordered collection; items leave in the order they arrived (FIFO).

**Operations:** `enqueue(x)` adds at the rear, `dequeue()` removes and returns the front item, `front()` returns the front item without removing it, `isEmpty()`, `size()`.

**Errors:** `dequeue()` / `front()` on an empty queue; `enqueue` on a full queue (bounded implementations only).


**Implement it.** Write a `Counter` class whose value can only change through `increment()`, `decrement()` (never below 0) and `reset()`, and read through `get()`.

Hint: Keep `int value` private. The rule "never below 0" lives inside `decrement()`; that is abstraction protecting an invariant.

```cpp
class Counter {
    int value = 0;
public:
    void increment() { value++; }
    void decrement() { if (value > 0) value--; }
    void reset() { value = 0; }
    int get() const { return value; }
};
```


**Problems:**

- [Implement Stack using Queues](https://leetcode.com/problems/implement-stack-using-queues/) (easy). Hint: The Stack ADT does not care what is underneath. Can you meet its contract using only queue operations?
- [Design Parking System](https://leetcode.com/problems/design-parking-system/) (easy). Hint: Decide the interface first (`addCar`), then the hidden data (three counters).

## Mastery checklist

- [ ] I can define ADT and abstraction in my own words.
- [ ] I can explain the difference between an ADT and a data structure.
- [ ] I can write an ADT specification (data, operations, errors) for stack and queue.
- [ ] I can use private members to hide implementation details in C++.