Acropolis Institute of Technology

& Research, Indore

[Link]
Introduction to Stack
• Stacks is the data structures that follows the Last In First Out (LIFO)
principle. The last item to be inserted into a stack is the first one to be
deleted from it.
• For example, we have a stack of books on a table. The book at the top
of the stack is the first item to be moved if we require a book from that
stack.
Pop Pop
Push

4 November 2025 nehasehta@[Link] 2

Operations on Stack
• Elements can be inserted or deleted only from one end of the stack i.e. from
the top .
• The element at the top is called the top element.
• The operations of inserting and deleting elements are called push and pop
respectively.

4 November 2025 nehasehta@[Link] 3

Operations on Stack
• push() − Pushing (storing) an element on the stack.
• pop() − Removing (accessing) an element from the stack.
• peek() − Get the top data element of the stack, without removing it.
• isFull() − Check if stack is full.
• isEmpty() − Check if stack is empty.

4 November 2025 nehasehta@[Link] 4

Algorithms
isFull(stack) isEmpty(stack)

if top of stack = MAXSIZE-1 if top of stack < 0

return true return true
else else
return false return false
endif endif

4 November 2025 nehasehta@[Link] 5

Algorithms
Push(stack , item)

if isFull(stack)
“Stack Full, can’t push”
else
increment top of stack
Data[top of stack] ← item

4 November 2025 nehasehta@[Link] 6

Algorithms
Item Pop(stack S)
if isEmpty(stack)
stack empty, can’t pop
else
item ← Data[top of stack]
decrement top of stack
return item

4 November 2025 nehasehta@[Link] 7

Algorithms
Peek(stack )
if isEmpty(stack)
stack empty
else
item = Data[top]
return item

4 November 2025 nehasehta@[Link] 8

Applications of Stack
• The simplest application of a stack is to reverse a word. We push a given
word to stack - letter by letter - and then pop letters from the stack.

• "undo" mechanism in text editors is also an application of stack. This

operation is accomplished by keeping all text changes in a stack.

• Another great use of stack is during the function call and return process.

• Evaluating arithmetic expressions

• Recursion Removal

4 November 2025 nehasehta@[Link] 9

Stack using arrays
#define MAX 100

struct stack
{
int Data[MAX]; // define Array to store stack elements
int top;
};

void initialize(struct stack st) // function to initialize stack

{
[Link] = -1;
}
int isEmpty(struct stack st) //function to check if the stack is empty or not
{
return ([Link] == -1);
}
int isFull(struct stack st) //function to check if the stack is full or not
{
return ([Link] == MAX – 1)
}
4 November 2025 nehasehta@[Link] 10
Stack using arrays
void push(struct stack st, int item) //function to add an element x in the stack
{
if (isFull(st)) Stack overflow
{ The condition resulting
printf("OverFlow \n"); from trying to push
exit(EXIT_FAILURE); an element onto a
} full stack.
[Link] [++[Link]] = item; // add an element and increments the top index
}

int pop(struct stack st) // function to pop top element from the stack
{
if (isEmpty(st)) Stack underflow
{ The condition resulting
printf("UnderFlow\n"); from trying to pop
exit(EXIT_FAILURE); an empty stack.
}
return [Link] [[Link]--];
}

4 November 2025 nehasehta@[Link] 11

Stack using arrays
int peek(struct stack st) // function to return top element in a stack
{
if (!isEmpty(st)) // check for empty stack
return [Link] [[Link]];
else
exit(EXIT_FAILURE);
}

4 November 2025 nehasehta@[Link] 12

Multiple Stack
Use a single array having more than one stack i.e. the array is divided for multiple
stacks.

For example, an array STACK divided into two stack STACK A and STACK B
• STACK A expands from the left to right, i.e. from 0th element.
• STACK B expands from the right to left, i.e, from 9th element.
• The combined size of both STACK A and STACK B never exceed 10.

4 November 2025 nehasehta@[Link] 13

Quiz
Q. 1 Consider the following operation performed on a stack of size 5.
Push(1);
Pop();
Push(2);
Push(3);
Pop();
Push(4);
Pop();
Pop();
Push(5);

After the completion of all operation, the number of element present on stack are

a) 1
b) 2
c) 3
d) 4

4 November 2025 nehasehta@[Link] 14

Quiz
Q.2
#define MAX 10
struct STACK
{
int arr [MAX];
int top = -1;
}

If the array index starts with 0, the value of top which cause stack overflow
is?

a) 7
b) 8
c) 9
d) 10

4 November 2025 nehasehta@[Link] 15

Applications of Stack
• String Reversal
• Postfix Expression Evaluation
• Infix to Postfix Conversion
• Recursion

4 November 2025 nehasehta@[Link] 16

1. String Reverse

4 November 2025 nehasehta@[Link] 17

Expression
• In any programming language, if we want to perform any calculation or to
frame a condition
❖ We use a set of symbols to perform the task
❖ These set of symbols makes an expression.
• Expression is defined as a valid set of operands and operators
• Operators: Symbol which performs a particular task like arithmetic operation or
logical operation or conditional operation etc.
• Operands: Values on which the operators can perform the task. Here operand
can be a direct value or variable or address of memory location.

4 November 2025 nehasehta@[Link] 18

Types of Expression
Based on the operator’s position, expressions are divided into THREE types

1. Infix Expression

2. Postfix Expression

3. Prefix Expression

4 November 2025 nehasehta@[Link] 19

Infix Expression
• In infix expression, operator is used in between the operands.
• The general structure of an Infix expression is as follows...

For example: Operand1 Operator Operand2

(a + b)
4 November 2025 nehasehta@[Link] 20
Postfix Expression
• In postfix expression, operator is used after operands.

• We can say that "Operator follows the Operands". It is also

called as Reverse Polish Notation.

• The general structure of Postfix expression is as follows...

For example: Operand1 Operand2 Operator

a b +
4 November 2025 nehasehta@[Link] 21
Prefix Expression
• In prefix expression, operator is used before operands.

• We can say that "Operator precedes the Operands". It is also

called as Polish Notation.

• The general structure of Prefix expression is as follows...

For example: Operator Operand1 Operand2

+a b
4 November 2025 nehasehta@[Link] 22
Converting from Infix to Postfix by Hand
• The first thing you need to do is fully parenthesize the expression.
Example: • BODMAS stands for:
A+B-C Brackets
Becomes Orders
Division/Multiplication
(A+B)-C Addition/Subtraction

• Move each of the operators immediately to the right of their respective right
parentheses.

AB+ C-

Equivalent postfix: A B + C -
4 November 2025 nehasehta@[Link] 23
Converting from Infix to Postfix by Hand
• The first thing you need to do is fully parenthesize the expression.
Example:
(3 + 6) * (2 - 4) + 7
Becomes
(((3 + 6) * (2 - 4)) + 7)

• Move each of the operators immediately to the right of their respective right
parentheses.

36+ 24- ((3 6 + * 2 4 -)) + 7)

36+24-*
36+24-*7+
Equivalent postfix: 3 6 + 2 4 - * 7 +
4 November 2025 nehasehta@[Link] 24
Exercise
(A+B)*(C–D) A–B/(C*D^E)
(( A + B ) * ( C – D )) A – ( B / ( C * ( D ^ E )))
(A B + * C D - ) A – ( B / ( C * D E ^ ))
AB+CD-* A–(B/CDE^*)
A–BCDE^*/
ABCDE^*/-

4 November 2025 nehasehta@[Link] 25

Postfix Evaluation
• Going from left to right, if you see an operator, apply it to the previous
two operands (numbers)
• Example:
10 2 8 * + 3 -

10 16 + 3 -

26 3 -
23

4 November 2025 nehasehta@[Link] 26

Postfix Evaluation
• Going from left to right, if you see an operator, apply it to the previous
two operands (numbers)
• Example:

2 10 4 * 5 / + 9 3 - -

40 6
8
10

4 November 2025 nehasehta@[Link] 27

Postfix evaluation using Stack
4 3 * 6 7 + 5 - + ‘\0’

4 November 2025 nehasehta@[Link] 28

Postfix evaluation using Stack
4 3 * 6 7 + 5 - + ‘\0’

Operand ‘4’ push it into the stack

STAC
4 November 2025 K nehasehta@[Link] 29
Postfix evaluation using Stack

4 3 * 6 7 + 5 - + ‘\0’

4 Operand ‘3’ push it into the stack.

STAC
4 November 2025 K nehasehta@[Link] 30
Postfix evaluation using Stack
4 3 * 6 7 + 5 - +

3
4 Now comes Operator
STAC ‘*’.
4 November 2025 K nehasehta@[Link] 31
Postfix evaluation using Stack

4 3 * 6 7 + 5 - + ‘\0’

3
4
Pop operand ‘3’ and ‘4’
STAC
K
4 November 2025 nehasehta@[Link] 32
Postfix evaluation using Stack

4 3 * 6 7 + 5 - + ‘\0’

4*3

Evaluate the expression 4*3 =12

STAC Push it into the stack
K
4 November 2025 nehasehta@[Link] 33
Postfix evaluation using Stack

4 3 * 6 7 + 5 - + ‘\0’

12
STAC Operand ‘6’ push it into the stack
K
4 November 2025 nehasehta@[Link] 34
Postfix evaluation using Stack

4 3 * 6 7 + 5 - + ‘\0’

6
12
STAC Operand ‘7’ push it into the stack
K
4 November 2025 nehasehta@[Link] 35
Postfix evaluation using Stack

4 3 * 6 7 + 5 - + ‘\0’

7
6
12
STAC Now comes Operator
K ‘+’.
4 November 2025 nehasehta@[Link] 36
Postfix evaluation using Stack

4 3 * 6 7 + 5 - + ‘\0’

12
STAC
Pop operand ‘6’ and ‘7’
K
4 November 2025 nehasehta@[Link] 37
Postfix evaluation using Stack

4 3 * 6 7 + 5 - + ‘\0’

6+7

12 Evaluate ‘6+7’ =13

STAC Push it into the stack
K
4 November 2025 nehasehta@[Link] 38
Postfix evaluation using Stack

4 3 * 6 7 + 5 - + ‘\0’

13
12
Operand ‘5’ push it into the stack
STAC
K
4 November 2025 nehasehta@[Link] 39
Postfix evaluation using Stack

4 3 * 6 7 + 5 - + ‘\0’

5
13
12 Now comes operator ‘-’
STAC
K
4 November 2025 nehasehta@[Link] 40
Postfix evaluation using Stack

4 3 * 6 7 + 5 - + ‘\0’

13-5

12 Operands ‘5’ and ‘13’ are popped

Evaluating “13-5” We get ‘8’
STAC
K
4 November 2025 nehasehta@[Link] 41
Postfix evaluation using Stack
4 3 * 6 7 + 5 - +

12 Now, push the resultant value i.e

STAC ‘8’ in the stack
K
4 November 2025 nehasehta@[Link] 42
Postfix evaluation using Stack

4 3 * 6 7 + 5 - + ‘\0’

8
12 Now comes operator ‘+’
STAC
K
4 November 2025 nehasehta@[Link] 43
Postfix evaluation using Stack

4 3 * 6 7 + 5 - + ‘\0’

12+8

Operands ‘12’ and ‘8’ are popped

Evaluating “12+8” We get ‘20’
STAC
4 November 2025 K nehasehta@[Link] 44
Postfix evaluation using Stack
4 3 * 6 7 + 5 - +

So push ‘20’ in stack

STAC
4 November 2025 K nehasehta@[Link] 45
Postfix evaluation using Stack
4 3 * 6 7 + 5 - + ‘\0’

Now end of input is found

Now , pop the element which is the answer

20

STAC
K
4 November 2025 nehasehta@[Link] 46
Postfix evaluation using Stack
4 3 * 6 7 + 5 - + ‘\0’

20

STAC
4 November 2025 K nehasehta@[Link] 47
Algorithm
1. Read the element.

2. If element is an operand then:

Push the element into the stack.

3. If element is an operator then :

• Pop two operands from the stack.
• Apply operation on two operands.
• Push the result on the stack.

4. Repeat until end of the input is encountered.

4 November 2025 nehasehta@[Link] 48

Advantage of Postfix Expression
• No ambiguity and no brackets are required.

• It is the same process used by a computer to perform

computations:
✔ operands must be loaded into registers before
operations can be performed on them.

• Reverse-Polish can be processed using stacks.

4 November 2025 nehasehta@[Link] 49

Quiz
Q.1 What is the value of the postfix expression 6 3 2 4 + – *:
a) 1
b) 40
c) 74
d) -18

Q.2 The postfix form of A*B+C/D is?

a) *AB/CD+
b) AB*CD/+
c) A*BC+/D
d) ABCD+/*

4 November 2025 nehasehta@[Link] 50

Infix to Postfix conversion using stack
• In infix expression, operator is used in between the operands.

• We may have given a parenthesized expression to mention the intended

precedence. Eg:-
• (3 + 4) × 5 – 6

• If we don’t have an expression with default parentheses, we apply

BODMAS rule to define the precedence. Eg:-
• 3+4×5–6
• 3 + (4 × 5) – 6
• ((3 + (4 × 5)) – 6

4 November 2025 nehasehta@[Link] 51

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack

output

4 November 2025 nehasehta@[Link] 52

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack (

output

4 November 2025 nehasehta@[Link] 53

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( (

output

4 November 2025 nehasehta@[Link] 54

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( ( (

output

4 November 2025 nehasehta@[Link] 55

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( ( (

output A

4 November 2025 nehasehta@[Link] 56

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( ( ( +

output A

4 November 2025 nehasehta@[Link] 57

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( ( ( +

output AB

4 November 2025 nehasehta@[Link] 58

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( ( ( +

output AB

4 November 2025 nehasehta@[Link] 59

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( ( (

output AB+

4 November 2025 nehasehta@[Link] 60

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( (

output AB+

4 November 2025 nehasehta@[Link] 61

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( ( *

output AB+

4 November 2025 nehasehta@[Link] 62

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( ( * (

output AB+

4 November 2025 nehasehta@[Link] 63

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( ( * (

output AB+C

4 November 2025 nehasehta@[Link] 64

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( ( * ( -

output AB+C

4 November 2025 nehasehta@[Link] 65

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( ( * ( -

output AB+CE

4 November 2025 nehasehta@[Link] 66

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( ( * ( -

output AB+CE

4 November 2025 nehasehta@[Link] 67

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( ( * (

output AB+CE-

4 November 2025 nehasehta@[Link] 68

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( ( *

output AB+CE-

4 November 2025 nehasehta@[Link] 69

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( ( *

output AB+CE-

4 November 2025 nehasehta@[Link] 70

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( (

output AB+CE-*

4 November 2025 nehasehta@[Link] 71

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack (

output AB+CE-*

4 November 2025 nehasehta@[Link] 72

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( /

output AB+CE-*

4 November 2025 nehasehta@[Link] 73

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( / (

output AB+CE-*

4 November 2025 nehasehta@[Link] 74

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( / (

output AB+CE-*F

4 November 2025 nehasehta@[Link] 75

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( / ( +

output AB+CE-*F

4 November 2025 nehasehta@[Link] 76

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( / ( +

output AB+CE-*FG

4 November 2025 nehasehta@[Link] 77

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( / ( +

output AB+CE-*FG

4 November 2025 nehasehta@[Link] 78

Example
Expression=>
(((A+B)*(C-E))/(F+G))
( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( / (

output AB+CE-*FG+

4 November 2025 nehasehta@[Link] 79

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( /

output AB+CE-*FG+

4 November 2025 nehasehta@[Link] 80

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack ( /

output AB+CE-*FG+

4 November 2025 nehasehta@[Link] 81

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack (

output AB+CE-*FG+/

4 November 2025 nehasehta@[Link] 82

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack

output AB+CE-*FG+/

4 November 2025 nehasehta@[Link] 83

Example
Expression=>
(((A+B)*(C-E))/(F+G))

( ( ( A + B ) * ( C - E ) ) / ( F + G ) )

stack

output AB+CE-*FG+/

4 November 2025 nehasehta@[Link] 84

Algorithm to convert Infix To Postfix
Let, X is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix
expression Y.

1. Push “(“onto Stack, and add “)” to the end of X.

2. Scan X from left to right.

3. if an operand is encountered, add it to Y.

4. If a left parenthesis is encountered, push it onto Stack.

5. If an operator is encountered ,then:

1. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) which has
the same precedence as or higher precedence than operator.
2. Add operator to Stack.

4 November 2025 nehasehta@[Link] 85

Algorithm to convert Infix To Postfix
[Link] a right parenthesis is encountered ,then:

1. Repeatedly pop from Stack and add to Y each operator ( on the top of Stack) until
a left parenthesis is encountered.

2. Remove the left Parenthesis.

7. Repeat Step 3 to 6 for each element of X and until the Stack is empty

4 November 2025 nehasehta@[Link] 86

Example
infix expression
a / b * (c + (d - e))

4 November 2025 nehasehta@[Link] 87

Example
infix expression Next Symbol Postfix String Stack
A+B*C/D-E A A
+ A +
B AB +
* AB +*
C ABC +*
/ ABC* +/
D ABC*D +/
- ABC*D/+ -
E ABC*D/+E -
ABC*D/+E-

4 November 2025 nehasehta@[Link] 88

Processing Function Calls

………….. ………….. …………..

4 November 2025 nehasehta@[Link] 89

Processing Function Calls

4 November 2025 nehasehta@[Link] 90

Recursion
• A Recursive thing is something whose definition includes itself.

• In Programming, Recursion is when a function calls itself.

4 November 2025 nehasehta@[Link] 91