�ݺ�ߣ

Abstract Data Types (ADT)
 We are well acquainted with data types by
now, like integers, arrays, and so on.
 To access the data, we've used operations
defined in the programming language for the
data type, for instance by accessing array
elements by using the square bracket notation.
 An abstract data type is a data type whose
representation is hidden from, and of no
concern to the application code.
5

Abstract Data Types (ADT)
 For example, when writing application code, we don’t
care how strings are represented: we just declare
variables of type string, and manipulate them by using
string operations.
 Once an abstract data type has been designed, the
programmer responsible for implementing that type is
concerned only with choosing a suitable data structure
and coding up the methods.
 On the other hand, application programmers are
concerned only with using that type and calling its
methods without worrying much about how the type is
implemented.
6

The Array As An ADT
• An array is probably the most versatile or
fundamental Abstract Data Type
• An array is a finite sequence of storage cells,
for which the following operations are defined:
– create(A,N)creates an array A with storage for N
items;
– A[i]=item stores item in the ith
position in the array
A; and
– A[i] returns the value of the item stored in the ith
position in the array A.
7

Showing that an array is an ADT
Let A be an array of type T and has n elements then it satisfied the
following operations
1. CREATE(A): Create an array A
2. INSERT(A,X): Insert an element X into an array A in any location
3. DELETE(A,X): Delete an element X from an array A
4. MODIFY(A,X,Y): modify element X by Y of an array A
5. TRAVELS(A): Access all elements of an array A
6. MERGE(A,B): Merging elements of A and B into a third array C
Thus by using 1D array we can perform above operations thus an array
acts as an ADT.
8

Simple as it sounds
Fig. stack of items
10

Definition
• A stack is an ordered collection of
items into which new items may be
inserted and from which items may be
deleted at one end, called the top of the
stack.
• Stack is a linear data structure where all the
insertions and deletions are done at end
rather than in the middle.
11

Intro
• We may come across situations, where
insertion or deletion is required only at one
end, either at the beginning or end of the
list.
• The suitable data structures to fulfil such
requirements are stacks and queues.
• For ex. a stack of plates, a stack of coins,
a stack of books etc. 12

Stack as an abstract data type
• A stack of elements of type T is a finite sequence of
elements together with the operations
1. CreateEmptyStack(S): create or make stack S be an empty
stack
2. Push(S,x): Insert x at one end of the stack, called its top
3. Top(S): If stack S is not empty; then retrieve the element
at its top
4. Pop(S): If stack S is not empty; then delete the element at
its top
5. IsFull(S): Determine if S is full or not. Return true if S is
full stack; return false otherwise
6. IsEmpty(S): Determine if S is empty or not. Return true if
S is an empty stack; return false otherwise.
13

Operations
• Push – Place something on stack on the top
• Pop – Remove the very top item
• Top – examine without removing top item
• IsEmpty – Tells us whether the stack is
empty
• size – how many elements are there?
15

Simple Example
• Undo
• Browser History (Back)
16

ADT conclusion
• An abstract data type is the specification of the data type which
specifies the logical and mathematical model of the data type.
• ADT acts as a useful guideline to implement a data type correctly.
• The implementation of an ADT involves the translation of the ADT’s
specification into syntax of a particular programming language.
• For ex, the int data type, provides an implementation of the
mathematical concept of an integer number.
• The int data type in C can be considered as an implementation of
Abstract Data Type, INTEGER-ADT, which defines the union of set
{ -1, -2, -3 …} and the set of whole numbers {0, 1, ....}
17

�ݺ�ߣ

Abstract data types (adt) intro to data structure part 2

More Related Content

Abstract data types (adt) intro to data structure part 2