BCA SEM-III

UNIT-II
SUBJECT: DATA
STRUCTURE

Prof. Smita Muley

 INTRODUCTION TO STACK:
A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. Stack has one end, whereas the Queue has
two ends (front and rear). It contains only one pointer top pointer pointing to the topmost element of the stack. Whenever an
element is added in the stack, it is added on the top of the stack, and the element can be deleted only from the stack. In other
words, a stack can be defined as a container in which insertion and deletion can be done from the one end known as the top of
the stack.
KEY POINTS:

o It is called as stack because it behaves like a real-world stack, piles of books, etc.
o A Stack is an abstract data type with a pre-defined capacity, which means that it can store the elements of a limited size.
o It is a data structure that follows some order to insert and delete the elements, and that order can be LIFO or FILO.

Stack Representation
A stack allows all data operations at one end only. At any given time, we can only access the top element of a stack.
The following diagram depicts a stack and its operations −

A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can either be a fixed size one or it may
have a sense of dynamic resizing. Here, we are going to implement stack using arrays, which makes it a fixed size stack
implementation.
Working of Stack
Stack works on the LIFO pattern. As we can observe in the below figure there are five memory blocks in the stack; therefore, the
size of the stack is 5.
Suppose we want to store the elements in a stack and let's assume that stack is empty. We have taken the stack of size 5 as shown
below in which we are pushing the elements one by one until the stack becomes full.

Prof. Smita Muley

 Since our stack is full as the size of the stack is 5. In the above cases, we can observe that it goes from the top to the bottom when
we were entering the new element in the stack. The stack gets filled up from the bottom to the top.
When we perform the delete operation on the stack, there is only one way for entry and exit as the other end is closed. It follows
the LIFO pattern, which means that the value entered first will be removed last. In the above case, the value 5 is entered first, so it
will be removed only after the deletion of all the other elements.

Standard Stack Operations

PUSH operation
The steps involved in the PUSH operation is given below:

o Before inserting an element in a stack, we check whether the stack is full.

o If we try to insert the element in a stack, and the stack is full, then the overflow condition occurs.

o When we initialize a stack, we set the value of top as -1 to check that the stack is empty.
o 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.

o The elements will be inserted until we reach the max size of the stack.

Prof. Smita Muley

Algorithm
1) Initialize Set top=-1
2) Repeat step 3 to 5 until Top<maxsize-1
3) read item
4) set top=top+1
5) Set stack[top]=item
6) print ‘stack overflow’
7) exit

30
20
10

(MAXSIZE=3)
Case 1)
Initialize Top=-1

2) top<maxsize-1

-1<3-1
-1<2(true)

3) read itemRead 10

Top=top+1
-1+1=0
Stack[0]=item=10

Prof. Smita Muley

Case 2 top<maxsize-1
0<3-1
0<2(true)

3) read item Read 20

4) Top=top+10+1=1

5) Stack[1]=item=20

Case 3 top<maxsize-1
1<3-1
1<2(true)

3) read item Read 30

4) Top=top+11+1=2

5) Stack[2]=item=30

Case 4 top<maxsize-1
2<3-1
2<2(false)

3) Goto step 6 print overflow and exit

EXAMPLE:
PROGRAM LOGIC:
Void push( int item)
{
If(top==maxsize-1)
{
Printf(“overflow and exit\n”);
}
Else
{
Stack[++top]=item;
Printf(/”%d item inserted\n”,item);
}

POP operation
The steps involved in the POP operation is given below:

Prof. Smita Muley

o Before deleting the element from the stack, we check whether the stack is empty.

o If we try to delete the element from the empty stack, then the underflow condition occurs.

o If the stack is not empty, we first access the element which is pointed by the top

o Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.

Algorithm for deleting an item from the stack

1) Begin

2) Repeat step 2 to 4 until top>=0

3) set item=stack[top]

4) set top=top-1

5) print number of deleted item

6) print stack underflow

7)exit

20

10

Case 2
Check top>=0
1>0(True)

Set item = stack[top]

Item=s[1]=20

Prof. Smita Muley

Set top=top-1
1-1=0
item deleted is(20)

10

Case 3
1) Check top >=0

0=0(Top=0)

2)item = stack[0]
Item=10
3)top=top-1
0-1=-1
4) Deleted item is(10)

Case 4
Check Top>=0
-1 not equals to 0 (False condition)
go to step 5 print stack underflow and exit.

PROGRAMMING LOGIC:

Void pop()
{
If( top==-1)
{
printf(“underflow and exit\n”);
}
Else
{
Int item=stack[top--];
Printf(“%d item deleted\n”,item);
}
}

Applications of stack:
Prof. Smita Muley
 The following are the applications of the stack:

1. Memory management: The stack manages the memory. The memory isassigned in the contiguous memory blocks. The memory
is known as stack memory as all the variables are assigned in a function call stack memory. The memory size assigned to the
program is known to the compiler. When the function is created, all its variables are assigned in the stack memory. When the
function completed its execution, all the variables assigned in the stack are released.

2. Processing Function Calls:

Stack plays an important role in programs that call several functions in succession. Suppose we have a program containing three
functions: A, B, and C. function A invokes function B, which invokes the function C.

When we invoke function A, which contains a call to function B, then its processing will not be completed until function B has
completed its execution and returned. Similarly for function B and C. So we observe that function A will only be completed after
function B is completed and function B will only be completed after function C is completed. Therefore, function A is first to be
started and last to be completed. To conclude, the above function activity matches the last in first out behavior and can easily be
handled using Stack.

3. Expression evaluation: Stacks are also used in evaluating arithmetic expressions. When an expression is parsed, the operators
and operands are pushed onto the stack based on their precedence. As the expression is evaluated, the stack is popped, and the
operations are performed in the correct order.
Stack data structure is used to evaluate expressions in infix, postfix, and prefix notations. Operators and operands are push ed
onto the stack, and operations are performed based on the stack’s top elements.

4. Browser history: Web browsers use stacks to keep track of the web pages you visit. Each time you visit a new page, the URL
is pushed onto the stack, and when you hit the back button, the previous URL is popped from the stack.
5. Backtracking Algorithms: The backtracking algorithm uses stacks to keep track of the states of the problem-solving process.
The current state is pushed onto the stack, and when the algorithm backtracks, the previous state is popped from the stack.

Backtracking is a systematic method of trying out various sequences of decisions until you find out that works. Let's understand
through an example.
We start with a start node. First, we move to node A. Since it is not a feasible solution so we move to the next node, i.e., B. B is also
not a feasible solution, and it is a dead-end so we backtrack from node B to node A.

Suppose another path exists from node A to node C. So, we move from node A to node C. It is also a dead-end, so again backtrack
from node C to node A. We move from node A to the starting node.

Prof. Smita Muley

Now we will check any other path exists from the starting node. So, we move from start node to the node D. Since it is not a feasible
solution so we move from node D to node E. The node E is also not a feasible solution. It is a dead end so we backtrack from node
E to node D.

Suppose another path exists from node D to node F. So, we move from node D to node F. Since it is not a feasible solution and it's
a dead-end, we check for another path from node F.

Prof. Smita Muley

Suppose there is another path exists from the node F to node G so move from node F to node G. The node G is a success node.

RECURSION:
The recursion is a process by which a function calls itself. We use recursion to solve bigger problem into smaller sub-problems. if
each sub-problem is following same kind of patterns, then only we can use the recursive approach.
Using a recursive algorithm, certain problems can be solved quite easily. Examples of such problems are Towers of Hanoi
(TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc. A recursive function solves a particular problem by
calling a copy of itself and solving smaller subproblems of the original problems. Many more recursive calls can be generated
as and when required. It is essential to know that we should provide a certain case in order to terminate this recursion process.
So we can say that every time the function calls itself with a simpler version of the original problem.

Prof. Smita Muley

 Need of Recursion
Recursion is an amazing technique with the help of which we can reduce the length of our code and make it easier to read and
write. A task that can be defined with its similar subtask, recursion is one of the best solutions for it.

Applications of Recursion:
Factorial
Factorial of a non-negative integer is the multiplication of all positive integerssmaller than or equal to n. For example factorial
of 6 is 6*5*4*3*2*1 which is 720.
A factorial is represented by a number and a ” ! ” mark at the end. It is widely used in permutations and combinations to
calculate the total possible outcomes.

#include<stdio.h>

int fact(int n)
{
if((n==0)||(n==1))
return 1;
else
return n*fact(n-1);
}

int main()
{
int n;
printf("Enter a positive integer: ");
scanf("%d",&n);
printf("Factorial of %d = %ld", n, fact(n));
return 0;
}

Output:
Enter a positive integer: 5
Factorial of 5 = 120

Fibonacci series:

Prof. Smita Muley

 The Fibonacci series is the sequence where each number is the sum of the previous two numbers of the sequence. The first two
numbers of the Fibonacci series are 0 and 1 and are used to generate the Fibonacci series.

Fibonacci
series

#include<stdio.h>
int fib(int x)
{
if((x==1)||(x==0))
{
return(x);
}
else
{
return(fib(x-1)+fib(x-2));
}
}
int main()
{
int x , i=0;
printf("Enter the number of terms of series : ");
scanf("%d",&x);
printf("\n Fibonnaci Series : ");
while(i<x)
{
printf("%d ",fib(i));
i++;
}
return 0;
}
Output:
Enter the number of terms of series : 5

Fibonnaci Series : 0 1 1 2 3

Tower of Hanoi:
Tower of Hanoi is a mathematical puzzle where we have three rods (A, B, and C) and N disks. Initially, all the disks are
stacked in decreasing value of diameter i.e., the smallest disk is placed on the top and they are on rod A. The objective of the
puzzle is to move the entire stack to another rod (here considered C), obeying the following simple rules:
 Only one disk can be moved at a time.

Prof. Smita Muley

 Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be
moved if it is the uppermost disk on a stack.
 No disk may be placed on top of a smaller disk.
Example:
Input: 3
Output: Disk 1 moved from A to C
Disk 2 moved from A to B
Disk 1 moved from C to B
Disk 3 moved from A to C
Disk 1 moved from B to A
Disk 2 moved from B to C
Disk 1 moved from A to C

The idea is to use the helper node to reach the destination using recursion. Below is the pattern for this problem:
 Shift ‘N-1’ disks from ‘A’ to ‘B’, using C.
 Shift last disk from ‘A’ to ‘C’.
 Shift ‘N-1’ disks from ‘B’ to ‘C’, using A.

Follow the steps below to solve the problem:

 Create a function towerOfHanoi where pass the N (current number of disk), from_rod, to_rod, aux_rod.
 Make a function call for N – 1 th disk.
 Then print the current the disk along with from_rod and to_rod
 Again make a function call for N – 1 th disk

Programming Logic:
void towerOfHanoi(int n, char from_rod, char to_rod,
char aux_rod)
{
if (n == 0)
{
return;
}

Prof. Smita Muley

 towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
cout << "Move disk " << n << " from rod " << from_rod
<< " to rod " << to_rod << endl;
towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

Quick Sort:
The quick sort algorithm items to separates the list of elements into two parts and then sort each part recursively . It use divide and
conquer method . In this method the patrician of list is performed based on the element called pivot element.
The list is divided into two patrician such that all elements to the left pivot are smaller than the pivot and all elements of right of
pivot are greater than or equal to pivot.

Working of Quick Sort Algorithm

To understand the working of quick sort, let's take an unsorted array. It will make the concept more clear and understandable.
Let the elements of array are -

In the given array, we consider the leftmost element as pivot. So, in this case, a[left] = 24, a[right] = 27 and a[pivot] = 2 4.
Since, pivot is at left, so algorithm starts from right and move towards left.

Now, a[pivot] < a[right], so algorithm moves forward one position towards left, i.e. -

Prof. Smita Muley

Now, a[left] = 24, a[right] = 19, and a[pivot] = 24.
Because, a[pivot] > a[right], so, algorithm will swap a[pivot] with a[right], and pivot moves to right, as –

Now, a[left] = 19, a[right] = 24, and a[pivot] = 24. Since, pivot is at right, so algorithm starts from left and moves to right.
As a[pivot] > a[left], so algorithm moves one position to right as -

Now, a[left] = 9, a[right] = 24, and a[pivot] = 24. As a[pivot] > a[left], so algorithm moves one position to right as -

Now, a[left] = 29, a[right] = 24, and a[pivot] = 24. As a[pivot] < a[left], so, swap a[pivot] and a[left], now pivot is at left, i.e. -

Prof. Smita Muley

Since, pivot is at left, so algorithm starts from right, and move to left. Now, a[left] = 24, a[right] = 29, and a[pivot] = 24. As a[pivot]
< a[right], so algorithm moves one position to left, as -

Now, a[pivot] = 24, a[left] = 24, and a[right] = 14. As a[pivot] > a[right], so, swap a[pivot] and a[right], now pivot is at right, i.e. -

Now, a[pivot] = 24, a[left] = 14, and a[right] = 24. Pivot is at right, so the algorithm starts from left and move to right.

Prof. Smita Muley

 Now, a[pivot] = 24, a[left] = 24, and a[right] = 24. So, pivot, left and right are pointing the same element. It represents the termination
of procedure.
Element 24, which is the pivot element is placed at its exact position.
Elements that are right side of element 24 are greater than it, and the elements that are left side of element 24 are smaller than it.

Now, in a similar manner, quick sort algorithm is separately applied to the left and right sub-arrays. After sorting gets done, the
array will be -

Algorithm of quick sort:

Step 1: begin
Step 2: Select the start element of array as a pivot element
Step3: scan and find smallest element from right side of array.
Step 4: Interchange both elements
Step 5: scan and find biggest element from left side of array.
Step 6: Repeat the above process until all the elements of left side
are smaller and right side elements are greater than pivot
element.
Step 7: now, user get two sublist then apply same process on each
sublist until the all elements of array are not sorted.

Solve the below listed array by using quick sort technique and
Show the steps to sort the given numbers
1. 50 3 1 60 65 45 90 13 67
2. 42 84 75 20 60 10 90 50 05 30
3. 7 6 10 5 9 2 1 15 7
4. 54 26 93 17 77 31 44 55 20

Expression Evaluation:
Expression is nothing but the combination of operands and operator.
On the basis of operand position the stack arithmetic expression is classified into three types

1. Infix notation

Prof. Smita Muley

 2. Prefix(Polish notation)
3. Postfix(reversed polish notation)

1. Infix Notation:
If operator is placed in between the operands then its called as infix notation.
Ex: A+B and A-B
2. Prefix Notation:
If operator is placed before the operands then its called prefix expression it is also known as polish notation.
Ex: +AB, *AB
3. Postfix Notation:
If operator is placed after the operands then its called postfix expression. It is also known as reversed polish notation.
Ex: AB+, AB*

Operator Precedence and associativity:

Precedence of operators:

The precedence of operators determines which operator is executed first if there is more than one operator in an expression.

Ex: A+B*C

=A+(B*C)

Associativity of operators:

Rule where operators with the same priority appear in an expression.

Ex: A+B-C

Here both + and – have same priority. So solve such expression to give left to right associativity.

Operator Precedence Associativity

^ Highest Right Associativity

*,/ Second highest Left to right

+,- Lowest Left to right

Convert infix expression to postfix expression without using stack:

1. (A + B) * (B * D)

=(AB+) *(B*D)

=(AB+) *(BD*)

=AB+ BD**

Prof. Smita Muley

2. (A+B) * c

=(AB+)*C

=AB+C*

Print operands as they arrive

If stack is empty or contains a left parenthesis on top, push the incoming operator onto the
stack
Convert
If infix
incoming symbol is ‘(‘, push
expression to postfix
it ontoexpression
stack. with using stack:
If incoming symbol is ‘)’, pop the stack and print the operator until left
parenthesis is found.
If incoming symbol has higher precedence then the top of the stack,push it on to the stack
If incoming symbol has lower precedence then the top of the stack ,pop and print the top. Then test the incoming operator against
the new top of the stack.
If incoming operator has equal precedence with the top of the stack , use associativity rule.
At the end of the expression, pop and print all operators of stack.
Associativity L TO R then pop and print the top of the stack and then pushthe incoming operator.
R TO L then push the incoming [Link] to prefix conversion
reverse the prefix expression
same as postfix expression only difference is in equal precedence (In equal precedence push the incoming operator onto the stack)
K+L-M*N+(O^P)*W/U/V*T+Q^j^

Input Stack Postfix expression

K K
+ + k
L + KL
- - KL+
M - KL+M
* -* KL+M
N -* KL+MN
+ + KL+MN*-
( +( KL+MN*-
O +( KL+MN*-O
^ +(^ KL+MN*-O

Prof. Smita Muley

 P +(^ KL+MN*-OP
) + KL+MN*-OP^
* +* KL+MN*-OP^
W +* KL+MN*-OP^W
/ +/ KL+MN*-OP^W*
U +/ KL+MN*-OP^W*U
/ +/ KL+MN*-OP^W*U/
V +/ KL+MN*-OP^W*U/V
* +* KL+MN*-OP^W*U/V/
T +* KL+MN*-OP^W*U/V/T
+ + KL+MN*-OP^W*U/V/T*+
Q + KL+MN*-OP^W*U/V/T*+Q
^ +^ KL+MN*-OP^W*U/V/T*+Q
J +^ KL+MN*-OP^W*U/V/T*+QJ
^ +^^ KL+MN*-OP^W*U/V/T*+QJ
^ KL+MN*-OP^W*U/V/T*+QJ^^+

Ans
KL+MN*-OP^W*U/V/T*+QJ^^+

Prof. Smita Muley

 A+ (B*C – (D / E A F) * G) * H

Solve the given infix to postfix expression

I) [(A + B) * (B * D)]
II)[p – ( u * r – s) / t]
III) [( A + B) * C]
IV) [(A + B * D) *(B – C)]
V) [( A / B) +(C / D)]
VI) [P + ( Q * R – ( S/ T ^ U) * V)*W]

Convert Infix to prefix notation without using stack:

(A+B) * (B*D)
= (+AB) * (B*D)
= (+AB) * (*BD)
= *+AB * BD

Prof. Smita Muley

 Convert Infix to prefix notation with using stack:
To convert Infix to prefix using the stack, first reverse the infix expression and at last again reverse the output expression to get
prefix expression. We have operator’s stack, output’s stack and one input string. Operator’s stack works as FILO(First In Last
Out). Output’s stack works as FIFO (First In First Out).
1. [(A + B) * (B * D)]
REVERSE EXPRESSION
[(D * B) * (B + A)]
Input Stack Postfix expression

[ [ -

( [( -

D [( D

* [(* D

B [(* DB

) [ DB*

* [* DB*

( [*( DB*

B [*( DB*B

+ [*(+ DB*B

A [*(+ DB*BA

) [* DB*BA+

] DB*BA+*

REVERSE *+AB*BD

Calculate the given infix to prefix expression:

I)[p – ( u * r – s) / t]
II) [( A + B) * C]
III) [(A + B * D) *(B – C)]
IV) [( A / B) +(C / D)]

Prof. Smita Muley