Wednesday, April 16, 2014

DATA STRUCTURE AND ALGORITHM PART 1

Define abstract data type. Write the algorithm for enqueue and dequeue operations in circular queue.

An abstract data type is a mathematical model, together with various operations defined on the model. We shall design algorithms in terms of ADT’s, but to implement an algorithm in a given programming languages we must find some way of representing the ADT’s in terms of the data types and operators supported by the programming language itself.It satisfies  the following two conditions:
§  the representations of, and operations on, objects of the type are defined in a single syntactic unit
§  the representation of objects of the type is hidden from the program units that use these objects, so the only operations possible are those provided in the type definition.
ADT consists of
§  a specification of the possible values of the data types and
§  a specification of the operations that can be performed on those values in terms of the operations inputs, outputs, and effects.
Eg; list, array, stack, queue, etc.
Algorithm for   circular enqueue operations
i.            start
ii.            create an entry queue
iii.            set head and tail point to 0
ie. hp=0;      tp=0
iv.            if queue is full, print the message “queue is full.”
v.            Else if queue is not full
ie. [(tp+1) % Qsize == hp]
Then,
i.            add an item to a queue at tp
ii.            set tp=(tp+1)%Qsize
Algorithm for   circular dequeue operations
i.            start
ii.            if queue is empty,
Print the message “queue is empty “.
iii.            Else if queue is not empty ,[hp==tp]
then,
i.            read data from q[hp]
ii.            Set hp= (hp+1) %Qsize. 

No comments:

Post a Comment