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.