1

BSc/PMCs/RPCs/ 21CS2C05 /UNIT I

Introduction to Data Structures
Data Structure is the logical or mathematical model of a particular organization of data.
Data Structures can be classified as
1. Primitive data structures
2. Non-primitive data structures
3.
1. Primitive data structures: Data structures that are readily available in a
programming language. They can be operated by the programming instructions. The
storage representation (memory representation) and the possible operations for these
types of structures are predefined and the user cannot change this.
The different primitive data structures are integer, float, double, and
character.
2. Non-primitive data structures: Data structures that are not readily available in a
programming language. The storage representation and the possible operations for
these types of data structures can be defined by the user.
The different non-primitive data structures are arrays, stacks, queues ,and
linked lists.

Non primitive data structures are further classified into two types.
a) Linear data structure- In a linear data structure, the memory representation of
the elements of the data structure is continuous.
The different types of linear data structures are arrays, stacks, queues and linked
lists.
b) Non-linear data structure: In a non-linear data structure, the memory
representation of the elements of the data structures is non-continuous. The
elements are stored in a parent child relationship, where parent element is called
as root node and child element is called as leaf node.
The different types of non-linear data structures are graphs and trees.
Abstract Data Type: Abstract Data type (ADT) is a type (or class) for objects
whose behavior is defined by a set of values and a set of operations. The definition of
ADT only mentions what operations are to be performed but not how these
operations will be implemented. It does not specify how data will be organized in
memory and what algorithms will be used for implementing the operations. It is
called “abstract” because it gives an implementation-independent view.

Time-space tradeoff: Space-Time tradeoff in computer science is basically a

problem-solving technique in which we solve the problem:
 2

• Either in less time and using more space, or

• In very little space by spending more time.

The best algorithm is the one that helps to solve a problem that requires less space in
memory as well as takes less time to generate the output. But in general, it is not
always possible to achieve both of these conditions at the same time.
Asymptotic Notation

Asymptotic Notation is used to describe the running time of an algorithm - how

much time an algorithm takes with a given input, n. There are three different
notations: big O, big Theta (θ), and big Omega (Ω). Big (θ), is used when the
running time is the same for all cases, big-O for the worst-case running time, and
big-Ω for the best-case running time.

Operations on non-primitive data structures:

1. Traversing: It is the process of visiting each element exactly once to perform
some operation.
2. Insertion: It is the process of adding a new element to the data structure.
3. Deletion: It is the process of deleting an element from the data structure.
4. Searching: It is the process of searching of existence of an element among the
elements of a data structure.
5. Sorting: It is the process where elements of data structures are arranged in an
order.
6. Merging: It is the process of combining elements from two different data
structures into one data structure.
Complexity of algorithms
The complexity of an algorithm M is the function f(n) which gives the running time
and/or storage space requirement of the algorithm in terms of the size n of the input
data.
The complexity of an algorithm is usually discussed for three cases.
1. Worst case: the maximum value of f(n) for any possible input.
2. Average case: the expected value of f(n)
3. Best case: the minimum possible value of f(n)
 3

Linear arrays:

An array is a collection of variables of the same type that are referred to through a
common name. A specific element in an array is accessed by an index. In C++, all
arrays consist of contiguous memory locations. The lowest address corresponds to the
first element and the highest address corresponds to the last element. Arrays can have
from one to several dimensions.

The possible operations are arrays are:

1. Insertion of an element
2. Deletion of element
3. Searching for an element
4. Sorting the array of elements
5. Merging the array of elements

1. Insertion of element
An element can be inserted to an array either at the beginning of the array, or in a
required position.
Insert element at the beginning of the array.
Algorithm: insertbeg(a,ele) where a is an array of “n” elements and ele is the element to
insert.
Step 1: Start
Step 2 : for i=n to 0
Step 3: a[i+1]=a[i]
Step 4: a[0]=ele
Step 5: print “array elements after inserting”
Step 6: for i=0 to n-1
Step 7: print a[i]
Step 8: End
 4

Insert element at a required position

Algorithm: insertpos(a,ele,pos) where a is an array of “n” elements and ele is the
element to insert and pos is the position where the array element is to be inserted.
Step 1: Start
Step 2 : for i=n to pos
Step 3: a[i]=a[i-1]
Step 4: a[pos-1]=ele
Step 5: print “array elements after inserting”
Step 6: for i=0 to n+1
Step 7: print a[i]
Step 8: End

2. Deletion of element: An element can be deleted from an array either at the

beginning of the array, or in a required position.

Deletion of element at the beginning of the array

Algorithm: deletebeg(a) where a is an array of “n” elements and ele is the element to
insert.
Step 1: Start
Step 2 : for i=0 to n-1
Step 3: a[i]=a[i+1]
Step 4: print “array elements after deleting”
Step 5: for i=0 to n-1
Step 6: print a[i]
Step 7: End
 5

Deletion of element at a required position

Algorithm: deletepos(a,pos where a is an array of “n” elements, pos is the position for
which element has to be deleted.
Step 1: Start
Step 2: for i=pos-1 to n-1
Step 3: a[i]=a[i+1]
Step 4: print array elements after deleting
Step 5: for i=0 to n-2
Step 6: print a[i]
Step 7: End

Searching: A step-by-step procedure used to locate specific data in a data structure.

There are two types of Searching:
a) Linear Search: linear search or sequential search is a method for finding an
element within a list. It sequentially checks each element of the list until a match
is found or the whole list has been searched. If an element is found, its location
is displayed.

Algorithm Linear_Search(A, ele, N) – A is an array of N elements and ele is

the element to be searched in the array.
Step 1: loc=-1
Step 2: for i=0 to n-1 do
Step 3: if (ele=a[i]) then
Step 4: loc=i
Step 5: Goto step 6
[End of if]
[end of for loop]
 6

Step 6: if(loc>=0) then

Step 7:print ele “found in location”, loc
Step 8: else
Step 9: print ele “not found”
[endif]
Step 10: Exit
Advantages:
Simple to implement
Disadvantages:
The computational time is high.
Complexity: The complexity is O(n).

b) Binary Search: Find the middle element in the array. If the search key element is
matching with the element present in the middle position, the print element is
found. If the search key element is lesser than the middle element then continue
searching only in left of the middle element else continue searching only in right
of the middle element.
Algorithm Binary_Search(A,n,ele) where A is an array of "n" elements and
ele is the element to be searched.
Step 1: low=0
Step 2: high=n-1
Step 3: loc=-1
Step 4: while(low<=high)
Step 5: mid=(low+high)/2
Step 6: if (ele=a[mid])
Step 7: loc=mid
Goto step 12
 7

[end of if step 6]
Step 8: if (ele<a[mid]) then
Step 9: high=mid-1
Step 10: else
Step 11: low=mid+1
[ end of if step 8]
[ end of while step 4]
Step 12: if(loc>=0)
Step 13: print ele "found at location" loc
Step 14: else
Step 15: print ele "not found"
Step 16 : exit

Program to implement Binary Search

#include<iostream.h>
int binary_search(int *, int, int);// function prototype
int main()
{
int arr[10],i,n,ele,loc;
cout<<"Enter the number of elements"<<endl;
cin>>n;
cout<<"Enter the array elements"<<endl;
for(i=0;i<n;i++)
cin>>arr[i];
cout<<"Enter the element to be searched ";
cin>>ele;
loc=binary_search(arr,n,ele);
if(loc>=0) // element exists
cout<<ele<<" found at "<<loc+1<<endl;
else
cout<<ele<<" not found "<<endl;
return 0;
}
 8

int binary_search(int a[10],int n, int ele)

{
int low,high,mid;
low=0;
high=n-1;
while(low<=high)
{
mid=(low+high)/2;
if(a[mid]==ele)
{
return mid;
}
if(ele<a[mid])
high=mid-1;
else
low=mid+1;
}
return -1;
}

The complexity of the Binary Search:

Every comparison in the binary search reduces the number of possible elements
remaining for comparisons by a factor of 2. So the complexity is log2 n.

Explanation of binary search with examples

For a binary search to work, it is mandatory for the target array to be sorted. We shall
learn the process of binary search with a pictorial example. The following is our sorted
array and let us assume that we need to search the location of value 31 using binary
search.

First, we shall determine half of the array by using this formula −

mid = low + (high - low) / 2

Here it is, 0 + (9 - 0 ) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.
 9

Now we compare the value stored at location 4, with the value being searched, i.e. 31.
We find that the value at location 4 is 27, which is not a match. As the value is greater
than 27 and we have a sorted array, so we also know that the target value must be in the
upper portion of the array.

We change our low to mid + 1 and find the new mid value again.

low = mid + 1
mid = low + (high - low) / 2
Our new mid is 7 now. We compare the value stored at location 7 with our target value
31.

The value stored at location 7 is not a match, rather it is more than what we are looking
for. So, the value must be in the lower part from this location.

Hence, we calculate the mid again. This time it is 5.

We compare the value stored at location 5 with our target value. We find that it is a
match.
 10

We conclude that the target value 31 is stored at location 5.

Advantages:
Since the array is sorted, the time taken to search an element is lesser.

Disadvantages:
The array should be in sorted order. Either the array elements have to be entered in
sorted order, or after accepting the array elements they have to be sorted.

Sorting: The process by which the elements are arranged in ascending or descending
order.
There are various sorting techniques. They are
a. Bubble sort
b. Selection sort
c. Insertion sort
d. Merge sort
e. Shell sort
f. Heap sort
g. Quick sort
h. Radix sort
i. Bucket sort

Let us discuss Bubble sort.

Bubble sort: This is the most popular sorting method and also the simplest one.
This sorting algorithm is comparison-based algorithm in which each pair of adjacent
 11

elements is compared and the elements are swapped if they are not in order. This
algorithm is not suitable for large data sets as its average and worst case complexity are
of Ο(n2) where n is the number of items.
If the given array has to be sorted in ascending order, then bubble sort will start by
comparing the first element of the array with the second element, if the first element is
greater than the second element, it will swap both the elements, and then move on to
compare the second and the third element, and so on.
So Bubble sort is also called as "Sorting by exchange".
If we have total n elements, then we need to repeat this process for n-1 times.

It is known as bubble sort, because with every complete iteration the largest element in
the given array, bubbles up towards the last place or the highest index, just like a water
bubble rises up to the water surface.

Sorting takes place by stepping through all the elements one-by-one and comparing it
with the adjacent element and swapping them if required.
Example:

Algorithm Bubble_sort(A,n) where A is an array of "n" elements.

 12

Step 1: for i=1 to n-1

Step 2: for j=0 to n-i
[ Compare the adjacent elements]
Step 3: if (a{j]>a[j+1]) then
Step 4: t=a[j]
Step 5: a[j]=a[j+1]
Step 6: a[j+1]=t
[ end of if step 3]
[ end of for step 2]
[end of for step 1
Step 7. Exit

Program to implement Bubble Sort

#include<iostream.h>
int main()
{
int arr[10],i,j,n,temp;
cout<<"Enter the number of elements"<<endl;
cin>>n;
cout<<"Enter the array elements"<<endl;
for(i=0;i<n;i++)
cin>>arr[i];
cout<<"Sorted elements:"<<endl;
for(i=1;i<n;i++)
for(j=0;j<n-i;j++)
if (arr[j]>arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
for(i=0;i<n;i++)
cout<<arr[i]<<endl;
return 0;
 13

}
Analysis of Bubble sort, Selection sort, Insertion sort
The first pass of the algorithm results in n-1 comparisons and in the worst case may
result in n-1 exchanges also. The second pass results in n-2 comparisons and in the
worst case may result in n-2 exchanges. Contnuing the analysis we observe that as the
iterations or passes increases, the comparisons and exchanges decreases. Finally, the
total number of comparisons will be equal to
=(n-1)+(n-2)+(n-3)+........+2+1
=(n)*(n-1)/2
=O(n2)

Selection Sort: Selection sort is a sorting algorithm that selects the smallest element
from an unsorted list in each iteration and places that element at the beginning of the
unsorted list.

Working of selection sort:

Consider the following array elements:

12 1 0 8 3
A[0] A[1] A[2] A[3]] A[4]

Step 1: Assume A[0] as the smallest element.

12 1 0 8 3
A[0] A[1] A[2] A[3]] A[4]

Small=12
Loc=0

Step 2: Compare all the array elements with Small, if there is any element that is
smaller than Small, then swap Small and the smallest element. In the above
example, 0 is the smallest element, so swap 12 and 0. After swapping the array
elements are
 14

0 1 12 8 3
A[0] A[1] A[2] A[3]] A[4]

Step 3: The next element A[1]is taken as the smallest element. So Small is 1 and
loc=1.

0 1 12 8 3
A[0] A[1] A[2] A[3]] A[4]

Small=1
Loc=1

The array elements are scanned from A[2] and if any element is smaller than
Small i.e. 1, then Small and the smallest element are swapped. In the above
example, there is no smallest element compared to Small, so no swapping takes
place.

Step 4: Now A[2] is made is assigned to Small.

0 1 12 8 3
A[0] A[1] A[2] A[3]] A[4]

Small=12
Loc=2

Step 5: The array elements are scanned from A[3] and if any element is smaller
than Small i.e. 12, then Small and the smallest element are swapped. In the above
example, 3 is smallest element compared to Small, so swap 12 and 3, After
swapping the array elements are.

0 1 3 8 12
A[0] A[1] A[2] A[3]] A[4]

Step 6: Now A[3] is assigned to Small.

0 1 3 8 12
A[0] A[1] A[2] A[3]] A[4]

Small=8
Loc=3
 15

The array elements are scanned from A[4] and if any element is smaller than
Small i.e. 8, then Small and the smallest element are swapped. In the above
example there are no smaller elements smaller than 8, so no elements are swapped.

Finally the array elements are in sorted order.

0 1 3 8 12
A[0] A[1] A[2] A[3]] A[4]

Algorithm:

Algorithm selectionsort(arr,n) arr is a one dimensional array and n is the number

of elements.

Step 1: for i=0 to n-1 do

Step 2: small=arr(i)
Step 3: loc=i
Step 4: for j=i+1 to n do
Step 5: if(small>arr(j))
Step 6: small=arr(j)
Step 7: loc=j
[end if]
[ end of Step 4 for loop]
Step 8: temp=arr(i)
Step 9: arr(i)=arr(loc)
Step 10: arr(loc)=temp
[end of Step 1 for loop]
Step 11: exit

Program

#include<iostream.h>
#include<conio.h>>
void selectionsort(int *, int);
int main()
{
int n, arr[15],i;
cout<<"Enter the number of elements"<<endl;
cin>>n;
cout<<"Enter the array numbers"<<endl;
for(i=0;i<n;i++)
cin>>arr[i];
 16

cout<<"Array elements before sorting"<<endl;

for(i=0;i<n;i++)
cout<<arr[i]<<endl;
selectionsort(arr,n);
getch();
return 0;
}
void selectionsort(int a[15], int m)
{
int i,small,loc,j,temp;
for(i=0;i<m;i++)
{
small=a[i];
loc=i;
for(j=i+1;j<m;j++)
{
if(small>a[j])
{
small=a[j];
loc=j;
}
}
temp=a[i];
a[i]=a[loc];
a[loc]=temp;
}

cout<<"Array elements after sorting"<<endl;

for(i=0;i<m;i++)
cout<<a[i]<<endl;
}

Insertion Sort:

Insertion sort is a simple sorting algorithm that works similarly to the way you sort
playing cards in your hands. The array is virtually split into a sorted and an unsorted
part. Values from the unsorted part are picked and placed at the correct position in the
sorted part.

Working of Insertion Sort algorithm:

Consider an example: arr[]: {12, 11, 13, 5, 6}
 17

12 11 13 5 6
First Pass:
• Initially, the first two elements of the array are compared in insertion sort.

12 11 13 5 6
• Here, 12 is greater than 11 hence they are not in the ascending order and
12 is not at its correct position. Thus, swap 11 and 12.
• So, for now 11 is stored in a sorted sub-array.

11 12 13 5 6
Second Pass:
• Now, move to the next two elements and compare them

11 12 13 5 6
• Here, 13 is greater than 12, thus both elements seems to be in ascending
order, hence, no swapping will occur. 12 also stored in a sorted sub-array
along with 11
Third Pass:
• Now, two elements are present in the sorted sub-array which are 11 and 12
• Moving forward to the next two elements which are 13 and 5

11 12 13 5 6
• Both 5 and 13 are not present at their correct place so swap them

11 12 5 13 6
• After swapping, elements 12 and 5 are not sorted, thus swap again

11 5 12 13 6
• Here, again 11 and 5 are not sorted, hence swap again

5 11 12 13 6
• Here, 5 is at its correct position
Fourth Pass:
 18

• Now, the elements which are present in the sorted sub-array are 5,
11 and 12
• Moving to the next two elements 13 and 6

5 11 12 13 6
• Clearly, they are not sorted, thus perform swap between both

5 11 12 6 13
• Now, 6 is smaller than 12, hence, swap again

5 11 6 12 13
• Here, also swapping makes 11 and 6 unsorted hence, swap again

5 6 11 12 13
• Finally, the array is completely sorted.

Algorithm:
Algorithm insertionsort(arr,n) arr is a one-dimensional array of “n” elements and
n is the number of elements.

Step 1: for I = 1 to n-1 do

Step 2: key=arr(i)
Step 3: j=i-1
Step 4:while(j>=0 && arr(j)>key)
Step 5: arr(j+1)=arr(j)
Step 6: j=j-1
[ end of Step 4 while]
Step 7:arr(j+1)=key
Step 8: exit

Program
#include<iostream.h>
#include<conio.h>
void insertionsort(int*, int);
int main()
 19

{
int arr[10],i,n;
cout<<"How many elements to be stored"<<endl;
cin>>n;
cout<<"Enter the array elements"<<endl;
for(i=0;i<n;i++)
cin>>arr[i];
cout<<"Unsorted array elements:"<<endl;
for(i=0;i<n;i++)
cout<<arr[i]<<endl;
insertionsort(arr,n);
getch();
return 0;
}
void insertionsort(int arr[10], int n)
{
int i,key,j;
for(i=1;i<n;i++)
{
key=arr[i];
j=i-1;
while(j>=0 && arr[j]>key)
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;
}
cout<<"Sorted array elements"<<endl;
for(i=0;i<n;i++)
cout<<arr[i]<<endl;
 20

STACKS

A stack is a linear data structure in which an element may be inserted or deleted only at
one end, called the top of the stack. This means that the last item to be added to a stack
is the first item to be removed. Accordingly, stacks are also called last-in first-out
(LIFO) lists.

Array representation of stacks

The figure below shows the array representation of a stack in computer memory.

STACK
MAXSTK 5

Top 30
20
10

Here, STACK is a linear array and TOP is a variable that contains the location
of the top element of the stack. The variable MAXSTK gives the maximum number of
elements that can be held by the stack.

Operations on Stack

The operations that can be performed on stacks are:

• PUSH operation
 21

The steps involved in the PUSH operation are given below:

(a) Before inserting an element in a stack, we check whether the stack is full.
(b) If we try to insert the element in a stack, and the stack is full, then
the overflow condition occurs.
(c) When we initialize a stack, we set the value of top as -1 to check that the
stack is empty.
(d) When the new element is pushed in a stack, first, the value of the top gets
incremented, i.e., top=top+1, and the element will be placed at the new
position of the top.
(e) The elements will be inserted until we reach the max size of the stack.

POP operation

The steps involved in the POP operation is given below:

(f) Before deleting the element from the stack, we check whether the stack is
empty.
(g) If we try to delete the element from the empty stack, then
the underflow condition occurs.
(h) If the stack is not empty, we first access the element which is pointed by
the top
 22

(i) Once the pop operation is performed, the top is decremented by 1,

i.e., top=top-1.
(j) Display: Display the contents of stack.

Algorithm: PUSH (STK, TOP, MAXSTK, ITEM)

This algorithm pushes an ITEM onto a stack.

Step 1. [Stack already filled?]
IF TOP = MAXSTK then
Print “Overflow”
Return.
[End of step 1 IF structure]
Step 2. TOP = TOP + 1 [Increases TOP by 1]
Step 3. STK[TOP] = ITEM. [Inserts ITEM in new TOP position]
Step 4. Return
 23

Algorithm: POP(STK, TOP, ITEM)

This algorithm deletes the top element of STK and assigns it to the variable ITEM.
Step 1. [Stack has an item to be removed?]
If TOP = 0 then
Print “Stack Underflow”
Return.
[End of step 1 IF structure]
Step 2. ITEM = STK[TOP] [Assigns TOP element to ITEM]
Step 3. TOP = TOP – 1 [Decreases TOP by 1]
Step 4. Return

C++ Program for array implementation of stack

#include<iostream.h>
#include<conio.h>
#include<process.h>
#define STACKSIZE 5
class Stack
{
private:
int stk[STACKSIZE],top;
public:
Stack()
{
top=-1;
}
void push(int);
int pop();
void display();
};
void Stack::push(int item)
{
if(top==STACKSIZE-1)
{
cout<<"stack overflow";
return;
}
stk[++top]=item;
}

int Stack::pop()
 24

{
if(top==-1)
{
cout<<"stack underflow";
return -1;
}
return stk[top--];
}

void Stack::display()
{
int i;
if(top==-1)
{
cout<<"stack underflow";
return;
}
cout<<"Stack elements"<<endl;
for(i=top;i>=0;i--)
{
cout<<stk[i]<<"\t";
}
}

int main()
{
int ch,item;
Stack s;
clrscr();
for(;;)
{
cout<<endl<<"Stack operations"<<endl;
cout<<"1.PUSH"<<endl;
cout<<"2.POP"<<endl;
cout<<"3.DISPLAY"<<endl;
cout<<"4.EXIT"<<endl;
cout<<"Enter your choice"<<endl;
cin>>ch;
switch(ch)
{
case 1:cout<<"Enter item : ";
cin>>item;
s.push(item);
 25

break;
case 2:item=s.pop();
if(item!=-1)
cout<<"Popped item is "<<item;
break;
case 3:s.display();
break;
default:exit(0);
}
}
}

Applications of Stack

The various applications of stacks are

1. Conversion of expressions
Mathematical expressions in a program are written in infix form. These
expressions will be converted into equivalent machine instructions by the compiler
using stacks. An infix expression can be converted to prefix or postfix expression
using stacks.
2. Evaluation of expressions
An arithmetic expression represented in the form of either prefix, or postfix
expression can be easily evaluated.
3. Recursion
A function which calls itself is called a recursive function. Solutions to problems
such as tower of Hanoi, tree manipulations etc. can be implemented very efficiently
using recursion.

Conversion of Expressions

The sequence of operators and operands arranged as per the syntax of the language is
called an expression. An arithmetic expression can be represented in one of the
following ways.

1. Infix expression
2. Prefix expression
3. Postfix expression
Infix expression: The most common expression is infix expression. In an infix
expression, the operator symbol is placed between its two operands.
Ex: A + B C – D
 26

Prefix expression refers to the notation in which the operator symbol is placed
before its two operands. Prefix expression is also known as Polish expression named
after the Polish mathematician Jan Lukasiewicz.
Ex: +AB -CD
Postfix expression refers to the notation in which the operator symbol is placed
after its two operands. Postfix expression is also known as reverse Polish expression.
Ex: AB+ CD-

Conversion of Infix Expression to Postfix Expression

The computer usually evaluates an arithmetic expression written in infix notation

in two steps. First, it converts the infix expression to postfix expression, and then it
evaluates the postfix expression. In each step, the stack is the main tool to accomplish
the given task. First you will study conversion of infix expression to postfix expression
using operator precedence and associativity and then you will study conversion of infix
expression to postfix expression using stacks.

1. Conversion of Infix expression to Postfix Expression Using Operator

Precedence and Associativity
Ex: convert ((A + ( B – C) * D ^ E + F) to postfix expression

((A + ( B – C) * D ^ E + F) (B – C) has highest precedence

T1=BC-
T1
((A + T1 * D) ^ E +F) (T1 * D) has highest precedence
T2=T1D*
T2
((A + T2) ^ E + F) (A + T2) has highest precedence
T3=AT2+
T3
(T3 ^ E + F) (T3 ^ E) has the highest precedence
T4=T3E^
T4
(T4 + F)

We now convert (T4 + F) to postfix expression by repeated substitution

(T4 + F)
 27

T4F+

T3E^F+ Replacing T4 by T3E^

AT2+E^F+ Replacing T3 by AT2+

A T1D*+E^F+ Replacing T2 by T1D*

ABC-D*+E^F+ Replacing T1 by BC-

The equivalent postfix expression is ABC-D*+E^F+

Convert A+B*C to postfix expression.

B*C has multiplication operator, having more precedence than + convert B*C to BC*.
Now the expression becomes

A+BC*

ABC*+ is the postfix expression.

Convert (A+B)/(C-D) to postfix using arithmetic operator precedence and

associativity.

(AB+)/(CD-)

AB+CD-/ is the postfix expression.

Conversion of infix expression to postfix expression using stacks

In normal algebra we use the infix notation like a+b*c. The corresponding postfix
notation is abc*+. The algorithm for the conversion is as follows :

▪ Scan the Infix string from left to right.

▪ Initialize an empty stack.
▪ If the scanned character is an operand, add it to the Postfix string. If the
scanned character is an operator and if the stack is empty Push the
character to stack.
▪ If the scanned character is an Operator and the stack is not empty,
compare the precedence of the character with the element on top of
the stack (topStack). If topStack has higher precedence over the
scanned character Pop the stack else Push the scanned character to
 28

stack. Repeat this step as long as stack is not empty and topStack has
precedence over the character.

Repeat this step till all the characters are scanned.

▪ (After all characters are scanned, we have to add any character that the
stack may have to the Postfix string.) If stack is not empty add topStack to
Postfix string and Pop the stack. Repeat this step as long as stack is not
empty.
▪ Return the Postfix string.

Example :

Let us see how the above algorithm will be implemented using an example.

Infix String : a+b*c-d

Initially the Stack is empty and our Postfix string has no characters. Now, the first
character scanned is 'a'. 'a' is added to the Postfix string. The next character scanned is
'+'. It being an operator, it is pushed to the stack.

Postfix String

Stack

Next character scanned is 'b' which will be placed in the Postfix string. Next character is
'*' which is an operator. Now, the top element of the stack is '+' which has lower
precedence than '*', so '*' will be pushed to the stack.

Postfix String

Stack
 29

The next character is 'c' which is placed in the Postfix string. Next character scanned is
'-'. The topmost character in the stack is '*' which has a higher precedence than '-'. Thus
'*' will be popped out from the stack and added to the Postfix string. Even now the stack
is not empty. Now the topmost element of the stack is '+' which has equal priority to '-'.
So pop the '+' from the stack and add it to the Postfix string. The '-' will be pushed to the
stack.

Postfix String

Stack

Next character is 'd' which is added to Postfix string. Now all characters have been
scanned so we must pop the remaining elements from the stack and add it to the Postfix
string. At this stage we have only a '-' in the stack. It is popped out and added to the
Postfix string. So, after all characters are scanned, this is how the stack and Postfix
string will be :

Postfix String

Stack

End result :

• Infix String : a+b*c-d

• Postfix String : abc*+d-

Convert (A+B)/(C-D) to postfix using Stack.

Initially the Stack is empty and our Postfix string has no characters. Now, the first
character scanned is '('. '(' is added to the stack. The next character scanned is 'A'. It
being an operator, it is pushed to the postfix string.
 30

Postfix string
(

Stack

The next character is ‘+’, so push it to stack.

+
Postfix string
(

Stack

The next character is ‘B’ push it to postfix string.

AB

+
Postfix string
(

Stack

The next character is ‘)’, so pop all the elements until you get left parentheses.

AB+

Postfix string

Stack
 31

The next character is ‘/’, so add to the stack.

AB+

Postfix string
/

Stack

The next character is ‘(‘, so add to the Stack

AB+
(
/ Postfix string
Stack

The next character is C, an operand so add to the postfix string

AB+C

/ Postfix String

Stack

The next character is -, the scanned character is having less precedence than the
character at the top of the stack, so push it to stack.

AB+C

-
/ Postfix String

Stack
 32

The next character is operand D, so add to the postfix string.

AB+CD

-
Postfix String
/

Stack

The next character is ‘)’, so pop all the operators from the stack and add to the postfix
string, and the stack is empty.

AB+CD-/

Postfix String

Stack

So AB+CD-/ is the postfix string.

Convert A + B * C / D – E to postfix string.

Symbol Postfix Stack Rule

String
A A A is an operand so
push to postfix string
+ A + + is an operator, push to stack
B AB + B is an operand so push to postfix string
* AB +* The character ‘*’ has got more precedence than +, push * to
stack
C ABC +* C is an operand, so add to postfix string
/ ABC* /’+ The scanned character ‘/’ is having higher precedence than ‘*’,
so push ‘/’ and pop ‘*’
D ABC*D /+ D is an operand, so add to poststring
- ABC*D/+ - The top most character ‘/’ has got more precedence than -, so pop out /
and +, push ‘-‘ character
E ABC*D/+ - The character E is an operand, so put to postfix string , end of string is
E reached, so pop out ‘-‘ and add to postfix string
ABC*D/+E-
 33

The precedence values of symbols in the stack and input expression are given in the
table below.

Symbols Stack precedence Input precedence Associativity

+, - 2 1 Left
*, / 4 3 Left
^ 5 6 Right
Operands 8 7 Left
( 0 9 Left
) - 0 -
# -1 - -

Evaluation of a Postfix Expression

Algorithm: EvalPostfix(P, STACK,VALUE)

This algorithm finds the value of an arithmetic expression P written in postfix

notation.
Step 1. Scan P from left to right and repeat steps 2 and 3 for each element of P
until the end of input.
Step 2. If an operand is encountered, put it on STACK.
Step 3. If an operator op is encountered, then,
(a) Remove the top two elements from STACK. Let A be top element
and B be the next-to-top element.
(b) Evaluate B op A
(c) Place the result of (b) back on stack.
[End of If structure]
[End of step 1 loop]
Step 4. Set VALUE equal to the top element on STACK.
Step 5 Return.

Program to evaluate a postfix expression using Stack

#include<iostream.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
float compute(char symbol,float op1,float op2)
{
 34

switch(symbol)
{
case '+':return op1+op2;
case '-':return op1-op2;
case '*':return op1*op2;
case '/':return op1/op2;
case '^':return pow(op1,op2);
}
}
int main()
{
float s[20],op1,op2,res;
int top=-1,i,len;
char postfix[30],symbol;
clrscr();
cout<<"enter a postfix expression:"<<endl;
cin>>postfix;
len=strlen(postfix);
for(i=0;i<len;i++)
{
symbol=postfix[i];
if(isdigit(symbol))
{
s[++top]=symbol-'0';
}
else
{
op2=s[top--];
op1=s[top--];
res=compute(symbol,op1,op2);
s[++top]=res;
}
}
res=s[top];
cout<<"result="<<res<<endl;
getch();
return 0;
 35

}
Recursion

A function which calls itself is called as a recursion function.

Why recursive functions

Recursive function allows you to divide your complex problem into identical
single simple cases which can be handled easily. This is also a well-known computer
programming technique: divide and conquer.
In general recursive functions must have two parts, a base case (terminating
case) which handles an input which can be solved without a recursive call and a
recursive case which calls the function again .
Base case: The case for which the solution can be stated non-recursively
Recursive case: The case for which the solution is expressed in terms of a smaller
version of itself.
Warning of using recursive function
Recursive function must have at least one exit condition that can be satisfied.
Otherwise, the recursive function will call itself repeatedly.

A simple example of recursion is mathematical definition of a factorial.

5! =5 * 4!

=5*4*3!

=5*4*3*2!

=5*4*3*2*1!

=5*4*3*2*1*0!

=120

In general the solution for finding the factorial can be written as,
 36

In this, if n=0 , factorial is 1 and the solution is expressed in a non-recursive way.

This is the base case.

If n>0, the solution is expressed in terms of itself in a simpler way ie n* (n-1)!.

This is the recursive case.

/* C++ program to find the factorial of a given number using recursive function */
#include<iostream.h>
#include<conio.h>
int main()
{
int fact(int);
int n;
cout<<“Enter a number : ”;
cin>>n;
cout<<“Factorial of the number is ”<<fact(n); // Function call
getch();
return 0;
}

int fact(int n)
{
if (n==0) //base case
{
return 1;
}
return n*fact(n-1); //recursive case
}

A C++ program to find the sum of 1 to N natural numbers recursively

Let us first define the problem,

If N=1 then sum is 1 base case
If N>1 then sum= N+ sum(N-1) recursive case

#include<iostream.h>
 37

#include<conio.h>
int sum(int);
int main()
{
int n;
cout<<“Enter the number : ”;
cin>>n;
cout<<“Sum of numbers from 1 to N is”<<sum(n); // Function call
getch();
return 0;
}

int sum(int m)
{
if (m==1) //base case
return 1;
return m+sum(m-1); //recursive case
}

Nesting of Functions

A sub program calling another subprogram directly or indirectly is called nesting of

functions.

A C++ program to find the LCM of 2 numbers.

#include<stdio.h>
#include<conio.h>
int GCD(int,int); //Function prototype of GCD
int LCM(int ,int);
int main()
{
int a,b,lcm;
clrscr();
cout<<“Enter the two numbers : ”;
cin>>a>>b;
lcm=LCM(a,b); //Function call
cout<<“The LCM of 2 numbers is ”<<lcm;
getch();
return 0;
}

//Function definition
 38

int LCM(int x,int y)

{
int prod;
int l;
prod=x*y;
l=prod/GCD(x,y);
return (l);
}

int GCD(int m,int n)

{
int gcd;
while(m!=n)
{
if (m>n)
m=m-n;
else
n=n-m;
}
gcd=m;
return(gcd);
}

In this example the main program calls the function LCM with two arguments a and b
which are taken by x and y in LCM().

The LCM( ) function in turn requires GCD of two numbers to find lcm.So it calls GCD(
) function with arguments x and y which are taken as m and n by GCD( ) .

GCD() calculates gcd and sends it to LCM() .LCM() used the value to calculate lcm
and returns it to main().

This process of a sub function calling another sub function is called nesting of
functions.

Fibonacci sequence
The Fibonacci sequence (usually denoted by F0, F1, F2, F3, … ) is as follows
0, 1, 1, 2, 3, 5, 8, 11, 13, …
That is F0 = 0 and F1= 1 and each succeeding term is the sum of the two preceding
terms. A formal definition of this function is as follows:
 39

/* C++ program to find nth Fibonacci number */

#include<iostream.h>
#include<conio.h>
int fib(int n)
{
if(n==0)
return 0;
if(n==1)
return 1;
return fib(n-2) + fib(n-1);
}

int main()
{
int n;
clrscr();
cout<<“Enter n : “;
cin>>n;
cout<<“fib(“<<n<<”) =”<<fib(n);
getch();
return 0;
}

Towers of Hanoi
Suppose three pegs, labeled A, B, and C, are given, and suppose on peg A there are
placed a finite number of disks say n with decreasing size. The object of the game is to
move the disks from peg A to peg C using peg B as auxiliary. The rules of the game are
as follows:
1. Only one disk may be moved at a time. Specifically, only the top disk on any
peg may be moved to any other peg.
2. At no time can a larger disk be placed on a smaller disk.

Algorithm: Tower(N, BEG, AUX, END)

This algorithm gives a recursive solution to the towers of Hanoi problem for N
disks.
1. IF N = 1 then
Write: Move disk from BEG to END
 40

Return
[End of step 1 IF structure]
2. [Move N - 1 disks from peg BEG to peg AUX]
call Tower(N – 1, BEG, END, AUX)
3. Write: Move disk from BEG to END
4. [Move N - 1 disks from peg AUX to peg END]
call Tower(N – 1, AUX, BEG, END
5. Return

One can view the solution as a divide-and-conquer algorithm, since the solution for n
disks is reduced to a solution for n – 1 disks and a solution for n = 1 disk.

The schematic diagram for recursive solution for Towers of Hanoi

C++ program for tower of Hanoi problem

#include<iostream.h>
#include<conio.h>

void tower(int n, char BEG, char AUX, char END)

 41

{
if(n == 1)
{
cout<<"Move disk from "<<BEG<<" to "<<END<<endl;
return;
}
/* Move n-1 disks from BEG to AUX */
tower(n-1, BEG, END, AUX);

cout<<"Move disk from "<<BEG<<" to "<<END<<endl;

/* Move n-1 disks from AUX to END */

tower(n-1, AUX, BEG, END);
}

int main()
{
int n;
clrscr();
cout<<"Enter the number of disks : ";
cin>>n;
tower(n,'A','B','C');
getch();
return 0;
}

QUEUES
A queue is a linear list of elements in which deletions can take place at one end, called
the front, and insertions can take place only at the other end, called rear. Queues are
also called first-in first-out (FIFO) lists, since the first element in a queue will be the
first element out of the queue.

Representation of Queues in Computer Memory

Queues may be represented in the computer memory in various ways, usually by means
of one-way lists or linear arrays. Figure below shows the array representation of queues.

1 2 3 4 5
FRONT: 1 10 20 30
REAR: 3

QSIZE: 5 QUEUE

QUEUE is a linear array and FRONT and REAR are variables containing the location
of the front element and rear element of the queue. QSIZE specifies the maximum
 42

number of elements that can be stored in the queue. The condition FRONT = NULL
will indicate that the queue is empty. In the above queue, there are three elements. The
position of the first element is 1 indicated by FRONT=1 and the position of the last
element is 3 indicated by REAR=3.

Whenever an element is deleted from the queue, the FRONT is increased by 1. This can
be implemented by the assignment

FRONT=FRONT + 1

Similarly, whenever an element is added to the queue, the value of REAR is increased
by 1. This can be implemented by the assignment

REAR = REAR + 1

This means that after QSIZE insertions, the rear element of the queue will occupy
QUEUE[QSIZE].

Suppose that our queue contains only one element, i.e., suppose that

FRONT = REAR

And suppose that the element is deleted. Then we assign

FRONT = 0 AND REAR = 0

to indicate that the queue is empty.

Types of Queues

The different types of queues are

1. Queue (Ordinary queue)

2. Circular queue
3. Double ended queue (deque)
4. Priority queue

Operations on Queues

The operations that can be performed on queues are

1. Insert an item into a queue

 43

2. Delete an item from queue

3. Display the contents of queue

Queues (Ordinary queues)

In an ordinary queue, deletions can take place at one end, called the front, and
insertions can take place only at the other end, called rear.

Algorithm: QINSERTREAR(Q, FRONT, REAR, QSIZE, ITEM)

Here Q is a queue consisting of QSIZE elements. FRONT and REAR are pointers
pointing to the front and rear elements of a queue. This algorithm inserts ITEM at the
rear end of the queue.

1. [Queue already filled?]

If REAR = QSIZE then
Print “Queue Overflow”
Return
[End of step 1 If structure]
2. [Queue empty?]
If FRONT = -1 Then
FRONT = 0
REAR = 0
Else
REAR = REAR + 1
[End of If]
3. Q[REAR] = ITEM
4. Return.

Algorithm: QDELETEFRONT(Q, FRONT, REAR, ITEM)

Here Q is a queue consisting of N elements. FRONT and REAR are pointers pointing to
the front and rear elements of the queue. This algorithm deletes an item at the rear end
and assigns it to ITEM.

1. [Queue underflow/]
If FRONT = -1 Then
Write “Queue underflow”
Return
[End of If]
 44

2. [Delete front element]

ITEM = Q[FRONT]
3. [Queue has only one element?]
If FRONT = REAR Then
FRONT = 0 AND REAR = 0
Else
FRONT = FRONT + 1
[End of If]
4. Return

/* Program for array implementation queue */

#include<iostream.h>
#include<conio.h>
#include<process.h>
#define QSIZE 5

class Queue
{
private:
int q[QSIZE],front,rear;
public:
Queue()
{
front=-1;
rear=-1;
}

void qInsertRear(int item);

int qDeleteFront();
void qDisplay();
};

void Queue::qInsertRear(int item)

{
if(rear==QSIZE-1)
{
cout<<"Queue overflow"<<endl;
return;
}
if(front == -1)
 45

{
front=0;
rear=0;
}
else
{
rear++;
}
q[rear]=item;
}
int Queue::qDeleteFront()
{
int item;
if(front == -1)
{

return -1
}
item=q[front];
if(front==rear)
{
front=0;
rear=-0;
}
else
{
front++;
}
return item;
}

void Queue::qDisplay()
{
int i;
if(front==-1)
{
cout<<"Queue underflow"<<endl;
exit(1);;
}
cout<<endl<<"Queue elements"<<endl;
for(i=front;i<=rear;i++)
{
cout<<q[i]<<"\t";
 46

}
}

int main()
{
int item,ch;
Queue q1;
clrscr();
while(1)
{
cout<<endl<<"Queue operations"<<endl;
cout<<"1.Insert"<<endl;
cout<<"2.Delete"<<endl;
cout<<"3.Display"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1: cout<<"Enter item : ";
cin>>item;
q1.qInsertRear(item);
break;
case 2: item=q1.qDeleteFront();
if(item==-1)
cout<<"Queue underflow"<<endl;
else
cout<<"Deleted item is "<<item;
break;
case 3: q1.qDisplay();
break;
case 4: exit(0);
}
}
}

Disadvantages of ordinary Queues

Consider the queue shown below:

30 40 50
f r
In the above queue, the rear pointer ‘r’ points to the last element in the queue.
Though, free memory is available at the front end of the queue, insertion into the queue
 47

is denied because the value of rear pointer ‘r’ is equal to QSIZE (Queue size). We
cannot access the free memory available at the front end of the queue. This is a
disadvantage. This can be overcome by shifting the elements to the front end of the
queue. But shifting the elements consumes processor time and is not recommended.
This disadvantage can be overcome by implementing circular queue using an array.

Circular Queues

A circular queue implemented using array makes efficient use of memory. In a circular
queue, the rear end of the queue may be followed by the front end of the queue. The
pictorial representation of a circular queue and its equivalent representation using an
array are given bellow.

In the figure above, the circular queue contains only one element. So, f = r = 1. We
know that elements are inserted only at the rear end and deleted at the front end. So,
before insertion, the value of the r should be 0. So, initially when queue is empty, f = 0,
r = 0.

Figure below shows queue after inserting 20, 30, 40, and 50 into the queue above.
 48

Figure below shows queue after deleting first two elements, 10 and 20.
 49

Suppose we want to insert an element ITEM into a queue at the time the time the queue
does occupy the last part of the array, ie when r = QSIZE then, since the queue is
circular, Q[1] comes after Q[N] in the array. So we insert ITEM into the queue by
assigning ITEM to Q[1]. Specifically, instead of increasing r to N + 1, we reset r = 1
and then assign

Q[r] = ITEM

Similarly, if f = QSIZE and an element of Q is deleted, we reset f = 1 instead of

increasing f to QSIZE + 1.

Suppose that our queue contains only one element, i.e suppose that f = r ≠ 0

and suppose that the element is deleted. Then we assign

f = 0 and r = 0

Figure below shows queue after inserting 60 into the above queue.

Operations on Circular Queues

The various operations that can be performed on circular queues are

1. Insertion at rear end

2. Deletion at front end
3. Displaying the elements
 50

Note: To implement a circular queue, we will use a variable called count that contains
the number of elements in the queue at a given instant. The variable count is
incremented by 1 after inserting an element, and decremented by 1 after deleting an
element from the circular queue.

Insertion at the rear end of the circular queue

Algorithm: CQInsertRear(Q,FRONT, REAR, ITEM, QSIZE)

This algorithm inserts ITEM at the rear end of the circular queue.

1. [Check for overflow]

If FRONT = 1 and REAR = QSIZE, OR if FRONT = REAR + 1 Then
Write: “Queue Overflow”
Return
[End of if structure]
2. [Find new value of REAR]
If FRONT = 0 Then [Queue initially empty]|
FRONT = 1
REAR = 1
Else if REAR = QSIZE Then
REAR = 1
Else
REAR = REAR + 1
[End of if structure]
3. Q[REAR] = ITEM
4. Return

Deletion at the front end of the circular queue

Algorithm: CQDeleteFront(Q, FRONT,REAR, ITEM, QSIZE)

This algorithm deletes an element from the front end of the queue and assigns it to
ITEM.

1. [Check for underflow]

If FRONT = 0, then
Print “Queue is empty”
Return
[End of If structure]
2. [Delete item and assign it to ITEM]
ITEM = Q[FRONT]
 51

3. [Find new value of FRONT]

If FRONT = REAR Then [Queue has only one element]
FRONT = 0
REAR = 0
Else if FRONT = QSIZE Then
FRONT = 1
Else
FRONT = FRONT + 1
[End of if structure]
4. Return

Displaying circular queue contents

Algorithm: CQdisplay(Q,FRONT, REAR,QSIZE)

1. [Check for underflow]

If FRONT = 0 Then
Print “Queue is empty”
Return
[End of if structure]
2. If FRONT < = REAR Then
For I = FRONT to REAR
Write: Q[I]
[End of for loop]
Else
For I = FRONT to QSIZE
Write: Q[I]
[End of for loop]
For I = 1 to REAR
Write: Q[I]
[End of fro loop]
[End of if structure]
3. Return

/* C++ Program for array implementationof circular queue */

#include<iostream.h>
#include<conio.h>
#include<process.h>
#define QSIZE 5
class CirQueue
{
private:
int q[QSIZE],front,rear;
 52

public:
CirQueue()
{
front=-1;
rear=-1;
}
void cqInsertRear(int item);
int cqDeleteFront();
void cqDisplay();
};
void CirQueue::cqInsertRear(int item)
{
if((front == 0 && rear == QSIZE - 1) || (front == rear+1))
{
cout<<"Queue overflow"<<endl;
exit(1);
}
if(front == -1)
{
front=0;
rear=0;
}
else if (rear == QSIZE-1)
{
rear = 0;
}
else
{
rear++;
}
q[rear]=item;
}
int CirQueue::cqDeleteFront()
{
int item;
if(front == -1)
{
cout<<"Queue underflow"<<endl;
exit(1);
}
item=q[front];
if(front==rear)
{
 53

front=-1;
rear=-1;
}
else if (front == QSIZE-1)
{
front = 0;
}
else
{
front++;
}
return item;
}

void CirQueue::cqDisplay()
{
int i;
if(front==-1)
{
cout<<"Queue underflow"<<endl;
exit(1);
}
cout<<"Queue elements"<<endl;
if(front<=rear)
{
for(i=front;i<=rear;i++)
{
cout<<q[i]<<"\t";
}
}
else
{
for(i=front;i<QSIZE;i++)
{
cout<<q[i]<<"\t";
}
for(i=0;i<=rear;i++)
{
cout<<q[i];
}
}
}
int main()
 54

{
int item,ch;
CirQueue q1;
clrscr();
while(1)
{
cout<<endl<<"Circular Queue operations"<<endl;
cout<<"1.Insert"<<endl;
cout<<"2.Delete"<<endl;
cout<<"3.Display"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1: cout<<"Enter item : ";
cin>>item;
q1.cqInsertRear(item);
break;
case 2: item=q1.cqDeleteFront();
cout<<"Deleted item is "<<item;
break;
case 3: q1.cqDisplay();
break;
case 4: exit(0);
}
}
}

Deque (Double Ended Queue)

A deque is a linear list in which the elements can be added and deleted from both ends
of the queue.

Operations on deques

The operations that can be performed on deques are

1. Insert an element at the front end

2. Insert an element at the rear end
3. Delete an element at the front end
4. Delete an element at the rear end
 55

5. Display the contents of the queue

There are two variations of a deque. – namely, an input-restricted deque and out-put
restricted deque. These deques are intermediate between a deque and a queue. An input-
restricted deque is a deque which allows insertions at only one end of the list but allows
deletions at both the ends of the queue. An output-restricted queue allows deletions at
only one end of the queue but allows insertions at both ends of the queue.
We have already discussed insertion at the rear end, deletion from the front end and
display operations of ordinary queues the same algorithms and C functions holds good
for deques also. We shall now discus the other two operations.

Priority Queues

A priority queue is a collection of elements such that each element has been assigned a
priority and such that the order in which elements are deleted and processed follow the
rules given below:

1. An element of higher priority is processed before any element of lower priority.

2. Two elements with the same priority are processed according to the order in
which they were added to the queue.
Priority queues are used to implement job scheduling queues in time sharing operating
systems. Here, programs of high priority are processed first, and programs with the
same priority form a standard queue.