Abstract Data Types

6 minread

1,102words

Intermediatelevel

Abstract Data Types (ADT)

An Abstract Data Type (ADT) is a way to describe the logical structure and operations of a data type without worrying about how it's implemented in a specific programming language. In simple terms, ADT focuses on what operations can be done on data and how the data behaves, rather than how those operations are carried out internally.

Think of ADT as a "blueprint" for data. It tells us what operations the data should support, but not exactly how to implement them. For example, it might describe that we can "add an element" or "remove an element," but it doesn't say whether to use an array or a linked list to store the data.

Key Components of ADTs:

Data: What kind of data is being stored? It defines the type of data the structure will handle (e.g., integers, characters, objects).
Operations: What operations can be performed on the data? It defines what you can do with the data, like inserting, deleting, or accessing elements.
Rules: These are the rules for how data should behave when the operations are performed. For example, in a stack, the rule is Last In, First Out (LIFO), meaning the last element added is the first one to be removed.

Common Abstract Data Types

Stack

A stack is a data structure that follows the "Last In, First Out" (LIFO) principle. This means that the last element added to the stack is the first one to be removed. You can think of it like a stack of plates: the last plate you place on top is the first one you take off.
Operations:
- push(): Add an element to the top of the stack.
- pop(): Remove the top element from the stack.
- peek(): View the top element without removing it.
- isEmpty(): Check if the stack is empty.
Rules: Last In, First Out (LIFO).

Example in C++:

class Stack {
private:
    int arr[100];  // array to store stack elements
    int top;       // top index of the stack
public:
    Stack() { top = -1; } // constructor initializes stack
    void push(int x) { arr[++top] = x; } // add an element
    void pop() { if (top >= 0) top--; }  // remove the top element
    int peek() { return arr[top]; }      // view the top element
    bool isEmpty() { return top == -1; } // check if stack is empty
};

Queue
- A queue is a data structure that follows the "First In, First Out" (FIFO) principle. This means that the first element added to the queue is the first one to be removed. It's like a line at a ticket counter, where the person who arrives first is the first to be served.
- Operations:
  - enqueue(): Add an element to the end of the queue.
  - dequeue(): Remove the front element from the queue.
  - front(): View the front element without removing it.
  - isEmpty(): Check if the queue is empty.
- Rules: First In, First Out (FIFO).
Example in C++:
```
class Queue {
private:
    int arr[100];  // array to store queue elements
    int front, rear; // front and rear indexes
public:
    Queue() { front = -1; rear = -1; }
    void enqueue(int x) { arr[++rear] = x; if (front == -1) front = 0; }
    void dequeue() { if (front <= rear) front++; }
    int getFront() { return arr[front]; }
    bool isEmpty() { return front == -1 || front > rear; }
};
```
List
- A list in C++ is a data structure that allows you to store a collection of elements in a sequence. Unlike arrays, lists can easily grow or shrink in size because they don't need a fixed size when created. A linked list is a common type of list, where each element (called a node) points to the next element in the sequence. This makes inserting or removing elements efficient, especially when you don't know the size in advance. In C++, lists are part of the Standard Template Library (STL) and allow operations like adding, removing, and accessing elements in an ordered way
- Operations:
  - insert(): Add an element at a specific position.
  - remove(): Remove an element.
  - get(): Access an element by index.
  - size(): Get the total number of elements.
- Rules: No strict ordering rules like stacks or queues.
Tree
- A tree is a hierarchical data structure where data is stored in nodes, and each node can have a parent and zero or more children. The top node is called the root, and nodes with no children are called leaves. Trees are used to represent structures with a hierarchy, like folder structures in file systems or organization charts. In C++, trees are often used to implement efficient searching and sorting algorithms, like binary search trees (BST), where each node has at most two children, and data is organized so searching for an element is faster.
- Operations:
  - insert(): Add a new node.
  - remove(): Delete a node.
  - traverse(): Visit all nodes (inorder, preorder, postorder).
  - search(): Find a specific node.
- Rules: Data is organized in a hierarchical structure, with a root node and children.

Why Use ADTs?

Abstraction: ADTs hide the details of how data is stored and manipulated. This makes it easier to use the data type without worrying about the underlying complexity.
Modularity: ADTs allow you to break down complex problems by separating the "what" from the "how". You can define operations first, then implement them later, which is good for designing large systems.
Reusability: Once an ADT is defined, it can be used in different parts of a program or in different programs altogether.

Difference Between ADT and Data Structure

ADT: Focuses on what the operations are (conceptual).
Data Structure: Focuses on how the operations are performed and how the data is organized in memory (concrete).

For example, an ADT might define a "List" with operations like "insert", "delete", and "get", while a linked list or an array would be actual data structures that implement the ADT in C++.

Conclusion

Abstract Data Types are an essential concept in computer science because they allow us to think about data in a higher-level, more abstract way. They help define the operations and rules that govern how data should behave without worrying about the actual implementation. This approach makes it easier to design and use data structures like stacks, queues, and lists in programming.

Next topic 2

Complexity Analysis

Past Papers

Open this section to load past papers

Click on Show Past Papers to see past papers.

class Stack { private: int arr[100]; // array to store stack elements int top; // top index of the stack public: Stack() { top = -1; } // constructor initializes stack void push(int x) { arr[++top] = x; } // add an element void pop() { if (top >= 0) top--; } // remove the top element int peek() { return arr[top]; } // view the top element bool isEmpty() { return top == -1; } // check if stack is empty };

class Queue { private: int arr[100]; // array to store queue elements int front, rear; // front and rear indexes public: Queue() { front = -1; rear = -1; } void enqueue(int x) { arr[++rear] = x; if (front == -1) front = 0; } void dequeue() { if (front <= rear) front++; } int getFront() { return arr[front]; } bool isEmpty() { return front == -1 || front > rear; } };