Dr.

Amol Pande
Computer Department
DMCE,Airoli

Unit-2

Stack

Dr. Amol Pande 1

Summary of Data Structure subject
 Stack
• Definition :
– Stack is a linear data structure in which data can
be inserted or deleted from one end called top.
– It is based on LIFO (i.e. Last in first out) order.
• Real world Examples:
– Stack of dishes
– Stack of CD’s
– Stack of Books
Stack using Array & its operations
• Operations on Stack

• Push (insert)
• Pop (remove/Delete)
• Top of stack
• Is Stack full
• Is Stack empty
 PUSH operation
• PUSH operation(insert value in stack)
– Input values are : 10,20,30,40,50
– Assume that initially stack is empty.
– Assume Size of stack is 5
 STACK ADT
• #include<stdio.h>
• #include<conio.h>
• Void main()
• {
• int stk[5];
• top = -1;
• void push(int val);
• int pop ();
• int topofstk();
• int isstkempty();
• int isstkfull();
• }
Implementation Stack Operations(PUSH)
#include<stdio.h> void push(int data)
#include<conio.h> {
Int size = 5; if (isFull())
int stack[size]; printf("Stack is full\n")
int top=-1; else
int isFull() {
{ top=top+1;
if (top==SIZE-1) stack[top]=data;
return 1; }
else }
return 0;
}
int isEmpty()
Size =5 Top 4 50
{
if (top == -1) Top 3 40
return 1; Top 2 30
else Top 1 20
return 0; Top 0 10
} Stack Empty Top =-1
int top()
{
return stack[top];
}
 Implementation Stack Operations (POP)
#include<stdio.h> void pop()
#include<conio.h> {
int stk[5]; int data;
int top=-1; if(isEmpty())
int isFull() printf("Stack is empty“);
{ else
if (top==SIZE) {
retuen 1; data=stack[top];
else top=top-1;
return 0; printf("the removed value is “, data);
} }
int isEmpty() }
{
Size =5 Top 4 50
if (top == -1)
return 1; Top 3 40
else Top 2 30
return 0; Top 1 20
} Top 0 10
int top() Stack Empty Top =-1
{
return stack[top];
}
 Implementation Stack using Array
#include<stdio.h>
#include<conio.h>
int stk[5]; int top=-1;
void main()
int isFull() {
{
if (top==SIZE) int opt,I,data;
retuen 1; printf(“Main Menu of Stack\n”);
else
return 0; while(1)
} { printf("\nPress 1. PUSH\t 2. POP
int isEmpty()
{ \t3.ISEmpty\t4.ISFull\t5.top\t6.Exit \n");
if (top == -1) return 1; scanf("%d",&opt);
else return 0;
} switch(opt)
int top() {
{
return stack[top]; case 1:
}
for(i=0;i<5;i++)
void push(int data) {
{ printf(“Enter the value to push\n”);
if (isFull())
printf("Stack is full\n") scanf(“%d”,data);
else push(data);
{
top=top+1; } break;
stack[top]=data; case 2: pop(); break;
}
} case 3: isEmpty(); break;
void pop()
{ int data;
case 4: isFull(); break;
if(isEmpty()) case 5: top(); break;
printf("Stack is empty“); case 6: exit(0);
else {
data=stack[top]; }
top=top-1; }
printf("the removed value is “, data);
} }
}
 Application 1 : Well-form-ness of parenthesis
• Example: • Case 1 : a + b  Valid
• Expression is collection of operand and
operators :
• a + b  Valid Expression Top 4
• (a + b)  Valid Expression Top 3

• (a + b  invalid Expression Top 2

Top 1
• ((a + b ) * (c + d))  valid Top 0
Expression Top -1
• ((a + b ) * (c + d)  invalid
Expression • Case 2 : (a+b)
• (a + b ) * (c + d))  invalid
Expression
• [(a + b ) * (c + d)]  valid Expression
• [(a + b ) * (c + d)}  invalid Expression
• {(a + b ) * (c + d)}  valid Expression
• {(a + b ) * (c + d))  invalid Expression

Top 0 (
Top -1
• (==) hence valid
Example on Well-form-ness of parenthesis(Program)
 Conversion of Expression
• Expression is a collection of Operands and operators.
• 3 types of Expressions :
1. Infix : when operator is in between two operands
• Example : a + b
2. Postfix/(Reverse-Polish) Notation: When operator is after
operands. Example a b +
3. Prefix/(Polish)Notation: When operator is before
operands. Example + a b
Expression Infix Expression Postfix Expression
No
1 5*6–(7+2) 56*72+ -
2 5+6–(7+2) 5 6+ 7 2 + -
3 5-6–(7+2) 56-72+ -
4 5-6+(7+2) 56-72+ -
5 5-6*(7+2) 56 72+ * -
 Examples to Convert Infix expression to Postfix expression
• Example No 1: Infix Expression : 5 * 6 - ( 7 + 2 )
0 1 2 3 4 5 6 7 8
5 * 6 - ( 7 + 2 )

Sr Scanned STACK Postfix Remark

no. Values
0 5 5 5 Value so directly post to postfix array
1 * * Stack empty , so push * to top of stack
2 6 56 6 Value so directly post to postfix array
3 - - 56* If (priority of operator in infix exp. i.e( - ) < = priority of
operator on top of stack i.e.(*) ) true..
Then Pop * and add to postfix exp. also push – to top of the
stack
else only push new opr. of infix exp. Push to top of the stack.
4 ( -( 56* Push ( to top of stack
5 7 -( 56*7 7 Value so directly post to postfix array
6 + -(+ 56*7 + operator push to stack above (
7 2 -(+ 56*72 2 Value so directly post to postfix array
8 ) - 56*72+ Closing ) so pop operators till ( bracket & post it postfix array

9 End of 5 6 *7 2 + - If EOE and stack is not empty , then pop operator and post it to
Expressi postfix array.
on
So Final Postfix Expression is 5 6 * 7 2 + -
 Examples to Convert Infix expression to Postfix expression
• Example No 2: Infix Expression : 5 + 6 - ( 7 + 2 )
0 1 2 3 4 5 6 7 8
5 + 6 - ( 7 + 2 )

Sr Scanned STACK Postfix Remark

no. Values

0 5 5 5 Value so directly post to postfix array

1 + + Stack empty , so push + to top of stack
2 6 56 6 Value so directly post to postfix array
3 - - 56+ If (priority of operator in infix exp. i.e( - ) < = priority of
operator on top of stack i.e.( +) ) true..
Then Pop * and add to postfix exp. also push – to top of the
stack
else only push new opr. of infix exp. Push to top of the stack.
4 ( -( 56+ Push ( to top of stack
5 7 -( 56+7 7 Value so directly post to postfix array
6 + -(+ 56+7 + operator push to stack above (
7 2 -(+ 56+72 2 Value so directly post to postfix array
8 ) - 56+72+ Closing ) so pop operators till ( bracket & post it postfix array
9 End of 5 6 +7 2 + If EOE and stack is not empty , then pop operator and post it to
Expression - postfix array.
So Final Postfix Expression is 5 6 + 7 2 + -
 Examples to Convert Infix expression to Postfix expression(Program)
• Example No 3: Infix Expression : 5 - 6 * ( 7 + 2 )
0 1 2 3 4 5 6 7 8
5 - 6 * ( 7 + 2 )

Sr Scanned STACK Postfix Remark

no. Values
0 5 5 5 Value so directly post to postfix array
1 - - Stack empty , so push - to top of stack
2 6 56 6 Value so directly post to postfix array
3 * -* 56 If (priority of operator in infix exp. i.e( * ) < = priority of
operator on top of stack i.e.(-) ) true..
Then so Pop * and add to postfix exp. also push – to top
of the stack
else only push new opr. of infix exp. Push to top of the
stack.
4 ( - *( 56 Push ( to top of stack
5 7 - * ( 567 7 Value so directly post to postfix array
6 + -*(+ 567 + operator push to stack above (
7 2 - *(+ 5672 2 Value so directly post to postfix array
8 } -* 5672+ Closing ) so pop + operators till ( bracket & post it postfix
array
9 End of 5672+ *- If EOE and stack is not empty , then pop operator and post
Expressi it to postfix array till end of stack.
on
So Final Postfix Expression is 5 6 7 2 + * -
 Recursion :Tower of Hanoi
Recursion : Function calling it self.
• It uses Stack
#include<stdio.h>

int fact(int);
int main()
{
int num;

printf("Enter a positive number to find its Factorial\n");

scanf("%d", &num);

printf("\nFactorial of %d is %d.\n", num, fact(num));

return 0;
}

int fact(int num)

{
if(num)
return(num * fact(num - 1));
else
return 1;
}