Recurrsion,Stack,queue,
linked list
Jayashree M Oli ECE department
Brief discussion on Data structure
What is data?
It is entity that is utilized in calculation or manipulation
Types of data-
two types
1)Numerical data
2)Alphanumerical data
These two data types specify the nature of data item that undergo certain
operations
Integers, floating point- numerical data type
Strings constants, character constants- alphanumerical data type
Jayashree M Oli ECE department
contd
These data items when collected for processing by programmer has to be
stored in computer memory.
The process of storing information in computer memory is called
representation
Data may be single or it may be set of values
The data whether it is single value or a group of values to be processed must
be organized in a particular fashion.
This organization leads to structuring of data, and hence we are studying data
structures.
[Link]
[Link]
[Link] on data structures
Jayashree M Oli ECE department
contd
Data structure is a way of organizing all data items that consider not only the elements stored
but also their relationship to each other
Data structure mainly specifies following four things
1. Organizing of data
2. Accessing methods
3. Degree of associativity
4. Processing alternatives for information
Data structures are building blocks of [Link] of data structure stress on two main
things
[Link] data structure must be rich enough in structure to reflect the real relationship
existing between the data
2. The structure should be simple so that we can process data effectively, whenever required
Jayashree M Oli ECE department
Identification of inherent data structure is vital in nature
Structure of input and output data can be used to derive the structure of a
program.
Data structure affects the design of both structural and functional aspects of
a program.
Algorithm + data structure= program
To develop a program of an algorithm we should select an appropriate data
structure.
Jayashree M Oli ECE department
Classification of data structure
Data
structure
Primitive data Non-primitive
structure data structure
Floa char poin arrays
i lists files
ting ters
n
t poin
e t Linear list Non linear
g list
e
r stacks grap trees
queues
hs
Jayashree M Oli ECE department
Primitive data structure
Basic data structure and directly operated upon by machine instructions
Have different representations on different computers
Examples- integer, char….
Non primitive data structures
Sophisticates data structures
These are derived from primitive data structures
They emphasize on grouping same type(homogeneous) or
different(heterogeneous) data items
Examples- array ,list etc
Jayashree M Oli ECE department
Array
Can be defined as finite number of identical data items
So we may have array of integers, array of floating numbers or character
Features
Elements of array can be accessed by index set consisting of consecutive
numbers
Example index, i= { 0,1,2….n} index In starts with 0
The elements of array are stored in consecutive memory locations
No of elements that are stored is called the size of array.
The size of array is computed size= upperbound- lowerbound+1
Upper bound is called-largest index
lower bound is called -smallest index
Individual element are specified in array as x[1],x[2],x[3]…….
Jayashree M Oli ECE department
Operations performed on array
Create- creating empty array
Retrieve- accessing a particular element as and when required using index
Store- store new data item
Jayashree M Oli ECE department
Lists
Lists are most commonly used primitive data structures
A list can be defined as the ordered set containing variable number of data
items
Lists preserve the adjacency relationship among all data items. This means it
is possible for us to determine its successor and predecessor item
Example 1. Roll no of EAC students { 1,2,3…..}
2. The years the india and pak fought { 1962, 1971,1999}
3. days of week { sun,mon,tue……}
Jayashree M Oli ECE department
Differences between array and list
Array Lists
Set consisting of fixed no of data Ordered set consisting of a variable
items number of data items
No insertion and deletion Insertion and deletion operations
operations performed performed
Jayashree M Oli ECE department
Files
A file is collection of logically related information
It can be viewed as large list of records consisting of various fields
Example
A file consisting of student information
Reg no, name , branch, percentage
A file consisting of employee of an organization
Emp_no, emp_name,designation, basic_salary, HRA, CCA, gross_salary
Files are always stored in secondary storage devices such as floppy disks, hard
disks
Files are accessed sequentially or directly
Jayashree M Oli ECE department
Operations on data structures
The design of efficient data structure must take operations to be performed
on the data structure into account.
Example- Consider a data structure consisting of a set of data items. The data
structure is to be manipulated in a number of major program functions.
After evaluating the operations to be performed on the data structure an
abstract data type is defined to use it in subsequent programs.
Most commonly used operations
[Link]- reserving memory by declaration
2. Destroy- destroys memory malloc(),free()
3. Selection- accessing particular element
4. Updating- updates or modifies data
Jayashree M Oli ECE department
LIST ADT------------examples
public interface List<E> {
public void clear();
public void insert(E item);
public void append(E item);
public E remove();
public void moveToStart();
public void moveToEnd();
public void prev();
public void next();
public int length();
public int currPos();
public void moveToPos(int pos);
public E getValue();
}
Jayashree M Oli ECE department
Other operations include
1. Searching
2. Sorting
3. Merging
Jayashree M Oli ECE department
STACK
Stack
Representation of stack
Operation of stack
Algorithms
Applications of stack
Infix , postfix , prefix
Conversion from infix to postfix
Evaluation of postfix expression
Jayashree M Oli ECE department
Stack
Non primitive linear data structure
It is ordered list in which addition of new data item or deletion of already
existing data item is done in one end
Addition is always done at top of stack
LIFO
Stack create-----Top changes-------it is most accessible element
base remains fixed-------least accessible element
Jayashree M Oli ECE department
Creation , addition , deletion of stack
Jayashree M Oli ECE department
STACK FULL(overflow)- error
STACK EMPTY(underflow)—error
PUSH
POP
Examples of stack
1. A man carrying suitcase on head
2. A stack of plates in cafeteria
3. A biscuits in biscuit bundle
Jayashree M Oli ECE department
Real applications of stack in computer science is listed below
1. Recursion - return address, frame pointer
2. Keeping track of function call
3. Evaluation of expression
4. Reversing the character
5. Servicing hardware interrupt
6. Solving combinational problems using backtracking – rat in maze
Jayashree M Oli ECE department
Representation of stack
Stack can be represented in computer memory in two types
1. Static representation-AImplemented using array in cstatic stack is
implemented using an array in
2. Dynamic representation- implemented using a linked list in C
Static representation-
Is array representation
Stack is created by statement
Int stack [MAXSIZE]
We can use macro
# define MAXSIZE 10
Jayashree M Oli ECE department
Operations on stack
operation description restriction
Push Add new data item on to No of data items should not
the stack exceed MAXSIZE
Pop Deletes data item from the No of data items on the
top of stack stack should not go beyond
0
Top Returns the value of the
item at the top of the stack
Stack_empty Returns true if stack is
empty else false
Stack_full Returns true if stack full
else false
Jayashree M Oli ECE department
Algorithms for push and pop
Push operation
Push is function used to add data item on stack
Push( int stack[] , int MAXSIZE, int top)
{
int item
if (top= =MAXSIZE - 1) // CHECK FOR OVERFLOW
{ printf ( “stack is full \n” );
return;
}
else
{
printf( “ enter the elements to be inserted \n”);
scanf(“%d”, & item)
top=top+1; /* increment top */
stack[top] =item; /* insert item */
}
}
Jayashree M Oli ECE department
Pop operation
Pop is function used to delet data item on stack
Pop( int stack[] , int top)
{
int item;
if (top= =- 1) // CHECK FOR underflow
{ printf ( “stack is empty \n” );
return;
}
else
{
item =stack[top]; /* delete item */
top=top-1; /* increment top */
}
}
Jayashree M Oli ECE department
Applications of stack- keep track of function calls
# include <stdio.h>
funct2( int x)
main ()
{
{
int y,z;
int i=10,j;
y=x+10;
j=funct1(i);
z=funct3(y);
printf(%d”,j);
return(z);
}
}
funct1( int k)
funct3(int a)
{
{
int m=20,n;
int b;
n= funct2(m);
b= a* 5;
return(n* k)
return(b);
}
}
Jayashree M Oli ECE department
Jayashree M Oli ECE department
Infix , postfix,prefix expression
An expression in any programming language is combination of operands and
operations
Operands may be of int,float,double
Operations may be of arithmetic,logical,bitwise etc
Here we study arithmetic operations
Three ways
1. infix
It is the form of an arithmetic expression in which we fix place the arithmetic
operator in between the two operands
Example
A + B, A-B, A*B, A/B----------------A,B are operands
(A+B)-C, A+(B *C), (A/B)+C--------------A,B,C ARE operands
Parentheses impose a precedence of operation, i.e order of operation
Jayashree M Oli ECE department
Post fix
it is form of arithmetic expression in which we fix arithmetic operator after its
two operands
infix postfix Prefix
A+B AB+ +AB
A-B AB- -AB
A*B AB* *AB
A/B AB/ /AB
Jayashree M Oli ECE department
Arithmetic operations left to right
exponential operation is evaluated from right to left
parenthesis is evaluated first
OPERATION OPERATORS PRECEDENCE
EXPONENTIAL ^ Highest
MULTIPLICATION/DIVISION *,/
ADDITION/SUBTRACTION +, - lowest
Jayashree M Oli ECE department
A+B*C ABC*+
A+B-C AB+C-
(A+B)*C AB+c*
Jayashree M Oli ECE department
A+B*C---infix form
A+(BC*)-------operands with * are written in postfix form
A(BC*)+-----------postfix would result
ABC*+ -----------remove parentheses
Solve given example 5+(4-3)*8
Jayashree M Oli ECE department
1. 5+(4-3)*8
2. 43- ---------------------consider this term as T
3. 5+T*8
4. T8* ---------------------------------consider this term as F
5. 5+f
6. 5f+
7. 5(T8*)+ -----------------------------place the original term of F
8. 5((43-)8*)+ ------------------------------------remove paranthesis
9. 543-8*+ = 13
10. If in the above expression parenthesis were not present then ?
Jayashree M Oli ECE department
1. 5+(4-3)*8
5+4-3*8
38*------highest precedence
54+ --------------- + appears before
54+38*-
Jayashree M Oli ECE department
[Link]
form of expression in which we place arithmetic operator before
its two operands.
infix Prefix
A+B +AB
A-B -AB
A*B *AB
A/B /AB
Jayashree M Oli ECE department
solve
infix Prefix
A+B*c
A+b-c
(3+4)*(8-9)
x/y^z+A
Jayashree M Oli ECE department
solution
Jayashree M Oli ECE department
SOLVE
A*B+C/D
Arithmetic expression is evaluated from left to right
exponential operation is evaluated from right to left
parenthesis is evaluated first
Jayashree M Oli ECE department
Solution
A*B+C/D
+* AB / CD---------------pre
Jayashree M Oli ECE department
Pre index
A*B --------*AB-----------T
T+ C/D---------/CD------S
T+S----------+TS----------R
R=+((*AB)(/CD)) PARANTHESIS FOR CONVENIENCE
+*AB/CD
Post index
AB * CD / + ------------post
Jayashree M Oli ECE department
Solve
Transfer the following expression to their postfix and prefix expression
A-B/C
(A+B) * (C-D)/E-F
A^B^C*D
TRANSFER THE FOLLOWING TO INFIX
+*ABC
-/*A+BCDE
Jayashree M Oli ECE department
Post fix prefix
A-B/C ABC/- -A/BC
(A+B) * (C-D)/E-F
A^ B ^ C * D
Jayashree M Oli ECE department
HW
Transfer the following expression to their postfix and prefix expression
A-B/C
(A+B) * (C-D)/E-F AB+ *
A^B^C*D
TRANSFER THE FOLLOWING TO INFIX
+*ABC
-/*A+BCDE
Jayashree M Oli ECE department
Conversion from infix to postfix
Following assumption is made
[Link] single character (letter or digit) operands are allowed
[Link] +,-,*,/ operators are considered, unary minus is excluded
3. Expression is error free
Algorithm
Scan the infix expression from left and right
a) If scanned symbol is left parenthesis , push it onto the stack
b) If scanned symbol is an operand, then place directly in the postfix expression
c) If scanned symbol is right parenthesis , then pop all the items from the stack and
place them in postfix expression till we get matching left parenthesis
d) If scanned symbol is an operator ,then go on removing all the operators from the
stack and place them in postfix expression . If and only if the precedence of the
operator which is on the top of the stack is greater than or equal to the
precedence of scanned operator else push scanned operator on stack
Jayashree M Oli ECE department
Recursion
Definition
It is powerful programming concept
It helps the programmer to carry out certain task repeatedly for a known
number of times or as long as desired condition is true
It is modular programming technique
Recursion is the name given to the ability of function to call itself , until
desired condition is satisfied.
There must be an exclusive stopping condition statement within body of a
recursive function . Otherwise function enters infinite loop.
Jayashree M Oli ECE department
contd
When a recursive program is taken for execution, the recursive function calls
will not be executed immediately.
They are pushed on stack as long as stopping condition is encountered .
When stopping condition is encountered the recursive function calls are
removed (poped) from stack in the reverse order and executed one by one.
How does recursive function handles storage of variables
Each time a function is called recursively, storage for a new copy of each
function’s automatic variables is allocated
However only one copy of storage is allocated for static variables
Jayashree M Oli ECE department
Example- let us consider to display four multiples of
using recursive function
# include <stdio.h>
Main( )
{
int number=10;
Multiple _of_10(number);
Output
} 10000
Multiple_of_10 (int n) /*recursive function */ 1000
{ 100
if (n<10000) 10
{ multiple_of_10 (n*10);
}
printf(“%d\n”,n);
}
Jayashree M Oli ECE department
Types of recursive call
direct indirect
Function_1
Function_1( )
{
{
function_2( )
function_1( )
}
}
Function_2( )
{
function_1( )
Jayashree M Oli ECE department
#include <stdio.h>
Main ( ) Factorial of number
{
int n,f;
printf(“enter the number \n”)
scanf(“%d”, &n)
f=fact(n)
printf(“factorial of %d= %d\n”, n,f);
}
/* recursive function for factorial*/
Int fact(int m)
Output
{ Enter the number
int factor; 5
If (m=0) Factorial of 5=120
return(1)
Else
factor=m*fact(m-1);
Return(factor)
Jayashree M Oli ECE department
}
HW
Write a program to accept two positive integers and find their gcd using
recursive function
Jayashree M Oli ECE department
Efficiency of recursion
Always it is not good to use recursive method
It is inefficient in terms of memory utilization and execution speed as
compared to non-recursive (iteration )programming approach
Choice of recursive lies tradeoff between performance and its simplicity
Recursive function is easier to implement and maintain
Datastructures- queues,linked list ,trees etc implement recursive method
Jayashree M Oli ECE department
differences
iteration recursion
Process of executing a statement Name given to technique of
or a set of statements repeatedly defining something in terms of
until some specified condition is itself
satisfied
Their will be stopping condition
Process involves four clear parts, within the body of the recursive
initialization,decisions, function
computation and updation
Worse as compared to iterative
More efficient in terms of memory
It is defined as a function to call
utilization and speed
and recall itself
For,while,do-while are used
Jayashree M Oli ECE department
queues
Definition
Representation
Operation
Algorithms
Circular queues
Double ended queues
Jayashree M Oli ECE department
definition
A queue is a non primitive linear data structure
It is ordered homogeneous group of elements in which elements are added at
one end called the rear and deleted from other end called front
FIFO
The order they are inserted in the same order they are removed
A queue does not permit access to any element except the one least recently
added but not yet removed
Once an element has been removed it is lost from the queue structure and
cannot be accessed again, except by adding it once again
10 20 30 40 50 60
Jayashree M Oli ECE department
Features
Size-6
Element 10-first to be removed
Element 60- last to be deleted
Examples
Printing queue- multiple print job sent to printer
Time sharing computer system
Representation of queue
Two ways
1. Static(array)
2. Dynamic(linked list)
Jayashree M Oli ECE department
An array based representation of queue involves during a one dimensional
array of some specified size
The array representation of queue needs two indices: FRONT and REAR which
indicate position of front and rear ends
Declaration of array in C
Int queue[MAXSIZE]
Queue is name of array
MAXSIZE –no of elements
Once a queue with specified size is created then addition of new element at
the rear end and deletion of an element from the front end can be performed
Two indices to be maintained front and rear- helps in deleting and inserting
data items
Jayashree M Oli ECE department
To insert the element in queue
Increment REAR index by 1 and place the element in the rear position
Delete the element in queue
Deletion is done by taking element from front position and then front is
incremented by 1
Assumptions
Intial front=0;
Initial rear=0;
FRONT=REAR if the queue is empty
Jayashree M Oli ECE department
Basic operations on queue
operation description restriction
Create queue It creates new empty queue
Qinsert Inserts new data item at the rear of Queue must not be full
queue
Qdelete It deletes and then return the data Queue must not be empty
item at the front of the queue
Queue full It returns true if the queue is full
otherwise returns false
Queue empty It returns true if the queue is empty .
Otherwise return false
Jayashree M Oli ECE department
Program to insert element into queue
Jayashree M Oli ECE department
Insert element
Void insert ( )
{
if (capacity= = rear)
{
printf(“ queue is full”);
}
else
{
int element;
printf(“ enter element”)
scanf(element)
queue[rear]=element;
rear++;
}
Jayashree M Oli ECE department
Displaying the element in queue
Void display( )
{
if ( front== rear)
{
printf(“queue is empty”)
}
else
printf( “ queue elements”);
for( i=front; i< rear; i++)
{
printf(“%d\n”, queue [i]);
}
}
}
Jayashree M Oli ECE department
Delete queue elements
Void delete ( )
{
if(rear= =front)
{
printf(“Queue is empty”);
}
else
{
printf( “deleted%d”, queue[front]); 10
for( i=0; i<rear-1; i++)
{
queue[i]=queue[i+1];
}
rear--;
}
}
Jayashree M Oli ECE department
Circular queue
There are two problems associated with ordinary queues
1. Time consuming
2. Queue is shown full
Why time consuming
Every time you delete element- maxsize-1 positions need to be moved one
position to the left of the queue in computers
If queue size is too large then moving elements in queue is time consuming
process.
Jayashree M Oli ECE department
Circular queue
Definition
Operations
Front ( ), rear( ), enqueue( ), dequeue( )
Applications
Advantages and disadvantages
Jayashree M Oli ECE department
Circular queue
Jayashree M Oli ECE department
Representation of queue
Jayashree M Oli ECE department
Operations of circular queue
From the front end of queue
Jayashree M Oli ECE department
Enqueue()
Jayashree M Oli ECE department
Noitem= Noitem+1
}
}
Jayashree M Oli ECE department
Jayashree M Oli ECE department
Front=Front+1;
}
}
Jayashree M Oli ECE department
Jayashree M Oli ECE department
Jayashree M Oli ECE department
Jayashree M Oli ECE department
Disadvantages of circular queue
Jayashree M Oli ECE department
Applications of circular queue
Jayashree M Oli ECE department
Linked lists
Stack and queues- employed arrays to represent them in computer memory
When we choose array representation(sequential representation)it is necessary to
declare in advance the amount of memory to be utilized.
We do this by declaring the maximum size of an array.
But when this method is used of array representation, all the memory may not be
utilized.
Even though memory locations are allocated but they may be not used.
This leads to wastage of memory.
As memory is important resource it should be handled efficiently.
Jayashree M Oli ECE department
solution
If we allot the memory before execution of a program, it is fixed and cannot
be changed.
we have to adapt an alternative strategy to allocate memory only when it is
required
There is special data structure called linked list that provide a more flexible
storage system and it does not require use of arrays
Jayashree M Oli ECE department
Topics to be discussed
Definition-linked list
Components of a linked list
Representation of linked list
Types of linked list
Basic operations performed on linked list
Singly linked list
Doubly linked list
Circular doubly linked list
Linked representation of stacks and queues
Jayashree M Oli ECE department
Linked list
It is nonsequential collection of data items
Concept used is simple
For every data item in the linked list, there is an associated pointer that
would give the memory location of the next data item in the linked list
The data item in linked list are not in consecutive memory location, they may
be anywhere in the memory.
Accessing data items in the linked list is easier as each data item contained
within itself the address of the next data item
Jayashree M Oli ECE department
advantages
Linked lists are dynamic data structures-
they can grow or shrink during the execution of a program
Efficient memory utilization-
memory is not preallocated, allocated whenever required and deallocated
whenever not required.
Insertion and deletion are easier and efficient-
linked list provide flexibility in inserting a data item at a specified position
and deletion of data item for a given position
Many complex applications can be easily carried out with linked list
Jayashree M Oli ECE department
Disadvantages
More memory
Access to an arbitrary data item is little bit cumbersome and also time
consuming
Jayashree M Oli ECE department
