CSL 102-

Data Structures
Module 3

Computer Science and Engineering

Indian Institute of Information Technology, Nagpur.

1
09-04-2026
 What is Stack?

• Stack is a linear data structure that follows a particular order in which the
operations are performed.

• The order may be LIFO(Last In First Out) or FILO(First In Last Out).

• LIFO implies that the element that is inserted last, comes out first
and FILO implies that the element that is inserted first, comes out last.

Pop Pop
Push
 Stack
• There are many real-life examples of a stack. Consider an example of plates stacked
over one another in the canteen.

• The plate which is at the top is the first one to be removed, i.e. the plate which has
been placed at the bottommost position remains in the stack for the longest period
of time.

• It contains only one pointer top pointer pointing to the topmost element of the
stack.

• Whenever an element is added in the stack, it is added on the top of the stack, and
the element can be deleted only from the stack.

• In other words, a stack can be defined as a container in which insertion and deletion
can be done from the one end known as the top of the stack.
Stack
 Stack
• An abstract data type (ADT) is an abstraction of a data structure

• An ADT specifies:
• Data stored
• Operations on the data
• Error conditions associated with operations
Objects:
A finite sequence of nodes
Operations:
1. Push: Insert element at top.
2. Top: Return top element.
3. Pop: Remove and return top element.
4. IsEmpty: test for emptiness.
5. IsFull: test for overflow.
 PUSH operation

Before inserting an element in a stack, we check whether the stack is full.

If we try to insert the element in a stack, and the stack is full, then the overflow
condition occurs.

When we initialize a stack, we set the value of top as -1 to check that the stack is
empty.

When the new element is pushed in a stack, first, the value of the top gets
incremented, i.e., top=top+1, and the element will be placed at the new position of the
top.

The elements will be inserted until we reach the max size of the stack.
PUSH operation Using arrays

#include <stdio.h>
#define MAX_SIZE 10
int stack[MAX_SIZE];
int top = -1;

void push(int element)

int isFull()
{
{
if (isFull())
if(top == MAX_SIZE - 1)
{
return 1;
printf("Error: Stack overflow\n");
else
return;
return 0;
}
}
stack[++top] = element;
}
 POP operation

The steps involved in the POP operation is given below:

Before deleting the element from the stack, we check whether the stack is empty.

If we try to delete the element from the empty stack, then the underflow condition
occurs.

If the stack is not empty, we first access the element which is pointed by the top
Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.
 POP operation
int isEmpty() int pop()
{ {
if(top == -1) if (isEmpty())
return 1; {
else printf("Error: Stack underflow\n");
return 0; exit(1);
} }
return stack[top--];
}
int peek() int main()
{ {
if (isEmpty()) push(10);
{ push(20);
printf("Error: Stack is empty\n"); push(30);
exit(1); printf("Top element of stack: %d\n", peek());
} printf("Popped element: %d\n", pop());
return stack[top]; printf("Top element of stack: %d\n", peek());
} return 0;
}
 Linked list implementation of stack

• Instead of using array, we can also use linked list to implement stack. Linked list
allocates the memory dynamically.

• However, time complexity in both the scenario is same for all the operations i.e.
push, pop and peek.

• In linked list implementation of stack, the nodes are maintained non-contiguously in

the memory.

• Each node contains a pointer to its immediate successor node in the stack.

• Stack is said to be overflown if the space left in the memory heap is not enough to
create a node.
Linked list implementation of stack
 Adding a node to the stack (Push
operation)
Adding a node to the stack is referred to as push operation. Pushing an element to a stack in
linked list implementation is different from that of an array implementation.

In order to push an element onto the stack, the following steps are involved.

1. Create a node first and allocate memory to it.

2. If the list is empty then the item is to be pushed as the start node of the list. This
includes assigning value to the data part of the node and assign null to the address part
of the node.

3. If there are some nodes in the list already, then we have to add the new element in the
beginning of the list (to not violate the property of the stack). For this purpose, assign the
address of the starting element to the address field of the new node and make the new
node, the starting node of the list.

Time Complexity : o(1)

Adding a node to the stack (Push
operation)
 Adding a node to the stack (Push
operation)
#include<stdio.h> struct node *createNodewithValue(int n)
#include<stdlib.h> {
struct node struct node *tmp;
{ tmp=(struct node *)malloc(sizeof(struct node));
int data; tmp->next=NULL;
struct node *next; tmp->data=n;
}*top=NULL; return tmp;
}

struct Node* push(struct Node* top, int data) void display(struct node *top)
{ {
struct Node* newNode = createNodewithValue (data); struct node *tmp=top;
newNode->next = top; printf("\n The stack elements are: \n");
top = newNode; while(tmp!=NULL)
printf("%d pushed to stack.\n", data); {
return top; printf("%d \n",tmp->data);
} tmp=tmp->next;
}
}
 Removing a node from the stack (Pop
operation)

void pop ()
int main()
{
{
if(top==NULL)
push(10);
{
push(20);
printf("Stack is empty");
push(30);
return;
display(top);
}
pop();
int popped_item;
display(top);
struct node *tmp=NULL;
// pop();
tmp=top;
// pop();
popped_item=top->data;
return 0;
top=top->next;
}
free(tmp);
}
 Why adding and deleting at front

• Implementing a stack by adding nodes at the front of the linked list (also known as a
"head-first" approach)

• Adding a node at the front of a linked list (push operation) takes constant time,
O(1), regardless of the size of the stack.

• This is because we simply update the next pointer of the new node to point to the
current head of the list, and then update the head pointer to point to the new node.

• On the other hand, adding a node at the end of a linked list (tail-first approach)
requires traversing the entire list to find the last node, resulting in a time complexity
of O(n), where n is the number of nodes in the list. If we keep top pointing to last
node then it may take O(1).
Why adding and deleting at front
 Problem 1

Write a program to print all prime factors of a

number in descending order using a stack
 Problem 2: Decimal to Binary

Write a program to convert a number from

decimal to binary.
Problem 2: Decimal to Binary
Problem 2: Decimal to Binary
Problem 2: Decimal to Binary
 Applications of Stacks

• Direct applications:
• Page-visited history in a Web browser
• Undo sequence in a text editor
• Chain of method calls in the Java Virtual Machine
• Validate XML/HTML

• Indirect applications:
• Auxiliary data structure for algorithms
• Component of other data structures

44
 Evaluation of Arithmetic Expressions
• Stack is a very effective data structure for evaluating arithmetic expressions
in programming languages.

• An arithmetic expression consists of operands and operators.

• In addition to operands and operators, the arithmetic expression may also

include parenthesis like "left parenthesis" and "right parenthesis

• To evaluate the expressions, one needs to be aware of the standard

precedence rules for arithmetic expression.

Lecture #00: © DSamanta CS 11001 : Programming and Data Structures 45

 Evaluation of Arithmetic Expressions
• Evaluation of Arithmetic Expression

• Convert the given expression into special notation.

• Evaluate the expression in this new notation.

• Notations for Arithmetic Expression

• Three notations to represent an arithmetic expression:

1. Infix Notation
2. Prefix Notation
3. Postfix Notation
46
 Infix Notation

• The infix notation is a convenient way of writing an expression in which each

operator is placed between the operands.

• Infix expressions can be parenthesized or not

• Example:
1. A + B
2. (C - D)

• All these expressions are in infix notation because the operator comes between
the operands.

47
 Prefix Notation

• The prefix notation places the operator before the operands.

• Introduced by the Polish mathematician and hence often referred to as polish

notation.

• Example:
1. +AB
2. -CD

• All these expressions are in prefix notation because the operator comes before the
operands.

48
 Postfix notation

• The postfix notation places the operator after the operands.

• This notation is just the reverse of Polish notation and also known as Reverse Polish
notation.

• Example:
1. AB+
2. CD+

• All these expressions are in postfix notation because the operator comes after the
operands.

49
 Why postfix representation of the
expression?
• The Compiler scans the expression either from left to right or from right to left.

• Consider the below expression: a op1 b op2 c op3 d

• If op1 = +, op2 = *, op3 = +

• The compiler first scans the expression to evaluate the expression b * c, then again
scans the expression to add a to it. The result is then added to d after another scan.

• The repeated scanning makes it very in-efficient. It is better to convert the

expression to postfix(or prefix) form before evaluation.

• The corresponding expression in postfix form is abc*+d+.

• The postfix expressions can be evaluated easily using a stack.

50
Operator Precedence

51
Operator precendence

52
 Infix to Postfix Conversion Algorithm

Infix Expression:
A + B / C* D – E / (F + G)

Postfix Expression:
A + B / C* D – E / FG+
A + BC/ * D – E / FG+
A + BC/ D* – E / FG+
A + BC/ D* – E FG+/
A BC/ D* + – E FG+/
A BC/ D* + E FG+/-

53
 Infix to Postfix Conversion Algorithm
using Stack
1. Scan the expression from left to right
2. If symbol is operands then print it.
3. If the stack is empty or contains a left parenthesis on top, push the incoming operator onto
the stack.
4. If the incoming symbol is a left parenthesis, push it on the stack.
5. If the incoming symbol is a right parenthesis, pop the stack and print the operators until
you see a left parenthesis. Discard the pair of parentheses.
6. If the incoming symbol has higher precedence than the top of the stack, push it on the
stack.
7. If the incoming symbol has equal precedence with the top of the stack, use association. If
the association is left to right, pop and print the top of the stack and then push the
incoming operator. (If the association is right to left, push the incoming operator.)
8. If the incoming symbol has lower precedence than the symbol on the top of the stack, pop
the stack and print the top operator. Then test the incoming operator against the new top of
stack.
9. At the end of the expression, pop and print all operators on the stack. (No parentheses
should remain.)
54
 Infix to Postfix Conversion Algorithm

Requires operator precedence information

Operands:
Add to postfix expression.
Close parenthesis:
pop stack symbols until an open parenthesis appears.
Operators:
Pop all stack symbols until a symbol of lower precedence appears. Then push the operator.
End of input:
Pop all remaining stack symbols and add to the expression.

55
 Infix to Postfix Conversion Algorithm

Current Operator Postfix string

Expression: symbol Stack
1 A A
A * (B + C * D) + E 2 * * A
3 ( *( A
becomes
4 B *( AB
ABCD*+*E+ 5 + *(+ AB
6 C *(+ ABC
7 * *(+* ABC
8 D *(+* ABCD
Postfix notation
is also called as 9 ) * ABCD*+
Reverse Polish 10 + + ABCD*+*
Notation (RPN) 11 E + ABCD*+*E
12 ABCD*+*E+
56
 Infix to Postfix Conversion Algorithm
case '+':
// Infix to Postfix case '-':
void inToPost() { case '*':
int i, j = 0; case '/':
char symbol, next; case '^':
while (!isEmpty() && precedence(stack[top]) >= precedence(symbol))
for (i = 0; i < strlen(infix); i++) { postfix[j++] = pop();
symbol = infix[i]; push(symbol);
break;
switch (symbol) { default: // operand
case '(': postfix[j++] = symbol;
push(symbol); }
break; }
// Pop remaining operators
case ')': while (!isEmpty())
while ((next = pop()) != '(') postfix[j++] = pop();
postfix[j++] = next;
break; postfix[j] = '\0';
} 57
 Infix to Postfix Conversion Algorithm

Current Operator Postfix string

Expression: symbol Stack
1 A A
A * (B + C * D) + E 2 * * A
3 ( *( A
becomes
4 B *( AB
ABCD*+*E+ 5 * *(* AB
6 C *(+ ABC
Expression:
7 + *(+ ABC*

A * (B * C + D) + E 8 D *(+ ABC*D
9 ) * ABC*D +
becomes 10 + + ABC*D +*
11 E + ABC*D +*E
ABC*D+*E+
12 ABC*D +*E+
58
 Infix to Postfix Conversion Algorithm

Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q

ANS KL+MN*-OP^W*U/V/T*+Q+

59
 Infix to Postfix Evaluation Algorithm

Infix Expression:
3 + 5 * (5/5) – 2 ^ 2

Postfix Expression:
3555/*+22^-

Evaluation of Postfix expression:

• Scan expression from left to right

• When operator is there, apply it to last 2 operands

60
 Infix to Postfix Evaluation Algorithm

Evaluation of Postfix expression:

3555 /*+22^-

351*+22^-

3 5 + 2 2^ -

822^-

84–

Q. Evaluate : 8 5 4 ^ 2 + * 6 2 ^ 9 3 * / -

61
 Postfix Evaluation

Algorithm for postfix evaluation

• Iterate through given expression from left to right, one character at a time

• If the character is an operand, push it to the operand stack.

• If the character is an operator,

• pop an operand from the stack, say it’s s1.
• pop an operand from the stack, say it’s s2.

• perform (s2 operator s1) and push it to stack.

• Once the expression iteration is completed, The stack will have the final result.
Pop from the stack and return the result.

62
 EXERCISE

• 38+98/-

63
EXERCISE

64
 EXERCISE

• Convert the following Infix expression to Postfix using Stack

1. (5 * (((9 + 8) * (4 * 6)) + 7))

2. 6 * (5 + (2 + 3) * 8 + 3)
3. a + b * c + (d * e + f) * g

• Evaluate the following Postfix expression using Stack

1. 5 6 2 + * 2 4 1 - * +
2. 4 2 3 5 1 - + * +
3. 2 5 3 6 + * * 5 / 2 -

65
 Infix to Prefix Algorithm
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.

66
 Infix to Prefix Algorithm

Infix Expression: K + L - M * N + (O^P) * W/U/V * T + Q

Reverse Expression: Q + T * V/U/W * ) P^O (+ N*M - L + K
Input Stack Prefix expression
Q Q
+ + Q
T + QT
* +* QT
V +* QTV
/ +*/ QTV
U +*/ QTVU
/ +*// QTVU
W +*// QTVUW
* +*//* QTVUW
) +*//*) QTVUW
P +*//*) QTVUWP

67
 Infix to Prefix Algorithm

Infix Expression: K + L - M * N + (O^P) * W/U/V * T + Q

Reverse Expression: Q + T * V/U/W * ) P^O (+ N*M - L + K

Input Stack Prefix expression

^ +*//*)^ QTVUWP
O +*//*)^ QTVUWPO
( +*//* QTVUWPO^
+ ++ QTVUWPO^*//*
N ++ QTVUWPO^*//*N
* ++* QTVUWPO^*//*N
M ++* QTVUWPO^*//*NM
- ++- QTVUWPO^*//*NM*
L ++- QTVUWPO^*//*NM*L
+ ++-+ QTVUWPO^*//*NM*L
K ++-+ QTVUWPO^*//*NM*LK
QTVUWPO^*//*NM*LK+-++

68
 Infix to Prefix Algorithm

Infix Expression: K + L - M * N + (O^P) * W/U/V * T + Q

Reverse Expression: Q + T * V/U/W * ) P^O (+ N*M - L + K

Note: QTVUWPO^*//*NM*LK+-++, is not a final expression.

We need to reverse this expression to obtain the prefix
expression.

Final Prefix Notation : ++-+KL*MN*//*^OPWUVTQ

69
 Reversing a Word

• Read each letter in the word and push it onto the stack.

• When you reach the end of the word, pop the letters off the stack and print them
out.
Stack Application Recursion
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
Program to Demonstrate Recursion
Cont…
 How to write Recursive Program
Idea
Step 1
Step 1
Step 1
Step 1
Step 1
Step 1
Step 1
Step 1
Step 1
Step 2
Step 2
Step 2
Cont…
Program to understand Indirect recursion
Cont…
Program to understand Indirect recursion
Cont…
Cont…
Cont…
Cont…
Cont…
Tail or Non-tail?
Cont…
Which solution to choose?
Cont…
Advantage
Cont…
Cont…
Disadvantage
Question
Cont…
Question
Cont…
Question
Question
Cont…
Print Fibonacci Numbers

int fun(int n) int main()

{ {
if (n == 0) int n, i ;
return 0; scanf("%d",&n);
else if (n == 1) for (i = 0 ; i < n ; i++)
return 1; {
else printf("%d\n", fun(i));
return (fun(n-1) + fun(n-2)); }
} return 0;
}
 Recursion Iteration
Basic Process of calling a function Repeated execution of the set of
itself within its own code. instructions. Loops are used to
execute the set of instructions
repetitively until the condition is
false.
Syntax Termination condition is Includes initialization, condition, and
specified. increment/decrement of a variable.

Termination Termination condition is Termination condition is defined in

defined within the recursive the definition of the loop.
function.
Code size Code size is smaller than Code size is larger than the code
the code size in iteration. size in recursion.
 Recursion Iteration

Infinite If recursion does not meet Iteration will be infinite, if the

to a termination condition, control condition of the iteration
it leads to an infinite statement never becomes false. On
recursion. Chance of infinite loop, it repeatedly used CPU
system crash in infinite cycles.
recursion.
Applied It is always applied to It is applied to loops.
functions.
Speed It is slower than iteration. It is faster than recursion.
Usage Generally used where there It is used when we have to balance
is no issue of time the time complexity against a large
complexity, and code size code size.
requires being small.
 Recursion Iteration

Stack It has to update and There is no utilization of stack.

maintain the stack.
Memory It uses more memory as It uses less memory as compared to
compared to iteration. recursion.
Overhead There is an extensive There is no overhead in iteration.
overhead due to updating
and maintaining the stack.