Unit-3 Stack 3/16/2022

Example:

Unit-3 Stack

Prepared By:
Prof. Vishal A. Polara
Assistant Professor
Information Technology Department
Birla Vishvakarma Mahavidyalaya Engineering College

1 Prof. Vishal A. Polara 4 Prof. Vishal A. Polara

Outline Operation on Stack

 Stack- definition and concepts  Following operations which are performs on stack:
 Operations on stacks  PUSH – Insert element at TOP.
 Application of stack  POP – Remove element from TOP.
 PEEK- Display top element
 Polish Expression
 PEEP/UPDATE – Update value of ith element.
 Reverse polish expression and their compilation
 TRAVERSAL – Traversal into stack 0  TOP.
 Recursion: Factorial, Fibonacci series, Tower of Hanoi.

2 Prof. Vishal A. Polara 5 Prof. Vishal A. Polara

Stack- definition and concepts PUSH Operation

 It is an ordered group of homogeneous items of int a[3]={0,0,0} TOP =-1 Default value
elements.
 Elements are added to and removed from the top of
PUSH 10 PUSH 20 PUSH 30 PUSH 40
the stack (the most recently added items are at the
top of the stack). 0 0 0 30 30
 Stack is an abstract data type (ADT). 0 0 20 20 20
 The last element to be added is the first to be 0 10 10 10 10
removed (LIFO: Last In, First Out). (i)Empty (ii) (iii) (iv) (v)
 Micro–processor is work based on stack structure. TOP=-1 TOP=0 TOP=1 TOP=2 Overflow
 Example: When member function call address &
arguments are PUSH into stack. After completion of
exception address & arguments are POP.

3 Prof. Vishal A. Polara 6 Prof. Vishal A. Polara

1
Unit-3 Stack 3/16/2022

Algorithm Algorithm
 Step-1: [Initialization]
 Step-1: [Initialization]  Initialization or declare int a[10]
 Initialization or declare int a[10]  Variable i, n, TOP=-1, choice
 Variable i, n, TOP=-1, choice  Set i  LB  0
 Set i  LB  0
 Step–2: Get the size of stack from user n  X value.
 Step–3: Repeat step–3 while(i < n)
 Step–2: Get the size of stack from user n  X value.
 Increase TOP  TOP + 1
 Step–3: Repeat step–3 while (choice != ‘n’)  Assign value a[TOP]  X value
 Get PUSH value from user X  value  Increase i  i + 1
 Check TOP value if (TOP < n)  Step–4: Repeat step–3 while (choice != ‘n’)
 Increase TOP  TOP + 1  If(TOP == -1)
 Assign value a[TOP]  X  printf(“Stack Underflow”);
 If (TOP>=n)  break;
7 Prof. Vishal A. Polara 10 Prof. Vishal A. Polara

 printf(“Stack Overflow”);
 break;
 Get the value for choice from user  Otherwise
 Print POP value a[TOP]
 Step–4: Print value of stack after PUSH operation.  Decrease TOP  TOP-1
 Set i  LB  0  Get the value for choice
 Print X value a[i] from stack.  Step–5: Print value of stack after POP operation.
 Increase i  i + 1 up to TOP  Set i  LB  0
 Step–5: Finished.  Print X value a[i] from stack.
 Exit  Increase i  i + 1 up to TOP
 Step–6: Finished.
 Exit

8 Prof. Vishal A. Polara 11 Prof. Vishal A. Polara

POP Operation PEEP Operation

int a[3]={10,20,30} TOP = 2  This function returns the value of ith element from the
Top of the stack.
POP 30 POP 20 POP 10 POP
 1. Check for underflow
30 0 0 0 30
 If Top-i+1<=0
20 20 0 0 20
 Then printf(“stack underflow”)
10 10 10 0 10  exit
(i)Full (ii) (iii) (iv) (v)Empty  Return ith element from top of the stack
TOP=2 TOP=1 TOP=0 TOP=-1 Underflow
 Return (a[Top-i+1])

9 Prof. Vishal A. Polara 12 Prof. Vishal A. Polara

2
Unit-3 Stack 3/16/2022

Stack linked list implementation

Stack Push Operation using Linked list
 Stack can be implemented using array but drawback is fixed
size. We can’t create stack of dynamic size.
 Dynamic size stack can be created using linked list.  Step 1: Allocate memory for the new
node and name it as NEW_NODE
 The storage requirement of linked representation of the stack
with n elements is O(n), and the typical time requirement for  Step 2: SET NEW_NODE -> DATA = VAL
the operations is O(1).  Step 3: IF TOP = NULL
 In a linked stack, every node has two parts—one that stores  SET NEW_NODE -> NEXT = NULL
data and another that stores the address of the next node. The  SET TOP = NEW_NODE
START pointer of the linked list is used as TOP.  ELSE
 All insertions and deletions are done at the node pointed by  SET NEW_NODE -> NEXT = TOP

TOP. If TOP = NULL, then it indicates that the stack is empty.  SET TOP = NEW_NODE
 [END OF IF]
 It also support all operation of stack
 Step 4: END

13 Prof. Vishal A. Polara 16 Prof. Vishal A. Polara

Push Operation using linked list

 In push operation we first check if TOP=NULL. If this Void push()
is the case, then we allocate memory for a new node, {
store the value in its DATA part and NULL in its struct node *temp;
NEXT part. The new node will then be called TOP.
temp=(struct node*)malloc(sizeof(struct node))
 However, if TOP!=NULL, then we insert the new node
at the beginning of the linked stack and name this new printf(“enter node data”);
node as TOP. scanf(“%d”,&temp->data);
temp->next(link)=top;
top=temp;
}

14 Prof. Vishal A. Polara 17 Prof. Vishal A. Polara

Pop Operation
Create node in linked list  The pop operation is used to delete the topmost element
from a stack.
Struct node  However, before deleting the value, we must first check
{ if TOP=NULL, because if this is the case, then it means
that the stack is empty and no more deletions can be
Int data;
done.
Struct node *next(link);  If an attempt is made to delete a value from a stack that
}; is already empty, an UNDERFLOW message is printed.
Struct node *top = NULL  In case TOP!=NULL, then we will delete the node
pointed by TOP, and make TOP point to the second
element of the linked stack.

15 Prof. Vishal A. Polara 18 Prof. Vishal A. Polara

3
Unit-3 Stack 3/16/2022

Stack Pop Operation using Linked list Application of Stack

 Step 1: IF TOP = NULL  Implement recursion functionality same as PASCAL,
o PRINT UNDERFLOW ALGOL-60, C, C++ languages.
o Goto Step 5  Implement stack machines which are perform stack
 [END OF IF] operation at hardware or machine level.
 Step 2: SET PTR = TOP  Compilation or solved infix expression into object code.
 Step 3: SET TOP = TOP -> NEXT  To represent infix, prefix & postfix polish notations.
 Step 4: FREE PTR  Reversing a list
 Step 5: END  Undo operation in word
 Parentheses checker
 Recursion
 Tower of Hanoi
19 Prof. Vishal A. Polara 22 Prof. Vishal A. Polara

Polish Expression
Void pop()  Arithmetic expressions are normally written in infix
{ notation. It is called infix because the arithmetic
struct node *temp; operator (i.e. +, -, *, /) is in-between the operands.
if(top==NULL)  It is difficult to develop an algorithm to evaluate infix
printf(“No node or element to delete”) expressions due to precedence problems. You cannot
else simply evaluate an expression straight left to right!
temp=top  the task of the compiler would be much easier. If we
could evaluate an arithmetic expression by simply going
printf(“%d”,temp->data)
straight left to right.
top=top->next(link)
 It is possible by Transforming the expression into a form
temp-> next(link)=NULL
called Polish notation.
free(temp)
 The process of writing the operators of an expression
} either before their operands or after operands are called
polish notation.
20 Prof. Vishal A. Polara 23 Prof. Vishal A. Polara

 Postfix notation is known as reverse polish notation(RPN).

Traversal (Display) operation  Although a prefix notation is also evaluated from left to right,
the only difference between a postfix notation and a prefix
 Void traverse()
notation is that in a prefix notation, the operator is placed
{ before the operands.
struct node *temp;  For example, if A+B is an expression in infix notation, then
if(top==NULL) the corresponding expression in prefix notation is given by
printf(“stack is empty”) +AB.
else  While evaluating a prefix expression, the operators are
temp=top applied to the operands that are present immediately on the
while(temp!=NULL) right of the operator.
printf(“%d\n”,temp->data)  prefix expressions do not follow the rules of operator
temp=temp->next(link) precedence and associativity, and even brackets cannot alter
} the order of evaluation.

21 Prof. Vishal A. Polara 24 Prof. Vishal A. Polara

4
Unit-3 Stack 3/16/2022

Reverse Polish Notation

Example:
 In postfix notation, as the name suggests, the operator is
placed after the operands. For example, if an expression is
written as A+B in infix notation, the same expression can be Infix Prefix Postfix
written as AB+.
a. {(A*B)+(C*D)}-e a. -+*AB*CDE a. AB*CD*+e-
 A postfix operation does not even follow the rules of operator
precedence. b. a=2,b=3,c=5,d= b. -+*23*549 b. 23*54*+9-
 The operator which occurs first in the expression is operated 4,e=9 c. -+6209 c. 620+9-
first on the operands. For ex. + evaluated before *. c. 2*3+5*4-9 d. -269 d. 269-
 In postfix notation the order of evaluation of a postfix d. 6+20-9 e. 17 e. 17
expression is always from left to right. Even brackets cannot e. 26-9
alter the order of evaluation.
f. 17
 The expression (A + B) * C can be written as: [AB+]*C.

25 Prof. Vishal A. Polara 28 Prof. Vishal A. Polara

 Order of Operation rule:

Example:
 1) Parenthesis( (), {},[])
 2) Exponents or modulus (%)( 2^3 - right to left $=^)
 3) multiplication and division (* and / fall on equal
level based on associativity from left to right)
 4) addition and subtraction (left to right)(+ and – fall
on equal level based on associativity from left to
[Link] one is grater or lesser)
 ( ), , $, ^, /, *, +, -

26 Prof. Vishal A. Polara 29 Prof. Vishal A. Polara

Steps for infix to postfix using stack

Example  Requires usage of an operator stack and postfix string.
 Steps:
• If token is an operand, push onto postfix string.
Infix Prefix Postfix
• If token is an operator, compare this with the top of the
a. 3+2 a. +3 2 a. 3 2 + operator stack
1) If token is lesser (precedence), pop the operator stack and
push onto postfix string then revaluate.
b. 3+2*4 b. +3 *2 4 b. 324*+
o An incoming left parenthesis will be considered to have
higher priority than any other symbol. A left parenthesis on
c. 3 + 2 * 4 – (5 + 2) c. -+3 *2 4 + 5 2 c. 3 2 4 * + 5 2 + the stack will not be removed unless an incoming right
parenthesis is found.
-
o

27 Prof. Vishal A. Polara 30 Prof. Vishal A. Polara

5
Unit-3 Stack 3/16/2022

Algorithm
o If a right parenthesis is the current symbol, pop
the stack down to (and including) the first left
parenthesis. Write all the symbols except the
left parenthesis to the output
2) If token is greater(precedence), push onto the
operator stack
3) If token is equal (precedence) use the lesser
rule
o Comparing against an empty operator stack
will always result in a push onto the operator
stack

31 Prof. Vishal A. Polara 34 Prof. Vishal A. Polara

A+B*C-D*E Infix to prefix (without parenthesis

Infix to postfix(exp)
Infix expression Stack Postfix {
expression create stack s
for i=0 to length(exp)-1
A A {
+ + A if(exp[i] is operand)
res=res+exp[i]
B + AB
elseif(exp[i] is operator)
* +* AB {
C +* ABC while(![Link]() && hashigherprec([Link](),exp[i]))
{
- - ABC*+ res=res+[Link]()
D - ABC*+D [Link]()
}
* -* ABC*+D [Link](exp[i])
E -* ABC*+DE }
}
Prof. Vishal A. Polara
ABC*+DE*- Prof. Vishal A. Polara
32 35

 (A-(B/C+(D%E*F)/G)*H)
while(![Link]())
{
res=res + [Link]()
[Link]()
}
Return res
}

33 Prof. Vishal A. Polara 36 Prof. Vishal A. Polara

6
Unit-3 Stack 3/16/2022

Pseudo code infix to postfix with parenthesis

Infix to postfix(exp)
{
create stack s
for i=0 to length(exp)-1 o If a left parenthesis is the current symbol,
{ pop the stack down to (and including) the
if(exp[i] is operand) first right parenthesis. Write all the
res=res+exp[i]
symbols except the right parenthesis to
elseif(exp[I] is operator)
the output
{ 2) If token is greater(precedence), push
while(![Link]() && !isopeningparent([Link]()) && onto the operator stack
hashigherprec([Link](),exp[i]) 3) If token is equal (precedence) use the
{ lesser rule
res=res+[Link]() o Comparing against an empty operator
[Link]() stack will always result in a push onto the
} operator stack
[Link](exp[i])
}
37 Prof. Vishal A. Polara 40 Prof. Vishal A. Polara

elseif isopeningparenthesis (exp[i])

[Link](exp[i])
(A+B)*C
elseif isclosingparenthesis (exp[i]) {
Infix Stack Prefix
While(![Link]() && !isOpeningparentec([Link]()))
{ symbol string
res=res+[Link]() C - C
[Link]()
} * * C
[Link]()
} ) *) C
} //close of for loop B *) CB
while(![Link]())
{ + *)+ CB
res=res + [Link]()
[Link]()
A *)+ CBA
} ( * CBA+*
Return res
} *+ABC
38 Prof. Vishal A. Polara 41 Prof. Vishal A. Polara

Steps for infix to prefix using stack Evaluation of postfix using stack
 Requires usage of an operator stack and prefix string.
 Steps:  23*54*+9- Postfix
• If token is an operand, push onto prefix string. Evalpostfix(exp)
• If token is an operator, compare this with the top of the {
operator stack Create a stack s
1) If token is lesser (precedence), pop the operator stack and For i=0 to length(exp)-1
push onto prefix string then revaluate. {
o An incoming right parenthesis will be considered to have if(exp(i) is operand)
higher priority than any other symbol. A right parenthesis push(exp[i])
on the stack will not be removed unless an incoming left elseif(exp[i] is operator)
parenthesis is found. op2=pop()
o op1=pop()

res=perform(exp[i],op1,op2)
39 Prof. Vishal A. Polara 42 Prof. Vishal A. Polara push(res)

7
Unit-3 Stack 3/16/2022

Evaluation of prefix using stack Example:

 -+*23*549 Prefix (right to left)
1) 2+3*4
Evalpostfix(exp)
{ Answer: 2 3 4 * +
Create a stack s 2) A + (B – D) * E – F
For i= length(exp)-1 to i=0 Answer: A B D – E * + F -
{
if(exp(i) is operand)
push(exp[i])
elseif(exp[i] is operator)
op2=pop()
op1=pop()

res=perform(exp[i],op1,op2)
43 Prof. Vishal A. Polara push(res) 46 Prof. Vishal A. Polara

Post fix Evaluation example

Symbol Op1 Op2 Value Stack Recursion
2 - - - 2
 A recursive function is defined as a function that calls
3 - - - 23 itself to solve a smaller version of its task until a final
* 2 3 6 6
call is made which
 Since a recursive function repeatedly calls itself, it
5 - - - 65 makes use of the system stack to temporarily store the
4 - - - 654 return address and local variables of the calling
function does not require a call to itself.
* 5 4 20 620
 Every recursive solution has two major cases:
+ 20 6 26 26  1) Base case, in which the problem is simple enough
9 - - - 26 9 to be solved directly without making any further calls
to the same function.
- 26 9 17 17
Prof. Vishal A. Polara Prof. Vishal A. Polara
44 47

Prefix Evaluation Example:

Symbol Op1 Op2 Value Stack
9 - - - 9 2) Recursive case:
4 - - - 94  1) first the problem at hand is divided into simpler sub-
5 - - - 945
parts.
 2) Second the function calls itself but with sub-parts of
* 5 4 20 920
the problem obtained in the first step.
3 - - - 9203  3) Third, the result is obtained by combining the
2 - - - 92032 solutions of simpler sub-parts.
* 2 3 6 9206
+ 6 20 26 926
- 26 9 17 17
45 Prof. Vishal A. Polara 48 Prof. Vishal A. Polara

8
Unit-3 Stack 3/16/2022

Factorial and Fibonacci series

 1) Base case: is when n = 1, because if n = 1, the result will be 1
as
 1! = 1. int Fibonacci(int n)
 2) Recursive case: of the factorial function will call itself but with {
a smaller value of n, this case can be given as
 if ( n == 0 )
 factorial(n) = n × factorial (n–1)
return 0;
int Fact(int n) else if ( n == 1 )
{ return 1;
if(n==1)
return 1; else
else return ( Fibonacci(n–1) + Fibonacci(n–2) );
return (n * Fact(n–1));
}
}

49 Prof. Vishal A. Polara 52 Prof. Vishal A. Polara

Tower of Hanoi
Analysis of factorial using recursion  The tower of Hanoi is one of the main applications of
recursion. It was invented in 1883 by French mathematician
 Step 1: Specify the base case which will stop the lucas for 64 disk.
function from making a call to itself.  For example: The problem is to move all these rings show in
 Step 2: Check to see whether the current value being
fig. from pole A to pole C while maintaining the same order.
 There are two rules:
processed matches with the value of the base case. If
yes, process and return the value.  1) only one disk move at a time
 2) The smaller disk must always come above the larger disk.
 Step 3: Divide the problem into smaller or simpler sub-
 Solution:
problems.
 Base case: if n=1
 Step 4: Call the function from each sub-problem.  Move the ring from A to C using B as spare
 Step 5: Combine the results of the sub-problems.  Recursive case:
 Step 6: Return the result of the entire problem.  Move n – 1 rings from A to B using C as spare
 Move the one ring left on A to C using B as spare
50 Prof. Vishal A. Polara 53  Prof.
Move n – 1 rings from B to C using A as spare
Vishal A. Polara

Fibonacci series move(n, 'A', ‘B', ‘C');

void move(int n, char source, char spare, char dest)
 The Fibonacci series can be given as {
0 1 1 2 3 5 8 13 21 34 55 …… if (n==1)
printf("\n Move from %c to %c", source,dest);
 That is, the third term of the series is the sum of the first
else
and second terms. Similarly, fourth term is the sum of
{
second and third terms, and so on.
move(n–1,source,dest,spare);
 As per the formula, FIB(0) =0 and FIB(1) = 1. So we move(1,source,spare,dest);
have two base cases. This is necessary because every
move(n–1,spare,source,dest);
problem is divided into two smaller problems.
}
 FIB (n) = 0, if n = 0 }
 1, if n = 1 Time : 2^n - 1
 FIB (n – 1) + FIB(n – 2), otherwise
51 Prof. Vishal A. Polara 54 Prof. Vishal A. Polara

9
Unit-3 Stack 3/16/2022

Tower of Hanoi (recursion tree) Recursion vs Iterative approach

 Recursion is more of a top-down approach to problem
Tower(3, A,B,C) solving in which the original problem is divided into
smaller sub-problems.
 On the contrary, iteration follows a bottom-up approach
that begins with what is known and then constructing the
Tower(2, A,C,B) iv) A-C Tower(2, B,A,C) solution step by step.
 recursive programs may require substantial amount of
run-time and space overhead.
 While incase of iterative approach less time and space is
required.
 Iterative doesnot use stack while recursion use stack.
Tower(1, A,B,C) ii) A-B Tower(1, C,A,B) Tower(1, B,C,A) VI) B-C Tower(1, A,B,C)  Any iterative problem can solve recursively. Not all
i)A-C iii) C-B
V) B-A VII) A-C recursive problem can be solved by iteration.
 one must use recursion only to find solution to a
problem for which no obvious iterative solution is
known.
55 Prof. Vishal A. Polara 58 Prof. Vishal A. Polara

Total move for three disk Types of Recursion

1) A-C  There are basically three types of recursion
 1) direct or indirect recursion
2) A-B  A function is said to be directly recursive if it explicitly
3) C-B calls itself.
 Ex.
4) A-C
int Func (int n)
5) B-A {
6) B-C if (n == 0)
7) A-C return n;
else
return (Func (n–1));
}

56 Prof. Vishal A. Polara 59 Prof. Vishal A. Polara

 Indirect recursion: A function is said to be

indirectly recursive if it contains a call to another
function which ultimately calls it.
int Funcl (int n)
{
if (n == 0)
return n;
else
return Func2(n);
}
int Func2(int x)
{
return Func1(x–1);
}

57 Prof. Vishal A. Polara 60 Prof. Vishal A. Polara

10
Unit-3 Stack 3/16/2022

int Fibonacci(int num)

2) Tail Recursion {
if(num == 0)
 Tail Recursion: A recursive function is said to be tail return 0;
recursive if no operations are pending to be performed elseif(num==1)
when the recursive function returns to its caller. return 1;
int Fact(n) else
{ return (Fibonacci(num - 1) + Fibonacci(num – 2));
return Fact1(n, 1); }
Fibonacci(7) = Fibonacci(6) + Fibonacci(5)
}
…..
int Fact1(int n, int res) Fibonacci(2) = Fibonacci(1) + Fibonacci(0)
{ Now we have, Fibonacci(2) = 1 + 0 = 1
if (n == 1) Fibonacci(3) = 1 + 1 = 2
return res; …..
else Fibonacci(6) = 3 + 5 = 8
Fibonacci(7) = 5 + 8 = 13
return Fact1(n–1, n*res);
61 Prof. Vishal A. Polara 64 Prof. Vishal A. Polara

 In the code, Fact1 function preserves the syntax of

Fact(n). Here the recursion occurs in the Fact1 function Advantages and disadvantages of recursion
and not in Fact function.  Recursive solutions often tend to be shorter and
 Carefully observe that Fact1 has no pending operation to simpler than non-recursive ones.
be performed on return from recursive calls. The value  Code is clearer and easier to use.
computed by the recursive call is simply returned without
 Recursion works similar to the original formula to
any modification.
solve a problem.
 So in this case, the amount of information to be stored on
 Recursion follows a divide and conquer technique to
the system stack is constant (only the values of n and res
solve problems.
need to be stored) and is independent of the number of
recursive calls.  In some (limited) instances, recursion may be more
efficient.

62 Prof. Vishal A. Polara 65 Prof. Vishal A. Polara

3) Linear or Tree recursion Disadvantages

 In simple words, a recursive function is said to be
 For some programmers and readers, recursion is a
linearly recursive when the pending operation (if any) difficult concept.
does not make another recursive call to the function.
 Recursion is implemented using system stack. If the
 For example, observe the last line of recursive factorial
stack space on the system is limited, recursion to a
function. The factorial function is linearly recursive as deeper level will be difficult to implement.
the pending operation involves only multiplication to be
performed and does not involve another recursive call to  Aborting a recursive program in midstream can be a
Fact. very slow process.
 On the contrary, a recursive function is said to be tree  Using a recursive function takes more memory and
recursive (or non-linearly recursive) if the pending time to execute as compared to its non-recursive
operation makes another recursive call to the function. counterpart.
 For example, the Fibonacci function in which the  It is difficult to find bugs, particularly while using
pending operations recursively call the Fibonacci global variables.
function.
63 Prof. Vishal A. Polara 66 Prof. Vishal A. Polara

11
Unit-3 Stack 3/16/2022

Thank You

67 Prof. Vishal A. Polara

12