Problem Solving Techniques

Unit 3 – Complete Study Notes

Stacks, Queues, and Recursion
BCA Semester 2 | Institute of Technology & Science, Ghaziabad
PART 1: STACKS

1.1 What is a Stack?

A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle.

Real-Life Analogy ■

Think of a stack of plates in a canteen. You always add a plate on TOP and also remove from the
TOP. The last plate placed is the first one taken out — that's LIFO!

Key Properties:
• LIFO – Last element inserted is the first to be removed
• Only the TOP element is accessible at any time
• Stack has a TOP pointer that tracks the topmost element

1.2 Stack Operations

There are 5 main operations on a Stack:

<b>Operation</b> <b>Description</b> <b>Condition Check</b>

PUSH Insert an element onto the stack Check if Stack is FULL → Overflow

POP Remove top element from stack Check if Stack is EMPTY → Underflow

PEEK / TOP View top element without removing Check if Stack is EMPTY

isEmpty() Check if stack has no elements Returns True/False

isFull() Check if stack has reached max size Returns True/False

1.3 Stack using Array – Algorithm

PUSH Operation
• Step 1: Check if TOP == MAX-1 (Stack Full → Overflow Error)
• Step 2: If not full, increment TOP by 1 (TOP = TOP + 1)
• Step 3: Insert element at STACK[TOP]

POP Operation
• Step 1: Check if TOP == -1 (Stack Empty → Underflow Error)
• Step 2: If not empty, store STACK[TOP] in a variable
• Step 3: Decrement TOP by 1 (TOP = TOP - 1)
• Step 4: Return the stored element

1.4 Stack using Linked List

In a Linked List implementation, each node has DATA and a NEXT pointer. The HEAD of the linked list acts as
the TOP of the stack.
 • PUSH = Insert a new node at the beginning (HEAD)
• POP = Remove the node at the beginning (HEAD)
• No fixed size — stack can grow dynamically
• No Overflow condition (only memory limit)

1.5 Applications of Stack

A) Arithmetic Expressions & Polish Notation

Computers process mathematical expressions using stacks. There are 3 notation types:

<b>Notation</b> <b>Operator Position</b> <b>Example (A+B)*C</b>

Infix Between operands (normal writing) (A+B)*C

Prefix (Polish) Before operands *+ABC

Postfix (Reverse Polish) After operands AB+C*

B) Infix to Postfix Conversion

This is a very common exam question! Use a stack to hold operators.
• Step 1: Scan expression from LEFT to RIGHT
• Step 2: If operand (A, B, 1, 2...) → directly add to output
• Step 3: If '(' → push onto stack
• Step 4: If ')' → pop and output until '(' is found
• Step 5: If operator (+,-,*,/) → pop operators with higher/equal precedence, then push current
• Step 6: At end, pop all remaining operators from stack

Operator Precedence (High → Low)

^ (power) > * / > + - | Higher precedence operators go FIRST in postfix

Example: Convert A+B*C to Postfix

Scan: A → output: A
Scan: + → push to stack: [+]
Scan: B → output: AB
Scan: * → * has higher precedence than +, push: [+, *]
Scan: C → output: ABC
End → pop all: ABC*+
Result: ABC*+

C) Evaluation of Postfix Expression

• Step 1: Scan postfix expression left to right
• Step 2: If operand → PUSH onto stack
• Step 3: If operator → POP two elements, apply operator, PUSH result back
• Step 4: At end, single element remaining in stack = ANSWER

Example: Evaluate 23+4*

Scan: 2 → push [2]
Scan: 3 → push [2,3]
Scan: + → pop 3,2 → 2+3=5 → push [5]
Scan: 4 → push [5,4]
Scan: * → pop 4,5 → 5*4=20 → push [20]
Result: 20
PART 2: RECURSION

2.1 What is Recursion?

Recursion is a technique where a function calls ITSELF repeatedly until a base condition is met.

Real-Life Analogy ■

Imagine two mirrors facing each other — you see the same image repeating inside itself. That's how
recursion works — a function repeating itself inside itself!

• Every recursive function MUST have a Base Case (stopping condition)

• Without a base case, recursion will go on forever → Stack Overflow
• Each recursive call is stored on the Runtime Stack (Call Stack)
• When base case is reached, the stack unwinds (returns values back)

2.2 Recursive Notation

A recursive function has two parts:
• Base Case: The condition where recursion STOPS
• Recursive Case: The function calling itself with a smaller/simpler input

General Structure

function F(n):
if n == base_condition: ← BASE CASE
return result
else:
return F(smaller_n) ← RECURSIVE CALL

2.3 Runtime Stack in Recursion

When a recursive function is called, each function call is pushed onto the Runtime Stack (also called Call
Stack). When the base case is reached, the stack starts POPPING and returning values.

Think of it like this ■

Factorial(3) calls Factorial(2), which calls Factorial(1).

All these calls wait in the stack. When Factorial(1) returns 1, the stack unwinds: 1×2=2, then 2×3=6.

2.4 Applications of Recursion

A) Factorial of a Number
Formula: n! = n × (n-1) × (n-2) × ... × 1 | Base Case: 0! = 1
 Algorithm – Factorial(n)

if n == 0:
return 1 ← Base Case
else:
return n * Factorial(n-1) ← Recursive Case

Example: Factorial(4)
= 4 × Factorial(3)
= 4 × 3 × Factorial(2)
= 4 × 3 × 2 × Factorial(1)
= 4 × 3 × 2 × 1 × Factorial(0)
= 4 × 3 × 2 × 1 × 1 = 24

B) GCD (Greatest Common Divisor)

GCD is the largest number that divides both A and B completely.

Algorithm – GCD(a, b)

if b == 0:
return a ← Base Case
else:
return GCD(b, a mod b) ← Recursive Case

Example: GCD(48, 18)

= GCD(18, 48 mod 18) = GCD(18, 12)
= GCD(12, 18 mod 12) = GCD(12, 6)
= GCD(6, 12 mod 6) = GCD(6, 0)
=6

C) Fibonacci Series
Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21 ... (each number = sum of previous two)

Algorithm – Fibonacci(n)

if n == 0: return 0 ← Base Case 1

if n == 1: return 1 ← Base Case 2
return Fibonacci(n-1) + Fibonacci(n-2) ← Recursive Case

Example: Fibonacci(5)
= Fib(4) + Fib(3)
= (Fib(3)+Fib(2)) + (Fib(2)+Fib(1))
= ... = 5

D) Tower of Hanoi
Classic recursion problem: Move N disks from Source peg to Destination peg using a Helper peg. Rules: Only
one disk moved at a time, larger disk cannot go on smaller disk.

Algorithm – Hanoi(n, source, destination, helper)

if n == 1:
Move disk 1 from Source to Destination ← Base Case
else:
Hanoi(n-1, source, helper, destination) ← Move n-1 disks to helper
Move disk n from source to destination
Hanoi(n-1, helper, destination, source) ← Move n-1 disks from helper to dest

For n=3 disks: Total moves = 2^3 - 1 = 7 moves

Formula

Minimum moves for Tower of Hanoi with N disks = 2N - 1

PART 3: QUEUES

3.1 What is a Queue?

A Queue is a linear data structure that follows FIFO (First In, First Out) principle.

Real-Life Analogy ■

Think of a line at a ticket counter. The person who came FIRST gets served FIRST. New people join
from the BACK (REAR) and leave from the FRONT. That's a Queue!

• FIFO – First element inserted is the first to be removed

• Insertions happen at REAR end
• Deletions happen at FRONT end
• Two pointers: FRONT (points to first element) and REAR (points to last element)

3.2 Queue Operations

<b>Operation</b> <b>Description</b> <b>Error Condition</b>

ENQUEUE Insert element at REAR REAR == MAX-1 → Overflow

DEQUEUE Remove element from FRONT FRONT == -1 → Underflow

PEEK / FRONT View front element Queue is EMPTY

isEmpty() Check if queue is empty FRONT == -1 or FRONT > REAR

isFull() Check if queue is full REAR == MAX-1

3.3 Types of Queues

1. Simple (Linear) Queue

• Basic FIFO structure
• Problem: Once FRONT moves forward, that space cannot be reused → Wastage!
• Max size is fixed

2. Circular Queue
A Circular Queue connects the REAR back to the FRONT, forming a circle. This solves the wastage problem of
simple queues.
• When REAR reaches the end, it wraps around to position 0
• Condition: REAR = (REAR + 1) % MAX
• Queue Full: (REAR + 1) % MAX == FRONT
• Queue Empty: FRONT == REAR

Real-Life Analogy ■
 Like a Ferris wheel — after the last seat, it goes back to the first seat. The circular path avoids
wasting empty positions.

3. Double-Ended Queue (Deque)

In a Deque, insertion and deletion can happen at BOTH ends (front and rear).

<b>Input-Restricted Deque</b> <b>Output-Restricted Deque</b>

Insertion only at one end, Deletion from both ends Insertion from both ends, Deletion only at one end

4. Priority Queue
In a Priority Queue, each element has a PRIORITY. The element with the HIGHEST priority is served first (not
necessarily the one inserted first).
• Used in CPU scheduling, Dijkstra's algorithm
• Two types: Ascending Priority Queue and Descending Priority Queue

3.4 Queue Using Array – Algorithm

ENQUEUE (Insert)
• Step 1: Check if REAR == MAX-1 → Overflow
• Step 2: If Queue is empty, set FRONT = REAR = 0
• Step 3: Otherwise, REAR = REAR + 1
• Step 4: QUEUE[REAR] = element

DEQUEUE (Delete)
• Step 1: Check if FRONT == -1 or FRONT > REAR → Underflow
• Step 2: Store QUEUE[FRONT] in a temp variable
• Step 3: FRONT = FRONT + 1
• Step 4: Return temp variable

3.5 Queue Using Linked List

• FRONT pointer = Head of linked list
• REAR pointer = Last node in the linked list
• ENQUEUE: Add node at REAR (end of list)
• DEQUEUE: Remove node from FRONT (head of list)
• Advantage: No fixed size, no overflow (until memory runs out)

3.6 Applications of Queues

• CPU Scheduling – OS uses queues to manage processes
• Printer Spooling – Print jobs stored in queue, processed one by one
• BFS (Breadth First Search) – Graph traversal uses a queue
• Call Center Systems – Customers wait in queue to be served
• Keyboard Buffer – Keystrokes stored in queue, processed in order
• Traffic Signal Management – Cars waiting at signals
PART 4: Stack vs Queue – Quick Comparison
<b>Feature</b> <b>Stack</b> <b>Queue</b>

Principle LIFO – Last In, First Out FIFO – First In, First Out

Access Point Only one end (TOP) Two ends (FRONT & REAR)

Insertion PUSH at TOP ENQUEUE at REAR

Deletion POP from TOP DEQUEUE from FRONT

Analogy Stack of plates Queue at ticket counter

Applications Undo, recursion, expressions CPU scheduling, BFS, printing

PART 5: Important Exam Questions & Answers

Short Answer Questions (2-5 Marks)

Q: What is a Stack? State its LIFO principle.

A: A Stack is a linear data structure where elements are inserted and removed from the SAME end called the
TOP. LIFO means Last In, First Out — the element inserted LAST is removed FIRST. Example: Stack of plates
where the top plate is removed first.

Q: What are the two error conditions in a Stack?

A: 1. OVERFLOW: Occurs when we try to PUSH an element into a FULL stack (TOP == MAX-1). 2.
UNDERFLOW: Occurs when we try to POP from an EMPTY stack (TOP == -1).

Q: What is the difference between PUSH and POP?

A: PUSH: Inserts a new element onto the TOP of the stack. Before pushing, we check for overflow. POP:
Removes the element from the TOP of the stack. Before popping, we check for underflow.

Q: What is a Queue? How is it different from a Stack?

A: A Queue is a linear data structure following FIFO. Elements are inserted at REAR and removed from FRONT.
Difference: Stack uses LIFO with one access point (TOP), while Queue uses FIFO with two access points
(FRONT and REAR).

Q: What is a Circular Queue? Why is it better than Simple Queue?

A: A Circular Queue connects the last position back to the first, forming a circle. It is better because in a Simple
Queue, once FRONT moves forward, those memory positions are wasted. In a Circular Queue, these empty
positions are reused by connecting the end to the beginning.

Q: What is recursion? What is a base case?

A: Recursion is a programming technique where a function calls itself to solve a smaller version of the same
problem. A base case is the condition that STOPS the recursion. Without a base case, the function calls itself
infinitely, causing Stack Overflow.

Q: State the minimum number of moves for Tower of Hanoi with N disks.

A: The minimum number of moves required to solve Tower of Hanoi with N disks is 2^N - 1. For 3 disks: 2^3 - 1 =
7 moves For 4 disks: 2^4 - 1 = 15 moves

Long Answer Questions (10 Marks)

Q: Explain Infix to Postfix conversion with example. Convert A*(B+C)/D to Postfix.
A: Algorithm: 1. Scan expression left to right 2. If operand → add to output 3. If '(' → push to stack 4. If ')' → pop
until '(' found 5. If operator → pop higher/equal precedence operators, then push current 6. At end → pop
remaining stack Conversion of A*(B+C)/D: Scan A → Output: A Scan * → Stack: [*] Output: A Scan ( → Stack: [*,
(] Output: A Scan B → Output: AB Scan + → Stack: [*, (, +] Output: AB Scan C → Output: ABC Scan ) → pop till (
→ Output: ABC+ Stack: [*] Scan / → * and / equal precedence, pop *, push / → Stack: [/] Output: ABC+* Scan D
→ Output: ABC+*D End → pop all → Output: ABC+*D/ Final Postfix: ABC+*D/

Q: Explain Evaluation of Postfix Expression with example: 5 3 2 * + 9 -

A: Algorithm: 1. Scan left to right 2. If operand → PUSH onto stack 3. If operator → POP two elements, apply
operator, PUSH result 4. Final answer = remaining element in stack Evaluation of 5 3 2 * + 9 -: Scan 5 → Stack:
[5] Scan 3 → Stack: [5, 3] Scan 2 → Stack: [5, 3, 2] Scan * → pop 2,3 → 3*2=6 → Stack: [5, 6] Scan + → pop 6,5
→ 5+6=11 → Stack: [11] Scan 9 → Stack: [11, 9] Scan - → pop 9,11 → 11-9=2 → Stack: [2] Result: 2
PART 6: Quick Revision – Key Points

STACKS – Remember These!

• LIFO = Last In, First Out

• TOP pointer tracks top element
• PUSH = insert, POP = remove
• Overflow = push to full stack (TOP == MAX-1)
• Underflow = pop from empty stack (TOP == -1)
• Applications: Expressions, Recursion, Undo, Backtracking

RECURSION – Remember These!

• Function calls itself

• MUST have a Base Case (stopping condition)
• Each call goes on Runtime/Call Stack
• Factorial base: n==0, return 1
• Fibonacci base: n==0 return 0, n==1 return 1
• Tower of Hanoi: 2^N - 1 moves for N disks
• GCD uses Euclid's algorithm: GCD(a,b) = GCD(b, a mod b)

QUEUES – Remember These!

• FIFO = First In, First Out

• FRONT = where elements leave, REAR = where elements enter
• Enqueue = insert at REAR, Dequeue = remove from FRONT
• Circular Queue solves memory wastage of Simple Queue
• Deque = Double Ended Queue (both ends for insert/delete)
• Priority Queue = higher priority element served first
• Applications: CPU scheduling, BFS, Printing, Buffering

NOTATION – Infix, Prefix, Postfix

• Infix: A+B (operator BETWEEN operands) — what we write normally

• Prefix: +AB (operator BEFORE operands) — Polish notation
• Postfix: AB+ (operator AFTER operands) — Reverse Polish, used by computers
• Precedence: ^ > * / > + -
• Computer prefers POSTFIX because no brackets needed and easier to evaluate

All the best for your exam! ■

PST Unit 3 – Stacks, Queues & Recursion