Unit- III
Stack
Prof. S.K. Kakde
Stack
A stack is a linear data structure that
follows the Last-In-First-Out
(LIFO) principle.
It behaves like a stack of plates, where
the last plate added is the first one to
be removed.
Think of it this way:
Pushing an element onto the stack is
like adding a new plate on top.
Popping an element removes the top
plate from the stack.
Stack
Stack
Stack as Abstract Data Type (ADT)
Defined by its operations, not
implementation
Operations:
push(x),
pop(),
peek(),
isEmpty(),
isFull()
Key Operations on Stack
Push: Adds an element to the top of
the stack.
Pop: Removes the top element from
the stack.
Peek: Returns the top element
without removing it.
IsEmpty: Checks if the stack is
empty.
IsFull: Checks if the stack is full (in
case of fixed-size arrays).
Applications of Stack
Recursion
Expression Evaluation and Parsing
Depth-First Search (DFS)
Undo/Redo Operations
Browser History
Function Calls
Representation of stack
An abstract data type (ADT) called a stack is
used to store data linearly. The only end of a
stack via which we may add or remove data is
the top of the stack.
The user of a data type does not need to be
aware of how that data type is implemented. For
instance, we have been using primitive values
such as int, float, and char data types only with
the understanding that these data types can
operate and be performed on without being
aware of how they are implemented.
Push
1. PUSH: begin
It stacks up a new if stack is full
item. return
A stack overflow endif
circumstance is else
when the stack is increment top
completely full.
stack[top] assign v
alue
end else
end procedure
POP
2. POP begin
It takes something if stack is empty
out of the stack. return
In the opposite
endif
sequence from which
they were pushed,
else
the things are store value of stack[
popped. top]
The condition is decrement top
referred to as an return value
underflow if the end else
stack is empty. end procedure
PEEK
3. PEEK: Algorithm:
The peek() is an
operation retrieves 1. START
the topmost element 2. return the
within the stack, element at the
without deleting it.
This operation is top of the
used to check the stack 3. END
status of the stack
with the help of the
top pointer.
Evaluation of Arithmetic
Expressions
Operands and operators are the
components of an arithmetic
expression.
The arithmetic expression may
additionally contain parenthesis such
as "left parenthesis" and "right
parenthesis," in addition to operands
and operators.
Example: A + (B – C)
Associativity
Operators Precedenc
e
^exponentiati Right to left
on Highest
Left to right
*Multiplication, Second
/division Highest
+ addition, – Left to
subtraction right Lowest
Evaluation
Evaluation of Arithmetic
Expression requires two steps:
1. Put the provided expression first in
special notation.
2. In this new notation, evaluate the
expression.
Notations
There are three notations to
represent an arithmetic expression:
1. Infix Notation
2. Prefix Notation
3. Postfix Notation
Infix Notation
Each operator is positioned between the
operands in an expression written using
the infix notation. Depending on the
requirements of the task, infix
expressions may be parenthesized or
not.
Example: A + B, (C – D) etc.
Because the operator appears between
the operands, all of these expressions are
written in infix notation
Prefix Notation
The operator is listed before the
operands in the prefix notation. Since
the Polish mathematician invented
this system, it is frequently referred
to as polish notation.
Example: + A B, -CD etc.
Because the operator occurs before
the operands in all of these
expressions, prefix notation is used.
Postfix Notation
The operator is listed after the
operands in postfix notation. Polish
notation is simply reversed in this
notation, which is also referred to as
Reverse Polish notation.
Example: AB +, CD+, etc.
All these expressions are in postfix
notation because the operator comes
after the operands.
Conversion
Infix To Postfix
Example:
Infix: a+b*c+d
Postfix: abc*+d+
cont..
cont..
cont..
cont..
cont..
cont..
Cont..
Cont..
cont..
cont..
cont..
Example:
A+B*C/D-E
A/B-C*D-E
a+b * d + e/f + a*d + c
(a+b) * d + e/(f + a*d) + c
Algorithm to Evaluate Prefix
Notation Using Stack
1. Read the given expression from right to left
using a for loop.
2. If the current character is an operand, push it
to the stack.
3. If the current character is an operator,
remove the top two characters from the
stack. Let’s say the removed characters are
operand1 and operand2. Now. evaluate
(operand1 operator operand2) and push the
solution back to the stack.
4. The last character in the stack after
traversing the complete prefix notation will be
the solution.
Expression: +9*26
Character | Stack | Explanation
6 6 6 is an operand,
push to Stack
2 6 2 2 is an operand,
push to Stack
* 12 (6*2) * is an operator,
pop 6 and 2, multiply
them and push result
to Stack
9 12 9 9 is an operand, push
to Stack
+ 21 (12+9) + is an operator, pop
12 and 9 add them and
push result to Stack
Result: 21
Prefix Evaluation
Example:
1. -+7*45+20
2. -+8/632
Postfix to Infix
The postfix notation is commonly
known as Reverse Polish notation.
Example:
Postfix: NM-XY+
Infix: (X + Y) (M – N)
Postfix Evaluation
Create a stack to store operands (or
values).
Scan the given expression from left to
right and do the following for every
scanned element.
• If the element is a number, push it into the stack.
• If the element is an operator, pop operands for
the operator from the stack. Evaluate the
operator and push the result back to the stack.
When the expression is ended, the
number in the stack is the final answer.
Consider the expression: exp = “2 3 1 * + 9 -“
Scan 2, it’s a number, So push it into stack. Stack
contains ‘2’.
Scan 3, again a number, push it to stack, stack now contains ‘2 3’
(from bottom to top)
Scan 1, again a number, push it to stack,
stack now contains ‘2 3 1’
Scan *, it’s an operator. Pop two operands from stack,
apply the * operator on operands.
We get 3*1 which results in 3.
We push the result 3 to stack. The stack now becomes
‘2 3’.
Scan +, it’s an operator. Pop two operands from stack,
apply the + operator on operands.
We get 3 + 2 which results in 5.
We push the result 5 to stack. The stack now becomes
‘5’.
Scan 9, it’s a number. So we push it to the stack.
The stack now becomes ‘5 9’.
Scan -, it’s an operator, pop two operands from stack,
apply the – operator on operands, we get 5 – 9 which
results in -4.
We push the result -4 to the stack.
The stack now becomes ‘-4’.
Precedence order
Operators Symbols
Parenthesis { }, ( ), [ ]
Exponential notation ^
Multiplication and *, /
Division
Addition and +, -
Subtraction
Associativity order
Operators Associativity
^ Right to Left
*, / Left to Right
+, - Left to Right
Associativity Rule
Example: 1 + 2*3 + 30/5
Since in the above expression, * and / have the
same precedence, so we will apply the associativity
rule.
As we can observe in the above table that * and /
operators have the left to right associativity, so we
will scan from the leftmost operator.
The operator that comes first will be evaluated first.
The operator * appears before the / operator, and
multiplication would be done first.
1+ (2*3) + (30/5)
Infix -> Prefix
Examples:
Input: A * B + C / D
Output: + * A B/ C D
Input: (A – B/C) * (A/K-L)
Output: *-A/BC-/AKL
Infix -> Prefix
A+B*C
First scan: In the above expression,
multiplication operator has a higher
precedence than the addition operator;
the prefix notation of B*C would be
(*BC).
A + *BC
Second scan: In the second scan, the
prefix would be:
+A *BC
Algorithm (Infix -> Prefix)
First, reverse the infix expression given in the
problem.
Scan the expression from left to right.
Whenever the operands arrive, print them.
If the operator arrives and the stack is found to be
empty, then simply push the operator into the stack.
If the incoming operator has higher precedence than
the TOP of the stack, push the incoming operator
into the stack.
If the incoming operator has the same precedence
with a TOP of the stack, push the incoming operator
into the stack.
If the incoming operator has lower precedence than
the TOP of the stack, pop, and print the top of the
stack. Test the incoming operator against the top of
the stack again and pop the operator from the stack
till it finds the operator of a lower precedence or
same precedence.
If the incoming operator has the same precedence
with the top of the stack and the incoming operator is
^, then pop the top of the stack till the condition is
true. If the condition is not true, push the ^ operator.
When we reach the end of the expression, pop, and
print all the operators from the top of the stack.
If the operator is ')', then push it into the stack.
If the operator is '(', then pop all the
operators from the stack till it finds )
opening bracket in the stack.
If the top of the stack is ')', push the
operator on the stack.
At the end, reverse the output.
Step 1: Reverse the infix expression. Note while
reversing each ‘(‘ will become ‘)’ and each ‘)’
becomes ‘(‘.
Step 2: Convert the reversed infix expression to
“nearly” postfix expression.
While converting to postfix expression, instead of using pop
operation to pop operators with greater than or equal
precedence, here we will only pop the operators from stack
that have greater precedence.
Step 3: Reverse the postfix expression.
The stack is used to convert infix expression to
postfix form.
Infix Postfix
Consider the infix expression exp =
“a+b*c+d”
Reverse a stack using
Recursion
Follow the steps mentioned below to
implement the idea:
1. Create a stack and push all the elements in
it.
2. Call reverse(), which will pop all the
elements from the stack and pass the popped
element to function insert_at_bottom()
3. Whenever insert_at_bottom() is called it will
insert the passed element at the bottom of
the stack.
4. Print the stack
The functions associated with
stack
empty() – Returns whether the stack is empty – Time
Complexity : O(1)
size() – Returns the size of the stack – Time Complexity : O(1)
top() – Returns a reference to the top most element of the
stack – Time Complexity : O(1)
push(g) – Adds the element ‘g’ at the top of the stack – Time
Complexity : O(1)
pop() – Deletes the most recent entered element of the stack
– Time Complexity : O(1)
Implementation of a
stack
class Stack:
# Peek at the top item of the
def __init__(self):
stack
[Link] = []
def peek(self):
# Push item onto the if not self.is_empty():
stack return [Link][-1]
def push(self, item): return "Stack is empty"
[Link](item) # Check if the stack is
empty
# Pop item from the def is_empty(self):
stack return len([Link]) ==
def pop(self): 0
if not self.is_empty():
return # Get the size of the stack
[Link]() def size(self):
return "Stack is empty" return len([Link])
stack = Stack()
[Link](10) Output:
[Link](20)
[Link](30)
print("Stack after pushing Stack after pushing
items:", [Link]) items: [10, 20, 30]
print("Popped item:", Popped item: 30
[Link]()) Top item after pop:
print("Top item after
pop:", [Link]())
20
print("Is stack empty?", Is stack empty? False
stack.is_empty()) Size of stack: 2
print("Size of stack:",
[Link]())
Video Link
https://
[Link]/watch?v=I37kGX-
nZEI
[Link]
v=rS-ZKTqwi90