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
No comments