Describe the concept of abstract data types (ADTs)

An abstract data type (ADT) is a data type which does not focus on what is stored but how its stored, a series of operations which manipulate the data.

The fundamental characteristics of ADTs are:

Encapsulation:

Bundles the data (attributes) and the operations (functions) that can act on that data together, hiding internal implementation details.

Better Conceptualization:

Provides a high-level view of the data structure, focusing on what it does rather than how it's built, leading to cleaner and more reusable code.

Operations:

Defines a set of allowed actions (functions) that can be performed on the data, ensuring data integrity and controlled access.

Primitive and Non-Primitive data types

Stacks

It is a linear data structure that follows a particular order in which the operations are performed. LIFO (Last In First Out).

Items are added to the top and the number of items in the stack is kept track of by a top value which is incremented each time an item is pushed/added or popped/removed.

Eg. Pile of plates at a buffet, Undo button

Code

Push

void push(int stack[], int x)
{
	if(top==max-1)
		printf(“Stack is full”);
	else
	{
		top++;
		stack[top]=x;
	}
}

Pop

Int pop(int stack[])
{
	Int x;
	if(top==-1)
		printf(“Stack is empty”);
	Else
	{
		x = stack[top];
		top– ;
	}
return x
}

Queues

A queue is a linear data structure that is open at both ends and the operations are performed in First In First Out (FIFO) order.

Eg. Line at the grocery or bank, Printer list

Code

Enqueue

Void enqueue(int queue[], int x) 
{ 
  if (rear >= (MAX - 1))  
    printf("Queue Overflow");
  else 
    queue[++rear] = x; 
}

Dequeue

int dequeue(int queue[]) 
{ 
    if (front > rear)  
        printf("Queue Underflow"); 
    else 
    { 
        int x = queue[front++]; 
        return x; 
    } 
}

Circular Queues

A circular queue is a type of queue data structure where the last element is connected to the first element, forming a circle-like structure. It follows the First In First Out (FIFO) principle, meaning that the element that is added first is removed first. A circular queue can be implemented using an array or a linked list

Singly linked lists

A linked list is an ADT made up of nodes, each containing two parts, a data store for storing data and a pointer which points to the location of the next node. The linked list has a head pointer which points to the first node and the pointer of the last node points to null to signify the end.