Data Structure and Algorithm (DSA)

Rajarshi Janak University (RJU)

BSc CSIT [Third Semester]

Prepared by:
Er. Madan Kadariya

NCIT
2

Chapter 2:
Stack(4 hrs)

Data Structure and Algorithms (DSA) NCIT 12/14/25

3

Outline
1. Introduction to Stack
2. Stack as an ADT
3. Stack Operations:
1. Push , Pop
4. Expression Conversion and Evaluation using stack
5. Applications of Stack

Data Structure and Algorithms (DSA) 12/14/25

 4 Introduction to Stack
— A Stack ADT (Abstract Data Type) is a linear data structure that follows the LIFO (Last In, First
Out) principle.
— This means the last element inserted into the stack is the first one to be removed.
— Access is allowed only at one point of the structure, normally termed the top of the stack
— access to the most recently added item only
Characteristics of Stack ADT
— Linear structure – elements are arranged in a sequential order.
— Restricted access – insertion and deletion allowed only at the top.
— Follows LIFO rule – last pushed, first popped.
— Single pointer/top variable – tracks the current top position.
— Efficient operations – push and pop run in O(1) time.
Key Operations
• Push(): Adds an element to the top of the stack.
• Pop(): Removes the top element from the stack and returns it.
• Peek (or Top): Returns the top element of the stack without removing it.
Data Structure and Algorithm Design (MCE/CS) NCIT 12/14/25
 5 Introduction to Stack
Basic Stack Operations in Stack ADT
1. push(S,x) - Adds an element x to the top of the stack , S. If the stack is full (in array
implementation),overflow occurs.
2. pop(S) - Removes and returns the top element. If the stack is empty, underflow occurs.
3. traverse(S) - Read each elements from stack S at once.
4. peek(S)/top(S) - Returns the top element from the stack S without removing it.
5. isEmpty(S) - Returns true if the stack S contains no elements.
6. isFull(S) (used in array implementation) - Returns true if the stack S cannot store new elements.
7. makeNull (S) - Make stack S is an empty stack.
8. search() - Get the location of item X in stack S.
9. etc
Advantages of Stack ADT Limitations
— Simple and easy to implement • Not suitable for random access
• Array-based stack has fixed size unless dynamic
— Ensures controlled access (safe memory usage)
arrays are used
— Efficient O(1) operations

Data Structure and Algorithm Design (MCE/CS) NCIT 12/14/25

 6
Stack
Static Implementation (Using Array)
Assuming a stack named STACK of size MAX with the TOP pointer that points to the top most element
of the stack and ITEM is the data item to be pushed.
Algorithm for Push
1. If TOP = MAX – 1, then:
1.1. Display “The stack is in overflow condition”
1.2. return/exit
2. TOP = TOP + 1
3. STACK [TOP] = ITEM Time Complexity
4. return/exit • Push: O(1)
• Pop: O(1)
Algorithm for POP • Peek: O(1)
1. If TOP < 0, then • IsEmpty: O(1)
1.1. Display “The Stack is empty”
1.2. return/exit
2. Else remove the Top most element
2.1 ITEM = STACK[TOP]
2.2 TOP = TOP – 1 Space complexity
5. return/exit • Depends on the number of elements it contains,
typically O(n) for storing n elements.

Data Structure and Algorithm Design (MCE/CS) NCIT 12/14/25

 7 Expression
Infix, Prefix and Postfix Notation
— Infix notation: The operator symbol is placed between two operand. E.g. A+B
— Prefix notation: The operator symbol is placed before two operand E.g. +AB
— Postfix Notation: The operator is placed after two operand E.g. AB+
— Using infix notation, if the expression consists of more than one operator and brackets, the precedence rule
(BODMAS) should be applied to decide which operator or which section of expression are evaluated first.
— The computer usually evaluates an infix expression first by converting it to postfix and evaluating the postfix
expression by using stack.
— As soon as an operator appears in the postfix expression during scanning of postfix expression the topmost
operands are popped off and are calculated by applying the encountered operator.
 8 Expression
Conversion of Infix to Postfix Expression without stack
The method of converting infix expression A + B * C to postfix form is:
A+B*C Infix Form
A + (B * C) Parenthesized expression
A + (B C *) Convert the multiplication
A (B C *) + Convert the addition
ABC*+ Postfix form
The rules to be remembered during infix to postfix conversion are:
1. Parenthesize the expression starting from left to light.
2. During parenthesizing the expression, the operands associated with operator having higher precedence
are first parenthesized. For example in the above expression B * C is parenthesized first before A + B.
3. The sub-expression (part of expression), which has been converted into postfix, is to be treated as single
operand.
4. Once the expression is converted to postfix form, remove the parenthesis.

Data Structure and Algorithms (DSA) 12/14/25

 9 Expression
Convert the following Infix Expression into Postfix expression without using stack.
Q1: A + [(B + C) + (D + E) * F] / G Solution: Evaluation order is
Q2: (A + B) * C / D + E ^ A / B A + { [ (BC +) + (DE +) * F ] / G}
A + { [ (BC +) + (DE + F *] / G}
A + { [ (BC + (DE + F * +] / G} .
ANS Q1: ABC + DE + F * + G / + A + [ BC + DE + F *+ G / ]
ANS Q2: AB + C * D / EA ^ B / + ABC + DE + F * + G / +

Solution: Evaluation order is

[(AB + ) * C / D ] + [ (EA ^) / B ]
[(AB + ) * C / D ] + [ (EA ^) B / ]
[(AB + ) C * D / ] + [ (EA ^) B / ]
(AB + ) C * D / (EA ^) B / +
AB + C * D / EA ^ B / +

Data Structure and Algorithms (DSA) 12/14/25

10 Expression
Algorithm for Converting Infix Expression to Postfix Expression Using Stack
— Suppose Q is an arithmetic expression written in infix notation, and P is the
expression written in postfix notation, then algorithm that finds the equivalent postfix
expression is given below:
1. Push “(” onto stack, and add“)” to the end of P.
2. Scan P from left to right and repeat Steps 3 to 6 for each element of P until the stack
is empty.
3. If an operand is encountered, add it to Q.
4. If a left parenthesis is encountered, push it onto stack.
5. If an operator ⊗ is encountered, then:
i. Repeatedly pop from stack and add P each operator (on the top of stack),
which has the same precedence as, or higher precedence than ⊗.
ii. Add ⊗ to stack.
6. If a right parenthesis is encountered, then:
i. Repeatedly pop from stack and add to P (on the top of stack until a left parenthesis is
encountered.
ii. Remove the left parenthesis. [Do not add the left parenthesis to P.]
1. Exit
— Note: Special character ⊗ is used to symbolize any operator in P.
Data Structure and Algorithms (DSA) 12/14/25
11 Infix to Postfix Conversion Using Stack
Consider the following arithmetic infix expression P
P=A+(B/C-(D*E$F)+G)*H
Character Scanned Stack Postfix String
A ( A
+ ( + A
( ( + ( A
B ( + ( AB
/ ( + ( / AB
C ( + ( / ABC
- ( + ( - ABC/
( ( + ( -( ABC/
D ( + ( -( ABC/D
* ( + ( -( * ABC/D
E ( + ( -( * ABC/DE
$ ( + ( -( *$ ABC/DE
F ( + ( -( *$ ABC/DEF
) ( + ( - ABC/DEF$*
+ ( + ( + ABC/DEF$* -
G ( + ( + ABC/DEF$* - G
) ( + ABC/DEF$* - G+
* ( + * ABC/DEF$* - G+
H ( + * ABC/DEF$* - G + H
) ABC/DEF$*- G + H * +
Data Structure and Algorithms (DSA) 12/14/25
12 Infix to Postfix Conversion Using Stack
Convert the following Infix Expression into postfix expression using stack
Q1: a+b*c+(d*e+f)*g
Q2: ((A - (B+C)) * D) $ (E + F)

Ans Q1: abc * + de * f + g * +

Ans Q2: ABC+ - D*EF+$

Data Structure and Algorithms (DSA) 12/14/25

13 Expression Evaluation
Algorithm for Evaluation of Postfix Expression using Stack
1. Add a right parenthesis “)” at the end of P. [This acts as a sentinel.]
2. Scan P from left to right and repeat Steps 3 and 4 for each element of P until the sentinel “)”
is encountered.
3. If an operand is encountered, put it on STACK.
4. If an operator ⊗ is encountered, then:
i. Remove the two top elements of STACK, where A is the top element and B is the
next-to-top element.
ii. Evaluate B ⊗ A.
[Link] the result on to the STACK.
5. Result equal to the top element on STACK.
6. Exit.

Data Structure and Algorithms (DSA) 12/14/25

14 Expression Evaluation
Evaluation of Postfix Expression using Stack
Let us assume the postfix expression : 6 2 3 + - 3 8 2 / + * 2 $ 3 +
Char Scanned Operand1 Operand2 Value Operator stack
6 6
2 6,2
3 6,2,3
+ 2 3 5 6,5
- 6 5 1 1
3 6 5 1 1,3
8 6 5 1 1,3,8
2 6 5 1 1,3,8,2
/ 8 2 4 1,3,4
+ 3 4 7 1,7
* 7 7 7 7
2 1 7 7 7,2
$ 7 2 49 49
3 7 2 49 49,3
+ 49 3 52 52

Data Structure and Algorithms (DSA) 12/14/25

15 Expression Evaluation
Evaluate the following postfix expression

Q1: 6 5 2 3 + 8 * + 3 + *
Q2: ABC+*DE/- where A=5, B=6, C=2, D=12, E=4

Ans Q1: 288

Ans Q2: 37

Data Structure and Algorithms (DSA) 12/14/25

16 Expression Conversion
Algorithm for Converting Postfix Expression to Infix Expression Using Stack
[Link] there are input symbol left
Read the next symbol from input.
3. If the symbol is an operand
Push it onto the stack.
4. Otherwise, the symbol is an operator.
5. If there are fewer than 2 values on the stack
Show Error /* input not sufficient values in the expression */
6. Else
Pop the top 2 values from the stack.
Put the operator, with the values as arguments and form a string.
Encapsulate the resulted string with parenthesis.
Push the resulted string back to stack.
7. If there is only one value in the stack, that value in the stack is the desired infix string.
8. If there are more values in the stack
Show Error /* The user input has too many values */
Data Structure and Algorithms (DSA) 12/14/25
17 Postfix to Infix Conversion Using Stack
Convert the following Postfix Expression into infix expression using stack
ABC-+DE-FG-H+/*
Char Scanned Operand1 Operand2 Value Operator stack
A A
B A,B
C A,B,C
- B C B-C A,B-C
+ A B-C A+B-C A+B-C
D A B-C A+B-C A+B-C,D
E A B-C A+B-C A+B-C,D,E
- D E D-E A+B-C,D-E
F D E D-E A+B-C,D-E,F
G D E D-E A+B-C,D-E,F,G
- F G F-G A+B-C,D-E,F-G
H F G F-G A+B-C,D-E,F-G,H
+ F-G H F-G+H A+B-C,D-E,F-G+H
/ D-E F-G+H (D-E)/(F-G+H) A+B-C,(D-E)/(F-G+H)
* A+B-C (D-E)/(F-G+H) (A+B-C)*(D-E)/(F-G+H) (A+B-C)*(D-E)/(F-G+H)

Data Structure and Algorithms (DSA) 12/14/25

18 Infix to Prefix Conversion Using Stack
— Suppose Q is an arithmetic expression written in infix notation then the algorithm that finds the
equivalent prefix expression is given below:
1. Reverse infix string, swap '(' with ')' and ')' with '('.
2. Initialize empty stack and empty output list.
3. Scan each character in reversed infix from left to right:
a. If operand → add to output.
b. If '(' → push to stack.
c. If ')' → pop from stack to output until '(' is popped.
d. If operator:
a. while stack not empty AND top has higher or equal precedence (considering associativity)
a. pop to output
b. push current operator to stack
4. Pop remaining operators from stack to output.
5. Reverse output list → gives prefix expression.
19 Infix to Prefix Conversion Using Stack
Convert the following infix expression into prefix expression : (A+B*C)
Step 1: Reverse the above infix expression: ) C * B + A (
Step 2: Replacing ( by ) and ) by (, we get ( C * B + A )
Step 3:
Character Scanned Stack Output String
( ( -
C ( C
* (* C
B (* CB
+ (+ CB*
A (+ CB*A
) Empty CB*A+

Step 4: Output after Step 3: C B * A + (Postfix String)

Reverse this: + A * B C (Infix is reverse of postfix string)
So, the required prefix expression is: + A * B C
20 Infix to Prefix Conversion Using Stack
Convert the following infix expression into prefix expression.
P=A+(B/C-(D*E$F)+G)*H
Step 1: Reverse the string -> H*)G+)F$E*D(-C/B(+A
Step 2: '(' ↔ ')': H*(G+(F$E*D)-C/B)+A ) Character Scanned Stack Postfix String
Step 3: Make table as given (
H ( H
Step 4: Reverse the final output string * (* H
( (*( H
G (*( HG
HGFE$D*-CB/-*A+ becomes + (*(+ HG
( (*(+( HG
+A*-/BC+*D$EFGH F (*(+( HGF
$ (*(+($ HGF
E (*(+($ HGFE
* (*(+(* HGFE$
D (*(+(* HGFE$D
) (*(+ HGFE$D*
- (*(- HGFE$D*+
C (*(- HGFE$D*+C
/ (*(-/ HGFE$D*+C
B (*(-/ HGFE$D*+CB
) (* HGFE$D*+CB/-*
+ (+ HGFE$D*+CB/-*
A (+ HGFE$D*+CB/-*A
) Empty HGFE$D*+CB/-*A+
Data Structure and Algorithms (DSA) 12/14/25
21 Expression Evaluation
Algorithm for Evaluation of Prefix Expression using Stack
1. Create an empty stack S.
2. Scan the prefix expression E from RIGHT to LEFT:
For each symbol X in E:
a. If X is an operand:
i. Push X onto stack S.
b. Else if X is an operator (e.g., +, -, *, /, $, ^):
i. Pop operand A from stack S.
ii. Pop operand B from stack S.
iii. Compute R = A operator B.
iv. Push R back onto S.
3. After scanning all characters:
a. The value in the top of stack S is the final result.
4. Return top(S).

Data Structure and Algorithms (DSA) 12/14/25

22 Expression Evaluation
Evaluation of Prefix Expression
Example: a) /+5,3-4,2 b) +5*3,2
(a) Char Operand1 Operand2 Value Operator
Scanned stack
2 2
4 2,4
- 4 2 2 2
3 4 2 2 2,3
5 4 2 2 2,3,5
+ 3 5 8 2,8
/ 8 2 4 4

(b) Do yourself (Ans: 11)

Data Structure and Algorithms (DSA) 12/14/25

 23 Applications of Stack
— Function Call Management: The call stack manages function execution by pushing contexts when
called and popping them when completed.
— Undo Mechanisms: Each action is stored on a stack, and undoing an action pops and reverses it.
— Syntax Parsing: Compilers use stacks to parse expressions and check syntax in nested structures.
— Backtracking: Stacks track paths in search algorithms, allowing the program to backtrack when
needed.
— Checking mathematical expression validity, expression evaluation and conversion: Stacks help validate
expressions and convert between notations.
— Reversing a string: Characters are pushed onto a stack and popped to reverse order.
— Maintaining an undo list for an application: Actions are stored on a stack to enable undo functionality.
— Keeping page visited history in a web browser: A stack tracks visited pages for back/forward
navigation.
— Sorting: Stacks can assist in sorting algorithms by holding temporary data.
— Tower of Hanoi: Though it's a puzzle/algorithm for moving disks between pegs, it's often solved using
stacks to represent each peg.
— Graph Algorithms :Depth-First Search (DFS) uses a stack to track vertices to visit.
— Garbage Collection : Some garbage collectors use stacks to traverse object references.
— etc

Data Structure and Algorithm Design (MCE/CS) NCIT 12/14/25

24

End of Chapter 2

Data Structure and Algorithms (DSA) 12/14/25