Stack Operation In Data Structure

well prepared and detailed description of stack in data structure.
Also cover the topic of Infix, prefix and post fix notation...

1. By:
Divyesh Jagatiya
Hardik Gopani
Keshu Odedara

2. *Stacks are linear lists.
*All deletions and insertions occur at one
end of the stack known as the TOP.
*Data going into the stack first, leaves
out last.
*Stacks are also known as LIFO data
structures (Last-In, First-Out).
Quick Introduction

3. *PUSH – Adds an item to the top of a stack.
*POP – Removes an item from the top of the
stack and returns it to the user.
*PEEP – Find an item from the top of the
stack.
*Change(Update) – User can change the
contents of the specific element.
Basic Stack Operations

4. *Reversing Data: We can use stacks to reverse data.
(example: files, strings)
Very useful for finding palindromes.
Consider the following pseudo code:
1)read (data)
2)loop (data not EOF and stack not full)
1) push (data)
2) read (data)
3)Loop (while stack not Empty)
1) pop (data)
2) print (data)
Stack Applications

5. *Converting Decimal to Binary: Consider the following code
1)Read (number)
2)Loop (number > 0)
1) digit = number modulo 2
2) print (digit)
3) number = number / 2
// from Data Structures by Gilbert and Frozen
The problem with this code is that it will print the binary
number backwards. (ex: 19 becomes 11001000 instead of 00010011. )
To remedy this problem, instead of printing the digit right away, we can
push it onto the stack. Then after the number is done being converted, we
pop the digit out of the stack and print it.
Stack Applications

6. *Evaluating arithmetic expressions.
*Prefix: + a b
*Infix: a + b (what we use in grammar school)
*Postfix: a b +
*In high level languages, infix notation cannot be used
to evaluate expressions. We must analyze the
expression to determine the order in which we
evaluate it. A common technique is to convert a infix
notation into postfix notation, then evaluating it.
Stack Applications

7. PUSH
OPERATION

8. PUSH Algorithm
PUSH(S, Top, x)
Step 1: [Check For Stack Overflow]
if Top >= N
then write("Stack Overflow")
Exit
Step 2: [Increment Top pointer By
Value One]
Top  Top +1
Step 3: [Perform Insertion]
s[Top]  X
Step 4: [Finished]
Exit
N 
Top 0

9. PUSH Algorithm
PUSH(S, Top, x)
Step 1: [Check For Stack Overflow]
if Top >= N
then write("Stack Overflow")
Exit
Step 2: [Increment Top pointer By
Value One]
Top  Top +1
Step 3: [Perform Insertion]
s[Top]  X
Step 4: [Finished]
Exit
N 
Top  A

10. PUSH Algorithm
PUSH(S, Top, x)
Step 1: [Check For Stack Overflow]
if Top >= N
then write("Stack Overflow")
Exit
Step 2: [Increment Top pointer By
Value One]
Top  Top +1
Step 3: [Perform Insertion]
s[Top]  X
Step 4: [Finished]
Exit
N 
Top 
A
B

11. PUSH Algorithm
PUSH(S, Top, x)
Step 1: [Check For Stack Overflow]
if Top >= N
then write("Stack Overflow")
Exit
Step 2: [Increment Top pointer By
Value One]
Top  Top +1
Step 3: [Perform Insertion]
s[Top]  X
Step 4: [Finished]
Exit
N 
A
B
Top  C

12. PUSH Algorithm
PUSH(S, Top, x)
Step 1: [Check For Stack Overflow]
if Top >= N
then write("Stack Overflow")
Exit
Step 2: [Increment Top pointer By
Value One]
Top  Top +1
Step 3: [Perform Insertion]
s[Top]  X
Step 4: [Finished]
Exit
N 
Top 
A
B
C
D

13. PUSH Algorithm
PUSH(S, Top, x)
Step 1: [Check For Stack Overflow]
if Top >= N
then write("Stack Overflow")
Exit
Step 2: [Increment Top pointer By
Value One]
Top  Top +1
Step 3: [Perform Insertion]
s[Top]  X
Step 4: [Finished]
Exit
N 
Top 
A
B
C
D
Stack Overflow

14. Pop
OPERATION

15. POP Algorithm
N 
Top 
A
B
C
D
POP(S , Top)
Step 1: [Check For Stack Underflow Or
Check Whether Stack Is Empty]
if (Top = 0) OR (Top = -1)
then write("Stack Underflow")
Exit
Step 2: [Decrement Top pointer /
Remove The Top Information]
Value  S[Top]
Top  Top - 1
Step 3: [Return From Top Element Of The
Stack]
Write(value)
Step 4: [Finished]
Exit

16. POP Algorithm
N 
A
B
C
POP(S , Top)
Step 1: [Check For Stack Underflow Or
Check Whether Stack Is Empty]
if (Top = 0) OR (Top = -1)
then write("Stack Underflow")
Exit
Step 2: [Decrement Top pointer /
Remove The Top Information]
Value  S[Top]
Top  Top - 1
Step 3: [Return From Top Element Of The
Stack]
Write(value)
Step 4: [Finished]
Exit
Top 

17. POP Algorithm
N 
A
B
POP(S , Top)
Step 1: [Check For Stack Underflow Or
Check Whether Stack Is Empty]
if (Top = 0) OR (Top = -1)
then write("Stack Underflow")
Exit
Step 2: [Decrement Top pointer /
Remove The Top Information]
Value  S[Top]
Top  Top - 1
Step 3: [Return From Top Element Of The
Stack]
Write(value)
Step 4: [Finished]
Exit
Top 

18. POP Algorithm
N 
A
POP(S , Top)
Step 1: [Check For Stack Underflow Or
Check Whether Stack Is Empty]
if (Top = 0) OR (Top = -1)
then write("Stack Underflow")
Exit
Step 2: [Decrement Top pointer /
Remove The Top Information]
Value  S[Top]
Top  Top - 1
Step 3: [Return From Top Element Of The
Stack]
Write(value)
Step 4: [Finished]
Exit
Top 

19. POP Algorithm
N 
POP(S , Top)
Step 1: [Check For Stack Underflow Or
Check Whether Stack Is Empty]
if (Top = 0) OR (Top = -1)
then write("Stack Underflow")
Exit
Step 2: [Decrement Top pointer /
Remove The Top Information]
Value  S[Top]
Top  Top - 1
Step 3: [Return From Top Element Of The
Stack]
Write(value)
Step 4: [Finished]
ExitTop  0

20. POP Algorithm
N 
POP(S , Top)
Step 1: [Check For Stack Underflow Or
Check Whether Stack Is Empty]
if (Top = 0) OR (Top = -1)
then write("Stack Underflow")
Exit
Step 2: [Decrement Top pointer /
Remove The Top Information]
Value  S[Top]
Top  Top - 1
Step 3: [Return From Top Element Of The
Stack]
Write(value)
Step 4: [Finished]
ExitTop  0
Stack Underflow

21. PEEP
OPERATION

22. PEEP Algorithm
N 
Top 
A
B
C
D
PEEP(S, Top, i)
Step 1: [Check For Stack Underflow]
if (Top - i + 1) <= 0
then write("Stack Underflow")
Exit
Step 2: [Return The ith Element From
The Top Of The Stack]
X  S(Top - i + 1)
Step 3: [Finished]
Exit
Top  D

23. CHANGE
OPERATION

24. CHANGE Algorithm
N 
Top 
A
B
C
D
CHANGE(S, Top, X, i)
Step 1: [Check For Stack Underflow]
if (Top - i + 1) < 0
then write("Stack Underflow")
Exit
Step 2: [Change The Element Value
From The Top Of The Stack]
S(Top - i + 1)  X
Step 3: [Finished]
Exit

25. CHANGE Algorithm
N 
Top 
A
B
C
D1
CHANGE(S, Top, X, i)
Step 1: [Check For Stack Underflow]
if (Top - i + 1) < 0
then write("Stack Underflow")
Exit
Step 2: [Change The Element Value
From The Top Of The Stack]
S(Top - i + 1)  X
Step 3: [Finished]
Exit

26. POLISH
NOTATION

27. *Rules:
*Operands immediately go directly to output
*Operators are pushed into the stack (including parenthesis)
-Check to see if stack top operator is less than current operator
-If the top operator is less, than push the current operator onto stack
-If the top operator is greater than the current, pop top operator and push onto
stack, push current operator onto stack
-Priority 2: * /
-Priority 1: + -
-Priority 0: (
If we encounter a right parenthesis, pop from stack until we get
matching left parenthesis. Do not output parenthesis.
Infix to Postfix Conversion

28. A + B * C - D / E
Infix Stack Postfix
(
a)A ( A
b)+ (+ A
c)B (+ AB
d)* (+* AB
e)C (+* ABC
f)- (- ABC*+
g)D (- ABC*+D
h)/ (-/ ABC*+D
i)E (-/ ABC*+DE
j)) ABC*+DE/-

Infix to Postfix Example

29. A + B * C - D / E
Label No. Postfix Stack
1 A A
2 B A B
3 C A B C
4 * A B * C
5 + A + B * C
6 D A + B * C D
7 E A + B * C D E
8 / A + B * C D / E
9 - A + B * C – D / E
Postfix Evaluation