Unit V

“STACK”

.
 CONCEPT OF
STACKs
Definition :
“ Stack is data structure in which addition and
removal of an element is allowed at the same end is
called as top of stack.”
- Stack isalso called as Last In First
Out(LIFO) list.
- It means element which get added at last will be
removed first.
e.g.
 CONCEPT OF
STACKs
Example :
 Components of Stack
• Top is a variable which refers
to last position in stack.

• Element is component which

has data.
• MaxStack is variable that
describes maximum number of
elements in a stack.
 Main Operation

STACK

PUSH POP
Add data Take data
to element from element
in stack. in stack
 Kinds of
Operation

• Stack Operation in array form

• Stack Operation in Linked list

form
 STACK AS AN ADT
Stack is an abstract data type which is defined
by the following structure and operation.

Stack operation :
1. createstack( )
2. Push( )
3. Pop( )
4. Peek( )
5. IsEmpty( )
6. IsFull( )
7. Size( )
 STACK AS AN ADT
Createstack( )- it create new empty stack.
push() − Pushing (storing) an element on the
stack. pop( ) − Removing an element from the
stack. peek() − get the top data element of the
stack, without removing it.

isFull( ) − check if stack is full.

isEmpty( ) − check if stack is empty.
Size() – return the number of item in the stack.
 STACK AS AN ADT
1. Initializing stack
:
 STACK AS AN ADT
2. IsFull( ) stack :
check stack is full or not?
 STACK AS AN ADT
3. IsEmpty( ) stack:
check stack is empty or not?
 STACK AS AN ADT
4. Push( ) stack: add element in stack
 STACK AS AN ADT
5. pop( ) stack : remove element from
stack
 STACK AS AN ADT
6. Display () stack :displaying stack
 ALGORITHM TO IMPLEMENT
STACK USING ARRAY
Step 1 : start
Step 2 : Display Menu : 1. push 2. pop 3.
display
4. exit.
Step 3 : read choice
Step 4 : if choice 1 then call
push ( ) if choice 2 then
call pop( )
if choice 3 the call display ( )
if choice 4 then call exit ( )
 MULTIPLE STACKs
“When a stack is created using single array, we can
not able to store large amount of data, thus this
problem is rectified using more than one stack in
the same array of sufficient array. This technique is
called as Multiple Stack”
 MULTIPLE
STACKs
Example : When an array of STACK[n] is used to
represent two stacks, say Stack A and Stack B. Then
the value of n is such that the combined size of both
the Stack[A] and Stack[B] will never exceed n.
Stack[A] will grow from left to right, whereas
Stack[B] will grow in opposite direction i.e. right
to left.
 APPLICATIONOF STACKs
❖ Convert infix expression to postfix and
prefix expressions
❖ Evaluate the postfix expression
❖ Reverse a string
❖ Check well-formed (nested) parenthesis
❖ Reverse a string
❖ Process subprogram function calls
❖ Parse (analyze the structure) of computer
programs
❖ Simulate recursion
❖ In computations like decimal to binary conversion
❖ In Backtracking algorithms (often used
Expression Representation

21
Algorithm Infix to postfixconversion

27
 Infix to postfix conversion
• Manual algorithm for converting infix
to postfix
(a + b) * c
o Write with parentheses to force correct operator
precedence ((a + b) * c)

o Move operator to right inside parentheses

((a b + ) c * )

o Remove parentheses
ab+c* 28
Infix to postfix conversion
infixVect
(a+b-c)*d–(e+f)

postfixVect
Infix to postfix conversion
stackVect
infixVect
a+b-c)*d–(e+f)

postfixVect

(
Infix to postfix conversion
stackVect

infixVect
+b-c)*d–(e+f)

postfixVect
a

(
Infix to postfix conversion
stackVect

infixVect
b-c)*d–(e+f)

postfixVect
a

+
(
Infix to postfix conversion
stackVect

infixVect
-c)*d–(e+f)

postfixVect
ab

+
(
Infix to postfix conversion
stackVect

infixVect
c)*d–(e+f)

postfixVect
ab+

-
(
Infix to postfix conversion
stackVect
infixVect
)*d–(e+f)

postfixVect
ab+c

-
(
Infix to postfix conversion
stackVect
infixVect
*d–(e+f)

postfixVect
ab+c-
Infix to postfix conversion
stackVect

infixVect
d–(e+f)

postfixVect
ab+c-

*
Infix to postfix conversion
stackVect
infixVect
–(e+f)

postfixVect
ab+c-d

*
Infix to postfix conversion
stackVect
infixVect
(e+f)

postfixVect
ab+c–d*

-
Infix to postfix conversion
stackVect

infixVect
e+f)

postfixVect
ab+c–d*

(
-
Infix to postfix conversion
stackVect

infixVect
+f)

postfixVect
ab+c–d*e

(
-
Infix to postfix conversion
stackVect
infixVect
f)

postfixVect

+ ab+c–d*e

(
-
Infix to postfix conversion
stackVect
infixVect
)

postfixVect

+ ab+c–d*ef

(
-
Infix to postfix conversion
stackVect

infixVect

postfixVect
ab+c–d*ef+

-
Infix to postfix conversion
stackVect

infixVect

postfixVect
ab+c–d*ef+-
 Infix to postfix conversion
Infix Expression: a + (b*c).

Resultant Postfix Expression: abc*+

 Infix to postfix conversion
Infix Expression: A * B + C * D.

Resultant Postfix Expression: abc*+

Infix to postfix conversion

Resultant Postfix Expression: AB+CD-*E/

Infix to postfix conversion

Resultant Postfix Expression:

Infix to postfix conversion

Resultant Postfix Expression:

Infix to postfix conversion
((a/(b-c+d))*(e - a)*c)

Resultant Postfix Expression: abc-d+/ea-*c*

 Infix to postfix conversion
Infix Expression: A+ (B*C-(D/E^F)*G)*H, where ^ is an exponential operator.

Resultant Postfix Expression: ABC*DEF^/G*-H*+

 Infix to postfix conversion
Infix Expression: A+(B*(C-D)/E).

Resultant Postfix Expression: ABCD-*E/+

 Infix to postfix conversion
Infix Expression: A * ( B + C * D) + E.

Resultant Postfix Expression: ABCD*+*E+

Infix to postfix conversion
Infix Expression: A * ( B + C * D) + E.

Resultant Postfix Expression: ABCD*+*E+

 Infix to postfix conversion
Infix Expression: A * ( B + C * D) + E.

Resultant Postfix Expression: ABCD*+*E+

 Infix to postfix conversion
Infix Expression: A * ( B + C * D) + E.

Resultant Postfix Expression: ABCD*+*E+

POSTFIX EXPRESSION EVALUATION
ALGORITHMS :

Resultant Postfix Expression: ABCD*+*E+

POSTFIX EXPRESSION EVALUATION
POSTFIX EVALUATE EXPRESSION : 53+82-*
POSTFIX EXPRESSION EVALUATION
* Evaluate the following postfix expression and show stack after every
step in tabular form. Given A=5, B=6, C=2, D=12, E=4
ABC + *DE\-
POSTFIX EXPRESSION EVALUATION
• Evaluate the following postfix expression
A : 6, 2, 3, +, - , 3, 8, 2, +, +, * , 2, ^, 3, +
 POSTFIX EXPRESSION EVALUATION
• Consider the following arithmetic expression written in postfix notation
10, 2, * , 15, 3, / , + , 12, 3, 2, ↑ , + , + evaluate this expression to find its value
 Convert infixinto prefix expression
convert the given infix to prefix expression and show detail of stack.
(A-B/C)*(D*E-F)
 Convert infixinto prefix expression
convert infix string ((A+B) * (C-D))/(E+F) into prefix string with stack.
---🡪 first reverse the string (F+E)/((D-C) * (B+A))
 Convert prefixinto postfix expr.
Steps :
 Convert prefixinto postfix expr.
Convert the following prefix expression into postfix expression
*+a-bc/-de+-fgh
 Linked stack operation
In stack elements are placed one above other. In the
same manner in stack as linked list, we place node one
above other.

Advantages of dynamic implementation of stack

:
1. No memory wastage
2. No memory shortage
3. No limitation on number of elements
 RECURSION IN STACK
“Calling function inside itself is called as
recursion. Such function is called as recursive
function”
How recursion works?
 RECURSION IN STACK
Advantages :
1. It helps to reduce size of program
2. Easy to maintain function calling
3. Evaluation of stack can be through recursion
4. Also infix,prefix,post-fix notation can be
evaluated with the help of recursion.
Disadvantages :
1. It takes more time bcz of stack overlapping
2. Stack overflow may ocuur
3. Memory requirement is more
4. Efficiency is less
 Examples of recursion:
• Algorithm to multiply natural numbers using
recursion
1. Start
2. Read two numbers a & b
3. Call multiply (a,b)
4. Product=0,i=0;
5. Return product
6. Print multiplication
Write a c++ program for multiplication of natural numbers using
recursion.
Using namespace std;
#include<iosteam>
Int multiply(int,int)
Int main()
{
int a,b,m;
Cout<<“\n Enter two numbers”
cin>>a>>b;
m=multiply(a,b);
Cout<<“\n Mutiplication is:” <<m;
}
Int multiply(int a,int b)
{
Static int product=0,i=0;
If(i<a){
Product=product+b;
i++;
multiply(a,b);
}
return product;
}
 Variants of recursion: Direct, Indirect, tail, tree
1. Direct Recursion:
• Recursion is said to be direct when functions calls itself
directly i.e. the function body contains an explicit call to
itself.
• The function of factorial is an example of direct recursion.
Algorithm of program to calculate the factorial of number
using recursion
1. Start
2. Read number num
3. Cal factorial(num)
4. If no<0 then return -1
Else if no=0 then return 1
Else
Return(no*factorial(no-1))
5. Print factorial fact
2. Indirect recursion:
• Recursion is said to be indirect when it calls other function
that in turn calls it.
• The functions involved in indirect recursion are called
mutually recursive functions.
• Comparatively, it is simpler and safer to use direct recursion
as it is much easier to understand and apply.
3. Tail Recursion:
• A recursive function is tail recursive when recursive call is
the last thing executed by the function.
• For example the following C++ function printnum() is tail
recursive.
Void printnum(int num)
{
if(num<0)
Return;
cout<<“ ”<<num;
printnum(num-1); //the last executed statement is
recursive call
}
 4. Tree Recursion
• A function is said to be Tree recursive or non linearly
recursive when the pending operation involves another
recursive call to the function
• Ex- Fibonacci function
• Algorithm:
1. Start
2. Initialize x=0,y=1
3. Read number of terms n
4. Print x,y and call fibonacci (x,y,n)
5. If n<0 then exit
6. Sum=x+y
print sum
x=y and y=sum
7. fibonacci (x,y,n-1)
Backtracking algorithm strategy:
 4-QUEEN PROBLEM
The N Queen is the problem of placing N chess
queens on an N×N chessboard so that no two
queens attack each other.
•THANK
YOU!!!!!!!