Why ADT:
* Modularity
divided program into small functions
esy to debug and maintain
easy to modify
group work
* reuse
do some operatons only once
* easy to change the implementation
transparent to the program
the list is an:
ordered sequence of data intems called elements
A1,A2,A3,.......,An is a list of size N
size of an empty list is 0
first element A1 is called "head"
the last element An is called "tail"
EXAMPLE:
The elements of a list are 34,12,52,16,12
-find(52) -> 3
-insert(20,4) -> 34,12,52,20,16,12
-delete(52) -> 34,12,20,16,12
find Kth(3) -> 20
list impelmentation
can be implemented using:
-array
-linked list
-cursor
ARRAYS:
-is a static data structure that represents a collection of fixed number of
homogeneours data items or
-a fixed-size indexed sequence of elements, all of the same type.
-the individual elements are typically stored in consecutive memory locations
-the length of the array is determined when the array is created, and cannot be
changed.
-any component of the array can be inspected or updated by using its index
*this is an efficient operation
*O(1) = constant time
-the aray indices may be integers(C,Java) or other discrete data types(Pascal)
Types of ARRAY:
One dimensional- only one index is used
Multi dimensional - array involving more than one index
Static -the compiler t\determines how memory will be allocated for the array
Dynamic - memory allocation takes place during
DATA STRUCTURE:
LINEAR DATA STRUCTURE:
STACKS:
*It is an ordered collection of homogeneous data element where the insertion and
deletion take place at one end.
*It is called a last-in-first-out collection
*It means, the item last entered will be first our.
eg:plates in a tray
trains in a railway yard
goods in a cargo.
OPERATION IN STACK:
insert (push operation)
deletion (pop operation)
top (current location of data)
*** PUSH-INSERT
*** POP-DELETE
ALGORITHM FOR PUSH OPERATION:(PUSH(A,Top,Item,Size))
* START
* If TOP>=SIZE
* PRINT"STACK IS FULL " or stack overflow
* Else
* Top=Top+1
* A[top] = item
* End if
* Stop
ALGORITHM FOR POP OPERATION:(PUSH(A,Top,Item))
* Start
* If Top<1
* Print"Stack is empty" or stack underflow
* else
* item = A[top]
* top = top - 1
* end if
* stop
applicagtions of stacks
* reversing string
* checking of nested parenthesis
* evaluation of arithmetic expresions
* conversion of infix expression to postfix expression
* evaluation of postfix expression
* implemention of recursion
INFIX:
X+Y
PREFIX:
+XY
POSTFIX:
XY+
PARENTHESES:
(*) evaluate2+3*5
(*) + first
(2+3)*5 = 5*5 = 25
(*) *first:
2+(3*5) = 2+15 = 17
(*) infix notation requires parenthesis
infix to prefix conversion:
Move each operatTor to the left of its operands & remove the parentheses:
((A + B)*(C + D))
ALGORITHM FOR INFIX TO POSTFIX:
* If the token is a operand, then put it in the postfix operation.
* If the token is an operator, then store the operator in stack.
* Any operator in the stack havng higher precedence than the operator that we are
looking at, can be popped and placed into the postfix expresionm else will be
pushed.
* If reached at the end of expression, then pop the operations and place it.
EVALUATION OF PREFIX AND POSTFIX OPERATION:
* Resolve operator recedence and put parenthesis.
* Consider the expression:
-> ( a*b + c*d - e )
* Postfix expression: ab*cd*+e-
* Prefix expression: -+*ab*cde
* Let us take a=2,b=3,c=4,d=2,e=3.
FPE INFIX TO POSTFIX;
Initilize a stack for operators, output list
Split the inut into a list of tokens.
for each token(left to right):
-> if it is operand: append to output
-> if it is '(' : push onto Stack
-> if it is ')' : pop & append till '('
Eg:
1) (((A+B)*(C-E))/(F+G))
stack: <empty>
output: []
2) ((A+B)*(C-E))/(F+G))
stack: (
output: []
3) (A+B)*(C-E))/(F+G))
stack: ((
output: []
4) A+B)*(C-E))/(F+G))
stack: (((
output: []
5) +B)*(C-E))/(F+G))
stack: (((
output: [ A ]
6) B)*(C-E))/(F+G))
stack: (((+
output: [ A ]
7) )*(C-E))/(F+G))
stack: (((+
output: [ AB ]
8) *(C-E))/(F+G))
stack: ((
output: [ AB+ ]
9) (C-E))/(F+G))
stack: ((*
output: [ AB+ ]
10) C-E))/(F+G))
stack: ((*(
output: [ AB+ ]
11) -E))/(F+G))
stack: ((*(
output: [ AB+C ]
12) E))/(F+G))
stack: ((*(-
output: [ AB+C ]
13) ))/(F+G))
stack: ((*(-
output: [ AB+CE ]
14) )/(F+G))
stack: ((*
output: [ AB+CE- ]
15) /(F+G))
stack: (
output: [ AB+CE-* ]
16) (F+G))
stack: (/
output: [ AB+CE-* ]
17) F+G))
stack: (/(
output: [ AB+CE-* ]
18) +G))
stack: (/(
output: [ AB+CE-*F ]
19) G))
stack: (/(+
output: [ AB+CE-*F ]
20) ))
stack: (/(+
output: [ AB+CE-*FG ]
21) )
stack: (/
output: [ AB+CE-*FG+ ]
22)
stack:
output: [ AB+CE-*FG+/ ]
INFIX:
EG: ((A+B)/C+D*(E-F)^G)
REVERSE: )G^)F-E(*D+C/)B+A((
TOKEN STACK OP
) )
G G
^ )^ G
) )^) G
F )^) GF
- )^)- GF
E )^)- GFE
( )^ GFE-
* )* GFE-^
D )* GFE-^D
+ )+ GFE-^D*
C )+ GFE-^D*C
/ )+/ GFE-^D*C
) )+/) GFE-^D*C
B )+/) GFE-^D*CB
+ )+/)+ GFE-^D*CB
A )+/)+ GFE-^D*CBA
( )+/ GFE-^D*CBA+
( GFE-^D*CBA+/+
APPLICATIONS OF QUEUES:
* Queues are widely used as waiting lists for a single shared resource like
printeer, disk, CPU.
* Queues are used as buffers in most of the applications like MP3 media player, CP
player, etc.
* Queue are used to maintain the play list in media players in ouder to add and
remove the songs from the play-list.
* Queues are used in operating systems for handiling interrupts.
ENQUEUE(int x);(simple program to add numbers in a queue:)
{
if (front == -1);
{
front++
}
if (rear==SIZE-1)
{
PRINTF("QUEUE is full",);
}
else
{
a[++rear]=x;
}
}
WHAT TO DO WHEN THE QUEUE IS FULL AND U NEED SPACE AT THE REAR-(MOVE THE WHOLE
QUEUE A STEP AHEAD TO GET SPACE AT THE REAR):
Dequeue()
{
return a[0];//returnign first element
for(i=0;i<rear;i++)//shifting all other elements
a[i]=a[i+1];
rear--;
}
""" IF A QUEUE IS FULL AND WE CANT INSERT A VALUE - THEN PUSH THE
ENTIRE STACK A STEP AHEAD, SO THAT WE CAN GET A SPACE AT THE REAR END:
"""
DISADVANTAGES OF LINEAR QUEUE:
* On deletion of an element from existing queue,front pointer is shifted to next
position.
* This results into virtual deletion of an element.
* By doing so memory space which was occupied by deleted element is wasted and
hence inefficient memory utilization is occur.
OVERCOME DISADVANTAGE OF LENEAR QUEUE:
To overcome disadvantage of linear queue,circular queue is use.
We can solve this problem by joining the front and rear end of a queue to make the
queue as a circular queue.
Circular queue is a linear data structure
It is also called as"Ring buffer".
Items can inserted and deleted from a queue in 0(1) time.
REPRESENTATION OF QUEUES
USING AN ARRAY
USING AN LIST
TYPES OF QUEUE:
CIRCULAR QUEUE
DEQUEUE
PRIORITY QUEUE
CIRCULAR QUEUE:
* A queue, in which the last node is connected back to the first node to form a
cycle, is called as circular queue.
* Circular queue are the queues implemented in circular form rather than in a
straight line.
* Circular quees overcome the problem of unutilized space in linear queue
implemented as an array.
* The main disadvantage of linear queue using array is that when elements are
deducted from the queue.
CIRCULAR QUEUE IMPLEMENTATION:
* After reaches the last position, i.e.MAX-1 IN ORDER to reuse the vacant
positions, we can bring rear backto the 0th position, if it is empty,
and continue incrementing rear in same manner as earlier.
* Thus rear will have to be incremented circularly.
* For deletion, front will also have to be incremented circularly.
ENQEUE OPERATION ON CIRCULAR QUEUE;
STEP 1: check for queue full
if rear = max -1 and front = 0 or if front =rear+1 then
circular queue is full and insertion operation is not possible.otherwise
go to step 2
STEP 2: Check position of rear pointer
if rear =max-1
then set rear =0 otherwise increment rear by 1.
rear=(rear+1)% MAX
STEP 3: Insert element at the position pointer by rear pointer
q[rear]=Data
STEP 4: Check the position of front pointer
if front=(-1) then set front as 0.
DEQUEUE OPERATION ON CIRCULAR QUEUE:
STEP 1: Check for queue empty if (front = -1)
then circular queue is empty and deletin operation
is not possible otherwise go to step 2.
STEP 2: Check for position of front and rear pointers.
if front= rear then
Data =q[front];
set front = rear -1
STEP 3: Check position of front
if front = MAX-1
Data = q[front];
then set front=0;
otherwise
data =q[front];
front = (front+1)%MAX
PRIORITY QUEUE:
A priorty queu is a collection of elements where each element is assigned a
priority and the order is whcih elements are deleted and processed is determined
from the
following rules:
* An element o fhigher priority is processed before any element of lower priority .
* Two element with the same priority are processed accordingly to the order in
which they are added to the queue.
an example where priority queue are used is in operating systems.
The operating system has to handle a large number of jobs,
These jobs have tobe properly scheduled.
The operating system assigns priorities to each type of job.
The jobs are placed in a queue and the jon with the highest priority will be exeutd
first.
THE PRIORITY QUEUE IMPELMENTATION:
the priority queue is again implemented in two way.
1. array\sequential representation.
2. Dynamic\linked representation.
in priority queue node is divided into three parts.
info
priority
next
