IPU BCA/BTech Semester 2 - Data Structures - Abstract Data Type (ADT)

Data Structures - Abstract Data Types (ADT)

Question: 
(a) What is Abstract Data Type (ADT)? 
(b) Give examples of commonly used ADTs.
(c) What are the advantages of ADTs?


Answer:
(a) An abstract data type (ADT) is a logical description or a specification of components of the data and the operations that are allowed and it is independent of the implementation. An ADT is a user defined data type that are defined along with their operations.

An ADT consists of two parts:
1. Declaration of data
2. Declaration of operations

(b) Commonly used ADTs are:
Linked Lists,
Stacks,
Queues,
Priority Queues,
Binary Trees,
Dictionaries,
Disjoint Sets,
Hash Tables,
Graphs etc.




(c) Advantages of ADTs are:

① Encapsulation: The user need not know knowledge of implementing the ADT. Its implementation may be complex but it is be encapsulated in a simple interface while defining it.

② Localization of change: Code that uses an ADT object do not require editing if the implementation of the ADT  changes.

③ Flexibility: Different implementations of an ADT may be more efficient in different situations thus increases the overall efficiency of the program.

④ Easy to understand and reusable code.


Question: Write down one dimensional array specifications as ADT.

Answer: eltype denotes type of element and ub is the upper bound.

abstract typedef <<eltype, ub>> ARRTYPE(ub, eltype);
condition type(ub) == int;

abstract eltype extract(a, i)  /* written as a[i] */
ARRTYPE(ub, eltype) a;
int i;
precondition 0 <= i < ub;
postcondition extract == a₁

abstract store(a, i, elt)
ARRTYPE (ub, eltype) a;
int i;
eltype elt;
precondition  0 <= i < ub;
postcondition a[i] == elt;



Question: Write down representation of a stack as ADT.

Answer:

abstract typedef <<eltype>> STACK (eltype);

abstract empty(s)
STACK (eltype s)
postcondition (empty == len(s) == 0);

abstract eltype pop(s)
STACK (eltype) s;
precondition empty(s) == FALSE;
postcondition pop == first(s)
s == sub(s', 1, len(s') - 1);


abstract push (s, elt)
STACK (eltype) s;
eltype elt;
postcondition s == <elt> + s';



Question: Represent queue as Abstract Data Type (ADT).

Answer:

abstract typedef <<eltype>> QUEUE (eltype);

abstract empty(q)
QUEUE (eltype) q;
postcondition empty == (len(q) == 0);

abstract eltype remove(q)
QUEUE (eltype) q;
precondition empty(q) == FALSE;
postcondition remove == first(q');
q == sub(q', 1, len(q') - 1);

abstract insert (q, elt)
QUEUE (eltype) q;
eltype elt;
postcondition q = q' + <elt>;


See also:
  - Abstract Data Type Notes by CSE Department IIT Kharagpur
  - Data Structure Notes by IIT Kgp