1.2 ~30 min easy

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.

Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.

02Mental 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:

the data it holds (logically, e.g. “an ordered collection”),
the operations allowed on it (e.g. push, pop, top, isEmpty),
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.

03Visualize

space play · ←→ step · r reset. The highlighted code line follows each step.

Loading visualizer…

Push a few values, then pop. The caller's view never changes; only the hidden storage does.

04C++ code

Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.

a Stack ADT with two implementations56 lines · C++17

Compiler ExplorerRun OnlineGDB

#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 ");
}

#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

array stack: 30 20 10 
list stack : 30 20 10

05Complexity

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.

06Watch

Introduction to data structures

mycodeschool · 6:33

Why this one: The second half explains ADTs with the list example, exactly the "interface vs implementation" split.

Watched

Introduction to stack

mycodeschool · 8:26

Why this one: Shows the stack as an ADT before any code. A preview of Chapter 5.

Watched

Original class slides (Python, by the course's lecture authors):Basic Data Structures

07Exam 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.

08Quick check

1.An Abstract Data Type specifies…
2.Which is an implementation (a data structure), not an ADT?
3.In C++, which feature hides implementation details from users of a class?
4.You replace an array-based stack with a linked-list stack. What must change in code that only uses push/pop?

09Practice

🟢 Trace by hand

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

Show answer

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.

Solution

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

🔴 Solve problems

Implement Stack using Queues easyleetcode.com
Hint
The Stack ADT does not care what is underneath. Can you meet its contract using only queue operations?

Solution idea
After each push of x into a queue of size k, rotate the queue k times (pop front, push back) so x is at the front.
Design Parking System easyleetcode.com
Hint
Decide the interface first (addCar), then the hidden data (three counters).

10Mastery checklist

Tick these honestly. When every box is ticked, the topic is marked complete.

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++.

0/4 ticked

My notes

View as Markdown · Chapter cheat sheet