Stack ppt file of Stack DSA For lab in the lab of DSA lecture and Lab.ppt

Data Structures & Algorithms
STACK

Specifications/ADT of Stack
 What is Stack?
 Representation of Stacks
 Operations on Stacks
 Push
 Pop
 IsEmpty
 IsFull
Usage
 Evaluation of Expressions
 Infix to Postfix Conversion
 Limited by Array (Fixed Size)
 Link List (Dynamic and Variable size)

What is Stack?
 In QUEUES, insertion and deletion can take place
at both ends, i.e. start and end,
 But if insertion and deletion are restricted from one
end, must used concept of STACK.
Stack can be defined as:
 A stack is a linear data structure which
can be accessed only at one of its ends
for storing and retrieving data
 In which items may be inserted or deleted only
from one end called top of the stack.
 There are two ways of implementing a stack:

Description of Stack
 Stack: A stack is an ordered collection
of items into which items may be
inserted or may be deleted from the
same end.
 Last in First Out (LIFO Structure)
 Conceptual data structure
 Empty_stack () and top_of_stack()
methods just tell the state of stack,
never change the state of stack

 Examples
 Function calls
 Recursion
 Expression evaluation
 Infix expression is that expression in which
operator lies between operands i.e a=b+c
 Postfix expression, in which operator
follows the operands
 Prefix expression in which operator accedes
the operands

 A common model of a
stack is a plate or coin
stacker. Plates are
"pushed “onto to the top
and "popped" off from
the top.
 Stack principle Last-In-
First-Out (LIFO)
queues.

Stack terminology
“Top”: where insertion and
deletion takes place
“Push”: is the term used to insert an
element into a stack
“Pop”: is the term used to delete an
element from a stack.

Basic operations of a Stack
New Push
Pop Is full
?
Empty stack ?

Implementation of Stacks
 A stack can be implemented using an array
(static & dynamic) and by Link List (Dynamic).
 A pointer variable TOP which contains the
location of the top element of the stack
 Variable STKSIZE which gives the maximum
number of elements that can be held by the
stack.

 Note that all operations need to check
array bounds
 Pushing onto a full stack: Overflow
 When TOP=STKSIZE
 Popping an empty stack: Underflow
 TOP=NULL
Stack implementation
(Constraints/Limitations)

Operations on Stack
 A stack is generally implemented with only
two common operations:
 Push(): adds an item to a stack
 Pop(): extracts/delete the most recently pushed
item from the stack
 Other methods such as
 Top(): returns the item at the top without
removing it i.e. it tells the state
 IsEmpty(): determines whether the stack has
anything in it, so its return type is TRUE/FALSE
 IsFull(): determines whether the stack is full or
stacksize is reached to STKSIZE anything in it

How the stack routines work
empty stack; push(a); push(b); pop(b);
empty stack
top = 0
a
push(a)
top = 1
b
a
push(b)
top = 2
a
pop()
top = 1

Implementation of Stack
(ByUsing Array)
const int STKSIZE = 5;
class cstack
{
private:
int top; //Represents index of array
int STK[STKSIZE];
public:
cstack() {top = -1;}
void push(int x);
int pop();
int emptystack(); //returns true/false
int stacktop(); //tells top most values
};

Implementation of Push()
Operation
void cstack::push(int x)
{
if(top == 4)
{
cout<<“STACK is OVERFLOW”;
return;
}
STK[++top]=x;
}

Implementation of pop()
Operation
void cstack::pop()
{
if(emptystack())
{
cout<<“STACK is EMPTY”;
return -1;
}
return STK[top--];
}

Implementation of
emptystack() Operation
int cstack::emptystack ()
{
if (top = -1)
return 1;
else
return 0;
}

Implementation for return the
top of stack value
void cstack::stacktop()
{
if(emptystack())
{
cout<<“STACK is EMPTY”;
return top;
}
retun STK[top];
}

main() function
void main()
{
cstack stack;
stack.push(5); stack.push(10); stack.push(15);
stack.push(20); stack.push(25); stack.push(30);
stack.pop(); stack.pop(); stack.pop();
stack.emptySTK();
stack.stacktop();
getch();
}

Implementation of Stack
(ByUsing Link List)
struct node{int info; node *link;};
class cstack
{
private:
node *top;
public:
cstack() {top = NULL;}
void push(int);
int pop();
int emptystack();
int stacktop();
};

Implementation of Push()
Operation
void cstack::push(int x) //add first node
{
node *p;
p=new node;
p->info=x;
p->link=top;
top=p;
}

Implementation of pop()
Operation
void cstack::pop()
{if(top=NULL)
{ cout<<“STACK is EMPTY”;
return 0; }
node *p;
p=top;
top=top->link;
int temp=p->info;
delete p;
return temp;}

Implementation for return the
top of stack value
void cstack::stacktop()
{
int temp;
temp=pop();
push(temp);
return temp;
}

How can you define Expressions?
 Arithmetic expression is made up
 Operands (Numeric Variables or
Constants)
 e.g. A+B*C
 Arithmetic Operators (+, -, *, /)
 Power Operator (^)
 Parentheses ()
 The Expression is always evaluated
from left to right

How Expressions are executed?
 Order in which the expression is evaluated is:
 If the expression has parenthesis, then they are
evaluated first
 Exponential (^) is given highest priority
 Multiplication (*) and division (/) have the next
highest priority
 Addition (+) and subtraction (-) have the lowest
priority

Evaluation of Expression
 Steps to evaluate the following expression:
 (2^3 + 6) * 2 – 9 / 3
 = (8 + 6) * 2 – 9 / 3
 = 14 * 2 – 9 / 3
 = 28 – 3
 = 25

Infix, Prefix (Polish) and Postfix
(Reverse Polish) Notations
Infix Prefix
(Polish Notation)
Postfix
(Reverse Polish
Notation)
A+B +AB AB+
A*B *AB AB*
A/B /AB AB/
A-B -AB AB-

Infix to Postfix Conversion
 Stack is used to convert an infix expression to postfix.
 Stack is also used to store operators and operands and then
pass to the postfix expression according to their precedence.
 Infix expression is converted into postfix expression according
to the following rules:
 Infix expression is scanned from left to right until end of the
expression.
 Operands are passed directly to the output.
 Operators are first passed to the stacks.
 Operand is encountered, it is added to the output.

 Each time an operator is read, the stack is repeatedly popped
and operands are passed to the output, until an operator is
reached that has a lower precedence than the most recently
read operator. The most recently read operator is then pushed
into the stack.
 When end of the infix expression is reached, all operators
remaining in the stack are popped and passed to the output in
the same sequence.
 Parentheses can be used in the infix expression but these are
not used in the postfix expression.
 During conversion process, parentheses are treated as
operators that have higher precedence than any other
operator.

 Left parenthesis is pushed into the stack, when
encountered.
 Right parenthesis is never pushed to the stack.
 Left parentheses is popped only when right
parentheses is encountered.
 The parentheses are not passed to the output postfix
expressions. They are discarded.
 When end of expression is reached, then all
operators from stack are popped and added to the
output.

Infix to Postfix
Conversion(Precedence Rules)
 prced(‘*’, ‘/’, ‘+’ ) = true
 prced(‘+’, ‘*’ ) = false
 prced(‘*’, ‘*’ ) = true
 prced(‘*’, ‘/’ ) = true
 prced(‘(’, any operator ) = false
 prced(any operator, ‘(‘ ) = false
 prced(any operator,’)’ ) = true
 prced(‘)’, any operator) = undefined
 prced(‘(’, ‘)’ ) = false

Example (Infix to Postfix
Conversion)
Convert infix expression A+B*C+
(D*E+F)*G into postfix
A + B * C + ( D * E + F ) * G
1. Scanned from left to right. First
operand read is A and passed to
output
Stack
Output: A

Conversion)
A + B * C + ( D * E + F ) * G
2. Next the ‘+’ operator is read, at
this stage, stack is empty.
Therefore no operators are
popped and ‘+’ is pushed into the
stack. Thus the stack and output
will be:
+
Stack
Output: A

Conversion)
A + B * C + ( D * E + F ) * G
3. Next the ‘B’ operand is read and
passed to the output. Thus the
stack and output will be:
+
Stack
Output: AB

Conversion)
A + B * C + ( D * E + F ) * G
4. Next the ‘*’ operator is read, The
stack has ‘+’ operator which has
lower precedence than the ‘*’
operator. Therefore no operators
are popped and ‘*’ is pushed into
the stack. Thus the stack and
output will be:
*
+
Stack
Output: AB

Conversion)
A + B * C + ( D * E + F ) * G
5. Next the ‘C’ operand is read and
*
+
Stack
Output: ABC

Conversion)
A + B * C + ( D * E + F ) * G
6. Next the ‘+’ operator is read, The
stack has ‘*’ operator which has
higher precedence than the ‘+’
operator. The Stack is popped and
passed to output. Next stack has
‘+’ operator which has same
precedence than the ‘+’ operator.
The Stack is popped and passed to
output. Now stack is empty,
therefore no operators are popped
and ‘+’ is pushed into the stack.
Thus the stack and output will be:
+
Stack
Output: ABC*+

Conversion)
A + B * C + ( D * E + F ) * G
7. Next the left parenthesis ‘(’ is
read, Since all operators have
lower precedence than the left
parenthesis, it is pushed into the
will be:
(
+
Stack
Output: ABC*+

Conversion)
A + B * C + ( D * E + F ) * G
8. Next the ‘D’ operand is read and
(
+
Stack
Output: ABC*+D

Conversion)
A + B * C + ( D * E + F ) * G
9. Next the ‘*’ operator is read.
Now, left parenthesis ‘(‘ has
higher precedence than ‘*’; it can
not be popped from the stack
until a right parenthesis ‘)’ has
been read. Thus the stack is not
popped and ‘*’ is pushed into the
will be:
*
(
+
Stack
Output: ABC*+D

Conversion)
A + B * C + ( D * E + F ) * G
10. Next the ‘E’ operand is read and
*
(
+
Stack
Output: ABC*+DE

Conversion)
A + B * C + ( D * E + F ) * G
11. Next the ‘+’ operator is read, The
stack has ‘*’ operator which has
higher precedence than the ‘+’
operator. The Stack is popped
and passed to output. Next stack
has left parenthesis ‘(’ which has
not been popped and ‘+’ operator
is pushed into the stack. Thus the
+
(
+
Stack
Output: AB*+DE*

Conversion)
A + B * C + ( D * E + F ) * G
12. Next the ‘F’ operand is read and
+
(
+
Stack
Output: ABC*+DE*F

Conversion)
A + B * C + ( D * E + F ) * G
13. Next the ‘)’ has encountered
now popped till ‘( ‘ and passed to
the output. Thus the stack and
output will be:
+
Stack
Output: ABC*+DE*F+

Conversion)
A + B * C + ( D * E + F ) * G
14. Next the ‘*’ operator is read, The
stack has ‘+’ operator which has
lower precedence than the ‘*’
operator. Therefore no operators
are popped and ‘*’ is pushed into
the stack. Thus the stack and
output will be:
*
+
Stack
Output: ABC*+DE*F+

Conversion)
A + B * C + ( D * E + F ) * G
15. Next the ‘G’ operand is read and
*
+
Stack
Output: ABC*+DE*F+G

Conversion)
A + B * C + ( D * E + F ) * G
16. The end of expression is
encountered. The operators are
popped from the stacked and
passed to the output in the same
sequence in which these are
popped. Thus the stack and
output will be:
Stack
Output: ABC*+DE*F+G*+

Convert the following infix
expressions into postfix expressions
 A$B*C-D+E/F/(G+H)
 (A+B)*(C$(D-E)+F)-G
 (A+B)*(C-D)
 A-B/(C*D$E)
 ((A+B)*C-(D-E))$(F+G)
 A+B*C+(D*E+F)*G
 X+6*(Y+Z)^3
 (((A-(B+C))*D)$(E+F)
 A+(((B-C)*(D-E)+F)/G)$(H-J)

Algorithm (for Infix to Postfix
Conversion) Simple
 Initialize a Stack for operators, output list
 Split the input into a list of symbols.
 for each symbol (left to right):
if it is operand: add to output
if it is '(': push onto Stack
if it is ')': pop & add till '('
if it has '+-*/':
while peek has precedence ≥ it:
pop & add
push onto Stack
pop and add the rest of the Stack.

Algorithm (for Infix to Postfix
Conversion) Most Efficient
stk = empty stack
symb = Read the first character
while(!end of string)
{
if(symb is an operand)
add symb to the postfix string
else
{
while((!empty stack()) && prced(stacktop(), symb))
{top symb = pop(stk);
add symb to the postfix string}
if(empty stack(), || symb!=‘)’)
push(stk, symb)
else
top symb = pop(stk);//end of else
}
symb = get the next char
}//end of while
While(!empty stack())
{top symb=pop(stk);
Add top symb to the postfix string}

Evaluation of Expression
 Computer evaluates an expression given in infix notation by
converting it into postfix notation.
 Stack is used to perform this operation
 Following steps are taken to evaluate a postfix expression:
 Expression is scanned from left to right until the end of the
expression
 When an operand is encountered, it is pushed into stack
 When an operator is encountered, then
 Top two operands of stack are removed
 Arithmetic operation is performed
 Computed result is pushed back to the stack
 When end of the expression is reached, the top value from the
stack is picked. It is the computed value of the expression

Example (Evaluation of Expression)
Postfix Expression
A B C * + D E * F + G * +
A=5, B=6, C=9, D=2, E=4, F=8, G=3
2. Scanned from left to right. In first,
second and third iteration, the value
of A, B and C are pushed into the
stack. Thus the stack will be: 9
6
5
Stack

Postfix Expression
A B C * + D E * F + G * +
A=5, B=6, C=9, D=2, E=4, F=8, G=3
2. In fourth iteration, the operator ‘*’ is
read. So the two values ‘9’ and ‘6’
are popped from the stack and
multiplication is perform. i.e 9*6=54.
The computed value pushed back to
the stack. Thus the stack will be:
54
5
Stack

Postfix Expression
A B C * + D E * F + G * +
A=5, B=6, C=9, D=2, E=4, F=8, G=3
3. In fifth iteration, the operator ‘+’ is
addition is perform. i.e 54+5=59.
59
Stack

Postfix Expression
A B C * + D E * F + G * +
A=5, B=6, C=9, D=2, E=4, F=8, G=3
4. In sixth and seventh iteration, the
value of D and E are pushed into the
stack. Thus the stack will be:
4
2
59
Stack

Postfix Expression
A B C * + D E * F + G * +
A=5, B=6, C=9, D=2, E=4, F=8, G=3
5. In eighth iteration, the operator ‘*’ is
multiplication is perform. i.e 2*4=8.
8
59
Stack

Postfix Expression
A B C * + D E * F + G * +
A=5, B=6, C=9, D=2, E=4, F=8, G=3
6. In ninth iteration, the value of F is
pushed into the stack. Thus the stack
will be:
8
8
59
Stack

Postfix Expression
A B C * + D E * F + G * +
A=5, B=6, C=9, D=2, E=4, F=8, G=3
7. In tenth iteration, the operator ‘+’ is
addition is perform. i.e 8+8=16. The
computed value pushed back to the
stack. Thus the stack will be:
16
59
Stack

Postfix Expression
A B C * + D E * F + G * +
A=5, B=6, C=9, D=2, E=4, F=8, G=3
8. In eleventh iteration, the value of G
is pushed into the stack. Thus the
stack will be:
3
16
59
Stack

Postfix Expression
A B C * + D E * F + G * +
A=5, B=6, C=9, D=2, E=4, F=8, G=3
9. In twelve iteration, the operator ‘*’ is
multiplication is perform. i.e
3*16=48. The computed value
pushed back to the stack. Thus the
stack will be:
48
59
Stack

Postfix Expression
A B C * + D E * F + G * +
A=5, B=6, C=9, D=2, E=4, F=8, G=3
10. In thirteen iteration, the operator ‘+’
is read. So the two values ‘48’ and
‘59’ are popped from the stack and
addition is perform. i.e 48+59=107.
107
Stack

A + B * C + ( D * E + F ) * G
A=5, B=6, C=9, D=2, E=4, F=8, G=3
= 5 + 6 * 9 + (2 * 4 + 8) * 3
= 5 + 54 + (8 + 8) * 3
= 59 + 16 * 3
= 59 + 48
=107

Algorithm (for evaluating the Postfix)
stk = empty stack
symb = get the first value
while(!end of string)
{
Push(stk, symb);
else
{
operand 2 = pop(stk());
operand 1= pop(stk());
result = apply symb to operand 1 && operand 2
push(stk, result);
} //end of else
symb = get the next value
}// end of while
return(pop(stk));

Infix to Prefix
 For Infix to Prefix conversion
 Read the input string from right to left.
OR
 Convert Infix to Postfix, then reverse the
output string
 Do it Yourself????????

Prefix to Postfix Conversion
push(stk, symb);
else{
operand1 = pop(stk);
operand2 = pop(stk);
strcat(operand1, operand2, symb);
push(operand);
}
return(pop(stk));

Stack ppt file of Stack DSA For lab in the lab of DSA lecture and Lab.ppt

Recommended

More Related Content

Similar to Stack ppt file of Stack DSA For lab in the lab of DSA lecture and Lab.ppt (20)

More from aamirali1061a (8)

Recently uploaded (20)

Stack ppt file of Stack DSA For lab in the lab of DSA lecture and Lab.ppt