Stacks: Fundamentals and Applications
Stack
•
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
(
L
ast-
I
n,
F
irst-
O
ut).
Stack
OPERATIONS ON THE STACK
•
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.
STACK
•
DATA :- 10,20,30,40,50,60
•
PUSH 10
•
PUSH 20
•
PUSH 30
•
PUSH 40
•
PUSH 50
•
…..
40
30
20
10
TOP
TOP
TOP
TOP
STACK OPERATIONS
•
POPPED ELEMENTS
•
40
•
30
•
20
40
30
20
10
TOP
TOP
TOP
APPLICATIONS OF STACK
•
INFIX TO POSTFIX CONVERSION
•
INFIX TO PREFIX CONVERSION
•
STRING REVERSE
•
EVALUATION OF POSTFIX EXPRESSION
•
CHECK WHETHER THE EXPRESSION IS
VALID OR NOT
INFIX TO POSTFIX CONVERSION
•
EXPRESSIONS
•
Prefix: + a b
•
Infix: a + b
•
Postfix: a b +
Infix to Postfix Conversion
•
There are two methods
---- Manual method(Parenthesis)
----- stack method
Manual Method(Infix to Postfix)
•
A+b *d/e
•
A+(b *d)/e
•
A+((b *d)/e)
•
( A + ( ( b * d )/e ) )
ABD*E/+
Manual Method(Infix to Prefix)
•
A+b *d/e
•
A+(b *d)/e
•
A+((b *d)/e)
•
( A + ( ( b * d )/e ) )
+A/*BDE
Infix to Postfix using stack
A + B * C - D / E
Infix
Stack(bot->top)
Postfix
a) A + B * C - D / E
b) + B * C - D / E
A
c) B * C - D / E
+
A
d) * C - D / E
+
A B
e) C - D / E
+ *
A B
f) - D / E
+ *
A B C
g) D / E
+ -
A B C *
h) / E
+ -
A B C * D
i) E
+ - /
A B C * D
j)
+ - /
A B C * D E
k)
A B C * D E / - +
Infix to Prefix using stack
•
Reverse the infix string .
•
Replace ‘(‘ with ‘)’ and ‘)’ with ‘(‘.
•
Convert it to postfix.
•
Reverse the result.
Postfix evaluation
Operand: push
Operator: pop 2 operands, do the math, pop result
back onto stack
1 2 3 + *
Postfix
Stack( bot -> top )
a)
1 2 3 + *
b)
2 3 + *
1
c)
3 + *
1 2
d)
+ *
1 2 3
e)
*
1 5 // 5 from 2 + 3
f)
5
// 5 from 1 * 5
For more detail contact us
Stacks are linear data structures where all operations happen at one end — the top. They follow the Last-In, First-Out (LIFO) principle. This text delves into stack operations like push and pop, stack data management, and various applications such as infix to postfix conversion. Detailed methods and examples are provided for better comprehension and learning.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
STACK CHAPTER 03 Visit for more Learning Resources Visit for more Learning Resources
Stack 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).
OPERATIONS ON THE STACK 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.
STACK DATA :- 10,20,30,40,50,60 PUSH 10 PUSH 20 PUSH 30 PUSH 40 PUSH 50 .. 40 TOP TOP 30 20 TOP 10 TOP
STACK OPERATIONS POPPED ELEMENTS 40 30 20 40 TOP TOP 30 20 TOP 10
APPLICATIONS OF STACK INFIX TO POSTFIX CONVERSION INFIX TO PREFIX CONVERSION STRING REVERSE EVALUATION OF POSTFIX EXPRESSION CHECK WHETHER THE EXPRESSION IS VALID OR NOT
INFIX TO POSTFIX CONVERSION EXPRESSIONS Prefix: + a b Infix: a + b Postfix: a b +
Infix to Postfix Conversion There are two methods ---- Manual method(Parenthesis) ----- stack method
Manual Method(Infix to Postfix) A+b *d/e A+(b *d)/e A+((b *d)/e) ( A + ( ( b * d )/e ) ) ABD*E/+
Manual Method(Infix to Prefix) A+b *d/e A+(b *d)/e A+((b *d)/e) ( A + ( ( b * d )/e ) ) +A/*BDE
Infix to Postfix using stack A + B * C - D / E InfixStack(bot->top) a) A + B * C - D / E b) + B * C - D / E c) B * C - D / E d) * C - D / E e) C - D / E f) - D / E g) D / E h) / E i) E j) k) Postfix + - / + + + * + * + - + - + - / A A A B A B A B C A B C * A B C * D A B C * D A B C * D E A B C * D E / - +
Infix to Prefix using stack Reverse the infix string . Replace ( with ) and ) with ( . Convert it to postfix. Reverse the result.
Postfix evaluation Operand: push Operator: pop 2 operands, do the math, pop result back onto stack 1 2 3 + * Postfix a) b) c) d) e) f) Stack( bot -> top ) 1 2 3 + * 2 3 + * 3 + * + * * 5 1 1 2 1 2 3 1 5 // 5 from 2 + 3 // 5 from 1 * 5 For more detail contact us For more detail contact us
