Abstract Data Type

An Abstract Data Type (ADT) is a mathematical model for certain kinds of data structures. It tells you:

• What operations can be performed on the data.
• What the operations do (the behavior).

But it does not tell you how the operations are implemented.

Think of ADT as a contract or blueprint:

• It says what you can do (like insert, delete, search).
• It hides how it’s done (whether internally it uses arrays, linked lists, etc.).

Array Example

Array Data Structure

An array is a collection of elements stored in contiguous memory locations, accessed using an index.

int arr[5] = {10, 20, 30, 40, 50};
cout << arr[2]; // Direct access using index
arr[3] = 99;    // Update value

Array ADT

We define what operations can be done on an array, without worrying about how they’re implemented.

For example: insert(position, value) ,delete(position) ,search(value) ,get(index) ,update(index, value) ,traverse()

The implementation (array in memory, pointer arithmetic, etc.) is hidden from the user.

class Array {
private:
    int *arr;       // pointer to store array elements
    int capacity;   // maximum size
    int length;     // current number of elements

public:
    // constructor
    Array(int size) {
        capacity = size;
        arr = new int[capacity];
        length = 0;
    }

    // insert at end
    void insert(int value) {
        if (length == capacity) {
            cout << "Array Overflow!" << endl;
            return;
        }
        arr[length++] = value;
    }

        // display array
    void display() {
        for (int i = 0; i < length; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }

    // destructor
    ~Array() {
        delete[] arr;
    }
};
int main() {
    Array a(5);

    a.insert(10);
    a.insert(20);
    a.insert(30);
    a.display(); // 10 20 30
}

Array ADT vs Data Structure

Aspect	Array as ADT (Abstract Data Type)	Array as Data Structure (Implementation)
Definition	Logical model that defines what operations can be performed on an array.	Concrete way of storing elements in contiguous memory with fixed indexing.
Focus	What the array can do (operations).	How the array is implemented in memory.
Operations (example)	- insert(position, value) - delete(position) - search(value) - get(index) - update(index, value) - traverse()	- Uses indices for access. - Uses pointer arithmetic (arr[i] = *(arr + i)). - Handles shifting elements for insert/delete.
Implementation details	Hidden from the user (black box).	Explicit — we know it’s stored in contiguous memory and manipulated using loops/pointers.
Flexibility	Can be implemented in multiple ways (static array, dynamic array like vector in C++, linked structure, etc.).	Only one way → fixed-size contiguous memory block.
Example (specification)	“An array supports insert, delete, search, get, update, traverse.”	int arr[5] = {1, 2, 3, 4, 5}; Access via arr[2] = 3.
User’s View	User only sees the operations, not how they are carried out.	Programmer must manage size, shifting, memory allocation, etc.
Analogy	Like a remote control → you know what each button does, not how the circuit inside works.	Like the circuit inside the remote → the actual working mechanism.

Stack Example

A stack is a collection of elements that follows the LIFO (Last In, First Out) principle. That means the last element inserted is the first one removed.

• Array: First a data structure, then wrapped as an ADT.
• Stack: First an ADT, then implemented using data structures.

Stack Data Structure

class Stack {
private:
    int *arr;
    int capacity;
    int top;

public:
    Stack(int size) {
        capacity = size;
        arr = new int[capacity];
        top = -1;
    }

    void push(int value) {
        if (isFull()) {
            cout << "Stack Overflow!" << endl;
            return;
        }
        arr[++top] = value;
    }

    ~Stack() { delete[] arr; }
};

Stack ADT

// Client code using Stack ADT (just knows operations)
Stack s(5);

s.push(10);
s.push(20);
s.push(30);

cout << s.peek() << endl;  // 30
cout << s.pop() << endl;   // 30
cout << s.pop() << endl;   // 20
cout << s.isEmpty() << endl; // 0 (false)

Stack ADT vs Data Structure

Aspect	Stack as ADT (Abstract Data Type)	Stack as Data Structure (Implementation)
Definition	Logical model that defines what operations a stack supports.	Concrete way of implementing stack using array, linked list, etc.
Focus	What can be done (push, pop, peek).	How it’s done (index pointer top, node linking, etc.).
Operations (example)	- push(x) - pop() - peek() - isEmpty() - isFull()	- Array: shifting index, resizing. - Linked List: nodes & pointers.
Implementation details	Hidden from the user (black box).	Explicit — memory management, pointer updates, overflow checks.
Access Rule	LIFO (Last In, First Out).	Enforced via array index (top) or linked nodes.
Flexibility	Can be implemented using array, linked list, or STL.	Tied to chosen approach (fixed-size array vs dynamic linked list).
Example (specification)	“A stack supports push, pop, peek, isEmpty, isFull.”	arr[++top] = value; (array) or new Node(value) (linked).
User’s View	User just uses operations, without caring about details.	Programmer deals with actual memory & algorithm.
Analogy	Like a stack of plates — you know you can only put/take from the top.	The actual cupboard structure (array shelves vs linked chain).