Stack and Queue

Unit 4
 Content

Stack and queue as ADT

Operations on stack and queue

Implementations using arrays

Dynamic memory allocation

Expression evaluation
Application of stack for:
Expression conversion

Recursion and stacks

 Stack
Stack PUSH(x) Pop (x)

A stack is a linear data

structure that follows the Last
In, First Out (LIFO) principle. 40 Top
30
20
This means the last element 10
inserted (pushed) is the first
one to be removed (popped).
LIFO
A stack of plates in a
cafeteria.
📦 Real-life Undo/Redo operations in

Analogies: an editor.
Browser history
(Back/Forward buttons).
Basic Operations on Stack
Operation Description
Add (insert) element x to the top of the
push(x)
stack.
Remove and return the top element from the
pop()
stack.
peek() / top() View the top element without removing it.
isEmpty() Returns true if the stack has no elements.
Returns true if no more elements can be
isFull() (for fixed size)
pushed.
Array-Based Stack (Static)
Size=4
int stack[SIZE];
int top = -1; 10 20 30 40
top
push(x):
if (top == SIZE - 1)
→ overflow Top =Size-1

else Overflow condition

stack[++top] = x;

pop(): Top=-1
if (top == -1)
→ underflow
else return stack[top--];
Linked List-Based Stack (Dynamic)
struct Node {
10 \0
int data;
top
struct Node* next;
};

20 10 \0
push(x):
create new node; top

new->next = top;
top = new;
30 20 10 \0
top
pop():
if (top == NULL) → underflow
else:
temp = top;
top = top->next;
🔹 Stack State Example
• Initially stack is empty [top] → NULL Top =-
1

• After push(10), push(20), push(30): 30

Top++
20
Top++
10
Top =-
1
• After pop():
20 Top
30
Top-- 10
20
10
 Applications of Stack

Application Description

Expression
Convert and evaluate infix, prefix, postfix expressions.
Evaluation

Syntax Parsing Used in compilers to check balanced parentheses, etc.

Recursion Function call stack in programming uses a stack.

Backtracking Used in maze-solving, game-playing, etc.

Undo/Redo Applications like MS Word maintain stack history.

Web Browsers For navigating backward/forward in history.

 Queue
• A Queue is a linear data structure that follows the First
In, First Out (FIFO) principle.
• FIFO means: The element added first is removed first.
• Think of a queue like a line of people waiting at a
ticket counter.

Front Rear

Dequeue
Enqueue
Queue
 Waiting in a line at a

Real- railway ticket counter.

life Print queue (documents

printed in the order

Examp submitted).

le Call center calls lined up

in a customer service
system.
Basic Queue Operations

Operation Description
enqueue(x
Insert (add) element x at the rear.
)
dequeue() Remove element from the front.
View the front element without
peek()
removing it.
isEmpty() Check if queue has no elements.
Check if queue is full (for fixed-size
Array-Based Implementation
int queue[MAX];
int front = 0, rear = -1; Overflow Condition
0 1 2 3
enqueue(x): Front 10 20 30 40 Rear
if (rear == MAX-1) Max-1
→ overflow
else
queue[++rear] = x;

dequeue():
if (front > rear) Front=0

→ underflow Rear =-1

else
return queue[front++];
Linked List-Based Queue
struct Node {
int data;
struct Node* next;
};

struct Queue {
Node* front;
Node* rear;
};
ENQUEUEING (Insertion)
ENQUEUE(Q, value):
newNode ← allocate new Node
[Link] ← value
[Link] ← NULL

If [Link] = NULL then

[Link] ← newNode
[Link] ← newNode
Else
[Link] ← newNode
[Link] ← newNode
DEQUEUING (Deletion)
DEQUEUE(Q):
If [Link] = NULL then
Output "Queue Underflow"
Return -1
temp ← [Link]
value ← [Link]
[Link] ← [Link]
If [Link] = NULL then
[Link] ← NULL
Deallocate temp
Return value
Application of Stack • The stack is a fundamental data structure
used in evaluating mathematical expressions,
in Expression especially in compilers, interpreters, and
Evaluation calculators.

Expression Type Example Description

Operators between
Infix A+B*C
operands

Operators before
Prefix (Polish) +A*BC
operands

Postfix (Reverse
ABC*+ Operators after operands
Polish)
Why Stack?

Stack helps manage operator precedence and

associativity.

It stores operands and intermediate results during

evaluation.

It supports LIFO behaviour which matches the needs

of nested or hierarchical expressions.
Infix notation
• The operator symbol placed between its two operand
A+B
C-D
E*F
G/H
• Expressions
Q= (A+B)*C
Q=A+(B*C)
Polish notation (Prefix)
• The operator symbol is placed before its two operand:
+AB
-CD
*EF
/GH
• Expressions:
• Q= (A+B)*C
= [+AB]*C
= *+AB
Properties of Polish notation

Property Explanation

Operator order dictates grouping and

No parentheses needed
precedence

Suitable for machine

Ideal for stack and tree-based processing
evaluation

Every valid expression has exactly one

Unambiguous interpretation
meaning

Easy to parse recursively Useful in compilers and interpreters

Reverse polish Notation (Postfix)
Reverse Polish Notation, the operator follows
its operands.
There is no need for parentheses, regardless of
the expression's complexity.

Fundamental Property:
In RPN, expressions are evaluated unambiguously
without parentheses, based on strict left-to-right order
using a stack.
Examples
• Infix: (A + B) * C
Postfix (RPN): A B + C *
• Evaluation:
[Link] A
[Link] B
3.+ → Pop A and B, compute A + B, push result
[Link] C
5.* → Pop (A + B) and C, compute result
Applications:
Area Use Case
Compilers Intermediate expression representation
Calculators RPN calculators (like old HP models)
Evaluation by popping operands and
Stack Machines
pushing result
Used in interpreters and syntax
Postfix Parsers
analyzers
Advantages of Reverse Polish Notation:

No need for parentheses

Faster and simpler evaluation using

stacks
Unambiguous interpretation of
expressions
Easily implementable in low-level
systems
Precedence Rule in Expression
Evaluation
• The precedence rule defines the order in which
operators are evaluated in an expression when
multiple operators are present.
Precedence
Operators Description Associativity
Level
1 (Highest) () exponent() Parentheses (Right to Left)
Multiplication/
2 *, /, % Left to Right
Division/Mod
Addition/
3 +, - Left to Right
Subtraction
4 (Lowest) = Assignment Right to Left
Examples precedence
A + B * C
• According to precedence:
• * has higher precedence than +
• So, B * C is evaluated first
• Then A + (B * C)

• Associativity:
• When two operators of the same precedence appear,
associativity decides the order:
• Left to Right (L→R): +, -, *, /
• Right to Left (R→L): =, +=, -=, etc.
Example
Q= 2 2-12/6
Q= 8+5*4-12/6
Q= 8+20-2
Q= 26
Example question
Convert by inspection and hand the given infix
expression to Postfix :
1. (A-B)*(D/E)
2. (A+B D)/(E-F)+G
3. A*(B+D)/E-F*(G+H/K)
Answer-Expression 1:
• Infix:
• (A - B) * (D / E)
• Postfix:
•AB-DE/*
• Explanation:
• A B - → Result of (A - B)
• D E / → Result of (D / E)
• Multiply both: A B - D E / *
Answer-Expression 2:
• Infix:
• (A + B ↑ D) / (E - F) + G
• Postfix:
• ABD↑+EF-/G+
• Explanation:
• B D ↑ → Exponentiation
• A + (result) → A B D ↑ +
• E-F→EF-
• Division: (A + B ↑ D) / (E - F) → A B D ↑ + E F - /
• Then add G: A B D ↑ + E F - / G +
Answer-Expression 3:
• Infix:
• A * (B + D) / E - F * (G + H / K)
• Postfix:
• ABD+*E/FGHK/+*-
• Explanation:
• B+D→BD+
• Multiply with A: A B D + *
• Divide by E: A B D + * E /
• H/K→HK/
• G + (result) → G H K / +
• Multiply with F: F G H K / + *
• Subtract both parts: A B D + * E / F G H K / + * -
Question
Consider the following arithmetic expression P, written in
postfix notation :
P= 12,7,3,-,/,2,1,5,+,*,+
a) Translate P by inspection and hand , into its equivalent
infix expression
b) Evaluate the infix expression
Answer-
Postfix to infix: Infix evaluation :
P= (7 - 3) = 4
12,7,3,-,/,2,1,5,+,*,+ 12 / 4 = 3
P= 12, [7- (1 + 5) = 6
3],/,2,1,5,+,*,+
2 * 6 = 12
P= [12/(7-
3)],2,1,5,+,*,+ 3 + 12 = 15
P= [12/(7-3)],2,
[1+5],*,+
P= [12/(7-3)],
[2*(1+5)],+
Question
Consider the following arithmetic expression P, written in
postfix notation :
P= 12,7,3,-,/,2,1,5,+,*,+
a) Translate P by inspection and Stack , into its
equivalent infix expression
b) Evaluate the infix expression
 Answer
Token Action Stack (Top at Right)
12 Push 12
7 Push 12, 7
3 Push 12, 7, 3
- Apply 12, (7 - 3)
/ Apply (12 / (7 - 3))
2 Push (12 / (7 - 3)), 2
1 Push (12 / (7 - 3)), 2, 1
5 Push (12 / (7 - 3)), 2, 1, 5
+ Apply (12 / (7 - 3)), 2, (1 + 5)
* Apply (12 / (7 - 3)), (2 * (1 + 5))
+ Apply ((12 / (7 - 3)) + (2 * (1 + 5)))
summary

Concept Use

Precedenc Decides which operator goes

e first

Associativi Resolves tie when operators

ty have same precedence
Infix to Postfix Conversion

Use Use stack to store operators and apply precedence rules.

Output Output operands directly.

Pop operators from stack based on precedence and append

Pop to result.

Infix Infix: A + B * C

Postfix Postfix: A B C * +
 Steps for Conversion (Algorithm)
Initialize an empty stack for operators and an empty list for the output.

Scan the infix expression from left to right.

Operands
Add directly to the output.
(A–Z, 0–9)
Left
Parenthesis Push to stack.
(
Right
Parenthesis Pop and add to output until ( is found. Discard (.
)
Operator While stack is not empty and top has higher or equal precedence, pop
(+, -, *, /, ^) from stack to output. Push the current operator to stack.

At the end Pop remaining operators from the stack to output.

 Step-by-Step Conversion (with Stack
A + B *Operations):
(C - D)
Step Symbol Action Stack Postfix Output
1 A Operand → Add to output A
2 + Operator → Push to stack + A
3 B Operand → Add to output + AB
Operator → Higher precedence than +
4 * +* AB
→ Push
5 ( Left parenthesis → Push +*( AB
6 C Operand → Add to output +*( ABC
7 - Operator → Push inside brackets +*(- ABC
8 D Operand → Add to output +*(- ABCD
Right parenthesis → Pop till ‘(’ and
9 ) +* ABCD-
discard '('
10 End Pop all remaining operators ABCD-*+
A + (B * C - (D / E ↑ F) * G) * H
Symbo
Step Stack Output Explanation
l
1 A A Operand → output
2 + + A Operator → push
3 ( + ( A Left paren → push
4 B + ( A B Operand → output
5 * + ( * A B Operator → push
6 C + ( * A B C Operand → output
7 - + ( - A B C * * popped → higher precedence than -
8 ( + ( -( A B C * Left paren → push
9 D + ( -( A B C * D Operand → output
10 / + ( -(/ A B C * D Operator → push
11 E + ( -(/ A B C * D E Operand → output
12 ↑ + ( -(/↑ A B C * D E Exponent has higher precedence → push
13 F + ( -(/↑ A B C * D E F Operand → output
14 ) + ( - A B C * D E F ↑ / Pop till (
15 * + ( -* A B C * D E F ↑ / Operator → push
16 G + ( -* A B C * D E F ↑ / G Operand → output
17 ) + A B C * D E F ↑ / G*- Pop till (
18 * + * A B C * D E F ↑ / G*- Higher precedence → push
19 H + * A B C * D E F ↑ / G*-H Operand → output
((A+B)*D)↑(E–F)
Ste
Symbol Action Stack Output
p
1 ( Push to stack ( []
2 ( Push to stack (( []
3 A Operand → add to output (( A

4 + Operator → push (stack top is () ((+ A

5 B Operand → add to output ((+ AB

6 ) Pop and add to output until ( is found ( AB+

7 * Operator → push (* AB+

8 D Operand → add to output (* AB+D

9 ) Pop and add to output until ( is found [] AB+D*

10 ↑ Operator → push ↑ AB+D*

11 ( Push to stack ↑( AB+D*
12 E Operand → add to output ↑( AB+D*E
13 – Operator → push ↑(– AB+D*E
14 F Operand → add to output ↑(– AB+D*EF

15 ) Pop and add to output until ( is found ↑ AB+D*EF–

16 End Pop remaining stack operators [] AB+D*EF–↑

A * (B + D) / E - F * (G + H / K)
Symbo
Action Stack Output
l
A Operand → add to output A
* Operator → push * A
( Left paren → push * ( A
B Operand → add to output * ( A B
+ Operator → push * (+ A B
D Operand → add to output * (+ A BD
) Pop until ( * A BD+
/ Operator → push (higher than *) */ ABD+
E Operand → add to output */ ABD+E
- Lower than /, so pop / and *, then push - - ABD+E/*
F Operand → add to output - A B D + E / * F
* Operator → push - * A B D + E / * F
( Push - * ( A B D + E / * F
G Operand → add to output - * ( A B D + E / * FG
+ Operator → push - * (+ A B D + E / * FG
H Operand → add to output - * (+ A B D + E / * FGH
/ Higher precedence than + → push -*(+/ ABD+E/*FGH
K Operand → add to output -*(+/ ABD+E/*FGHK
) Pop until ( - ABD+E/*FGHK/+*-
Recursion and Stack
Recursion is a method where a function calls itself
directly or indirectly to solve a problem.

It breaks the problem down into smaller subproblems until

a base case is reached.

Have base criteria or base values for which the function

doesn't call itself
A well-defined This prevents infinite recursion and provides a
recursive "stopping point."
Move closer to the base case with each recursive call.
function must: this ensures the function reaches the base case and
recursion ends.
Example: Factorial Function
• The factorial of a non-negative integer n, written as
n!, is defined as:
• Base case:
• If n = 0, then 0! = 1
• Recursive case:
• If n > 0, then n! = n * (n - 1)!
• This means n! is defined in terms of n-1, which is closer
to 0 — the base case.
Why Use a Stack for Recursion?
The current function's state (its parameters, local
variables, and the return address) must be saved.
This is done using a call stack.

Each recursive call pushes a new frame onto the

stack.
When a base case is reached, the function returns,
and the stack pops one frame at a time, unwinding
the recursion.
Algorithm
Step1: Start
Step2: Read the value of n
If n == 0
Return 1 // Base case: 0! = 1
Else
Return n * factorial(n - 1) // Recursive
case
Step3: End
Example: Recursive Factorial
int factorial(int n){
int fact = 1;
if (n == 0){
return 1;
}
else{
fact = fact * factorial(n - 1);
return fact;
}
}
Example: Recursive Factorial
void main(){
int n = 4;
int fact = factorial(4);
printf("\n factorial is = %d", fact);
}
Call Factorial (4)
Call Level Function Call Action
Return 4 *
1 factorial(4)
factorial(3)
Return 3 *
2 factorial(3)
factorial(2)
Return 2 *
3 factorial(2)
factorial(1)
Return 1 *
4 factorial(1)
factorial(0)
Return 1 (base
5 factorial(0)
case)