Fundamentals of Data Structures
V
UNIT V Stack Stack
Revision
•Basic concept of stack
•Stack as an ADT
•Representation of stack using Array
•Application of Stack
•Infix to Postfix
Revision of Last Lecture
•Application of Stack
•Postfix Evaluation
•Linked Stack and Operations
•Recursion and Variants
UNIT V Stack
Data
Data Structure
What is Data Structures?
Data structure is a representation of data and the
operations allowed on that data.
•A data structure is a way to store and organize data in
order to facilitate the access and modifications.
•Data Structures are the method of representing of logical
relationships between individual data elements related to
the solution of a given problem.
Stack Data Structures
Stack Data Structures
Stack – Basic Concept
•Stack is a LIFO (last in first out) structure.
•It is an ordered list of the same type of elements.
•A stack is a linear list where all insertions and
deletions are permitted only at one end of the list.
•List of operations -
▫Initialize
▫Push
▫Pop
▫IsEmpty
▫IsFull
Stack – Basic Concept
•Push: Adds an item in the stack. If the stack is full,
then it is said to be an Overflow condition.
•Pop: Removes an item from the stack. The items
are popped in the reversed order in which they are
pushed. If the stack is empty, then it is said to be
an Underflow condition.
•Peek or Top: Returns top element of stack.
•isEmpty: Returns true if stack is empty, else false.
Stack – Basic Concept
•Push: Adds an item in the stack.
•Pop: Removes an item from the stack.
Stack – Example
•Describe the output of the following series of stack
operations
▫Push(8)
▫Push(3)
▫Pop()
▫Push(2)
▫Push(5)
▫Pop()
▫Pop()
▫Push(9)
▫Push(1)
Stack – Example
#include<iostream>
#include<ctype.h>
using namespace std;
class stack
{
int top;
char data[20];
public:
stack() {top=-1;}
}
Stack – Example
void push(int x)
{
top++;
data[top]=x;
}
int pop()
{
char x;
x=data[top];
top--;
return x;
Stack
Applications of Stack
•Infix to Postfix /Prefix conversion
•Reversing a string
•Balancing of symbols
•Redo-undo features at many places like editors,
photoshop.
•Forward and backward feature in web browsers
•Used in many algorithms like Tower of Hanoi,
tree traversals,
•stock span problem, histogram problem.
•Other applications can be Backtracking, Knight
tour problem, rat
•in a maze, N queen problem and sudoku solver
DSL Group - D
Infix to Postfix Conversion
•Read Infix expression left to right one character at
a time
•If input symbol operand then place it in postfix
expression
•If input Symbol ( - Push onto the stack
•If input Symbol operator - Push onto the stack
▫Check if Priority of operator in stack is grater than
the priority of incoming operator then place it in
postfix expression. Repeat step till ….
▫Otherwise Push operator onto the stack
▫If ) – pop all operator till (
•Finally pop all element
•Print postfix expression as a result
Infix to Postfix Conversion
Infix Expression - A*B+C
Input Action Stack Output/
Postfix
- - Empty -
A Print A - A
* Push * * A
B Print B * AB
+ Push + + AB*
C Print C + AB*C+
Infix to Postfix Conversion
Infix Expression –
(A+B)*(C-D)
Input Action Stack Output/
Postfix
- - Empty -
- - - -
- - - -
- - - -
- - - -
- - - -
- - - -
- - - -
Infix to Postfix Conversion
Infix Expression
(a+b)*d+e(f+a*d)+c
(a+(b*c/d)-e)
Infix to Postfix Conversion
Infix Expression
(a+b)*d+e(f+a*d)+c
ANS - ab+d*e+fad*+c+
(a+(b*c/d)-e)
ANS –abc*d/+e-
Input Action Stack Output/
Infix to Postfix Postfix
Conversion ( Push ( ( (
a Print a ( a
Infix Expression + Push + (+ a
b Print b (+ ab
(a+b)*d+e(f+a*d)+c ) Pop all until - ab+
( & print all
the content
* Push * * ab+
d Print d * ab+d
+ Push + & + ab+d*
Pop
e Print e + ab+d*e
( Push ( (+ ab+d*e
f Print f (+ ab+d*ef
+ Push + (++ ab+d*ef
a Print a (++ ab+d*efa
Infix to Postfix Conversion
Post fix expression is:
ab+d*efad*++c+
Infix to Postfix Conversion
Group - D
Infix to Postfix Conversion
int main()
{
stack s;
char infix[20],postfix[20];
cout<<"Enter the infix expression";
cin>>infix;
s.conversion(infix,postfix);
cout<<"Post fix expression is: "<<postfix;
return 0;
}
Infix to Postfix Conversion
#include<iostream>
#include<ctype.h>
using namespace std;
class stack
{
int top;
char data[20];
public:
stack()
{
top=-1;
}
Infix to Postfix Conversion
void conversion(char infix[20],char postfix[20])
{
int j=0,i;
char e,token,x;
for(i=0;infix[i]!='\0';i++)
{
token=infix[i];
if(isalnum(token))
{
postfix[j]=token;
j++;
}
Infix to Postfix Conversion
else
{
if(token=='(')
push(token);
else if(token==')')
{
while((x=pop())!='(')
{
postfix[j]=x;
j++;
}
Infix to Postfix Conversion
else{
e=topmost();
while(precedence(token)<=precedence(e) && !empty())
{
x=pop();
postfix[j]=x;
j++;
}
push(token);
}} }
while(!empty())
{
x=pop();
postfix[j]=x;
j++;
}
postfix[j]='\0';}
Infix to Postfix Conversion
void push(int x)
{
top++;
data[top]=x;
}
int pop()
{ char x;
x=data[top];
top--;
return x;
}
char topmost()
{
char e;
e=data[top];
return e;
}
Infix to Postfix Conversion
int precedence(char x)
{
if(x=='(')
return 0;
if(x=='+'|| x=='-')
return 1;
if(x=='*'|| x=='/' ||x=='%')
return 2;
else
return 3;
}
int empty()
{
if(top==-1)
return 1;
else
return 0;
}
UNIT V Stack
Infix to Postfix Conversion
Infix to Postfix Conversion
Infix to Postfix Conversion
Infix to Postfix Conversion
Fully Parenthesized Expression
•A FPE has exactly one set of Parentheses
enclosing each operator and its operands.
•Which is fully parenthesized?
(A+B)*C
( ( A + B) * C )
( ( A + B) * ( C ) )
Infix to Prefix Conversion
Move each operator to the left of its operands &
remove the parentheses:
( ( A + B) * ( C + D ) )
Infix to Prefix Conversion
Move each operator to the left of its operands &
remove the parentheses:
(+A B *(C+D))
Infix to Prefix Conversion
Move each operator to the left of its operands &
remove the parentheses:
*+A B (C +D)
Infix to Prefix Conversion
Move each operator to the left of its operands &
remove the parentheses:
*+A B +C D
Order of operands does not change!
Infix to Postfix
(((A+B)*C)-((D+E)/F))
A B+C* D E+F/-
•Operand order does not change!
•Operators are in order of evaluation!
Computer Algorithm
FPE Infix To Postfix
•Assumptions:
1.Space delimited list of tokens represents a FPE
infix expression
2.Operands are single characters.
3. Operators +,-,*,/
FPE Infix To Postfix
•Initialize a Stack for operators, output list
•Split the input into a list of tokens.
•for each token (left to right):
if it is operand: append to output
if it is '(': push onto Stack
if it is ')': pop & append till '('
FPE Infix to Postfix
(((A+B)*(C-E))/(F+G))
•stack: <empty>
•output: []
FPE Infix to Postfix
((A+B)*(C-E))/(F+G))
•stack: (
•output: []
FPE Infix to Postfix
(A+B)*(C-E))/(F+G))
•stack: ( (
•output: []
FPE Infix to Postfix
A+B)*(C-E))/(F+G))
•stack: ( ( (
•output: []
FPE Infix to Postfix
+B)*(C-E))/(F+G))
•stack: ( ( (
•output: [A]
FPE Infix to Postfix
B)*(C-E))/(F+G))
•stack: ( ( ( +
•output: [A]
FPE Infix to Postfix
)*(C-E))/(F+G))
•stack: ( ( ( +
•output: [A B]
FPE Infix to Postfix
*(C-E))/(F+G))
•stack: ( (
•output: [A B + ]
FPE Infix to Postfix
(C-E))/(F+G))
•stack: ( ( *
•output: [A B + ]
FPE Infix to Postfix
C-E))/(F+G))
•stack: ( ( * (
•output: [A B + ]
FPE Infix to Postfix
-E))/(F+G))
•stack: ( ( * (
•output: [A B + C ]
FPE Infix to Postfix
E))/(F+G))
•stack: ( ( * ( -
•output: [A B + C ]
FPE Infix to Postfix
))/(F+G))
•stack: ( ( * ( -
•output: [A B + C E ]
FPE Infix to Postfix
)/(F+G))
•stack: ( ( *
•output: [A B + C E - ]
FPE Infix to Postfix
/(F+G))
•stack: (
•output: [A B + C E - * ]
FPE Infix to Postfix
(F+G))
•stack: ( /
•output: [A B + C E - * ]
FPE Infix to Postfix
F+G))
•stack: ( / (
•output: [A B + C E - * ]
FPE Infix to Postfix
+G))
•stack: ( / (
•output: [A B + C E - * F ]
FPE Infix to Postfix
G))
•stack: ( / ( +
•output: [A B + C E - * F ]
FPE Infix to Postfix
))
•stack: ( / ( +
•output: [A B + C E - * F G ]
FPE Infix to Postfix
)
•stack: ( /
•output: [A B + C E - * F G + ]
FPE Infix to Postfix
•stack: <empty>
•output: [A B + C E - * F G + / ]
Infix to Postfix
•Initialize a Stack for operators, output list
•Split the input into a list of tokens.
•for each token (left to right):
if it is operand: append to output
if it is '(': push onto Stack
if it is ')': pop & append till '('
if it in '+-*/':
while peek has precedence ≥ it:
pop & append
push onto Stack
pop and append the rest of the Stack.
Conversion
•Infix to Postfix Conversion
•Postfix to Infix Conversion
•Postfix to Prefix Conversion
•Infix to Prefix Conversion
•Prefix to Infix Conversion
•Prefix to Postfix Conversion
Infix to Prefix
Infix to Prefix
Infix to Prefix
Infix to Prefix
Infix to Prefix and postfix
Infix to Prefix and postfix
Postfix to Infix
•pqr-+st-xy-z+/*
Postfix to Prefix
•pqr-+st-xy-z+/*
Prefix to Infix
•*+p-qr/-st+-uvw
Prefix to Infix
•*+p-qr/-st+-uvw
•(p+q-r)*(s-t)/(u-v+w)
Prefix to Postfix
•*+a-bc/-de+-fgh
Prefix to Postfix
•*+a-bc/-de+-fgh
•abc-+de-fg-h+/*
UNIT V Stack
Applications of Stack
•Infix to Postfix /Prefix conversion
•Reversing a string
•Balancing of symbols
•Redo-undo features at many places like editors,
photoshop.
•Forward and backward feature in web browsers
•Used in many algorithms like Tower of Hanoi,
tree traversals,
•stock span problem, histogram problem.
•Other applications can be Backtracking, Knight
tour problem, rat
•in a maze, N queen problem and sudoku solver
DSL Group - D
Balancing of symbols
The contents of a stack during the scan of an expression that contains
the balanced delimiters { [ ( ) ] }
Balancing of symbols
The contents of a stack during the scan of an expression that contains
the unbalanced delimiters [ ( ) ] }
DSL Group - D
Need for Prefix and Postfix
Expressions
•Operators are no longer ambiguous with respect
to the operand
•Order of operations within prefix and postfix
expressions is completely determined by only the
position of the operator
•During compilation of expression, infix
expression is converted to postfix form first and
then it is evaluated
Postfix Expression Evaluations
Postfix Expression Evaluations
•AB+C-BA+C$-
▫For A=1, B=2, C=3
Postfix Expression Evaluations
•ABC+*CBA-+*
▫For A=1, B=2, C=3
Postfix Expression Evaluations
Postfix Expression Evaluations
UNIT V Stack
Linked Stack and Operations
•Stack by using Linked List
•Size of stack
•Node structure for linked stack
Struct node
{
Int data
Struct node *next
}node;
Linked Stack and Operations
Struct node
{
Int data
Struct node *next
}node;
Linked Stack and Operations
Write C++ Program for implementation of
Stack using Linked List
Recursion
