28 September 2025 09:31
• Fibonacci numbers using recursion
• a^n (a raised to the power n, using divide and conquer).
• reverse of a string using recursion
• Implementation and operations on Queue using linked list.
• Priority queue (heap).
• Find the Kth Smallest/Largest Element in an Array: Write a function to find the Kth
smallest or largest element in an array.
• Reverse a Linked List: Write a function to reverse a singly linked list.
• Implement a Queue Using Stacks: Write a function to implement a queue using two
stacks. (vice-versa)
Reverse a string using Recursion
public class ReverseStringRecursion {
// Recursive method to reverse a string
public static String reverse(String str) {
// Base case: if string is empty or has one character
if (str == null || [Link]() <= 1) {
return str;
Week 5 Lec 13 14 15 Page 1
public static String reverse(String str) {
// Base case: if string is empty or has one character
if (str == null || [Link]() <= 1) {
return str;
}
// Recursive case: reverse substring and append first character at the end
return reverse([Link](1)) + [Link](0);
}
public static void main(String[] args) {
String input = "Recursion";
String reversed = reverse(input);
[Link]("Original String: " + input);
[Link]("Reversed String: " + reversed);
}
}
To compute a^n using divide and conquer, we can use the Exponentiation by Squaring
technique. This method reduces the time complexity from O(n) to O(log n).
Core Idea:
- If n is even:
a^n = (a^{n/2})^2
- If n is odd:
a^n = a(a^{n/2})^2
Java Implementation:
public class PowerDivideAndConquer {
// Recursive method to compute a^n
public static long power(long a, int n) {
if (n == 0) return 1; // base case
long halfPower = power(a, n / 2);
if (n % 2 == 0) {
return halfPower * halfPower;
} else {
return a * halfPower * halfPower;
}
}
public static void main(String[] args) {
long a = 2;
int n = 10;
[Link](a + "^" + n + " = " + power(a, n));
}
}
Time Complexity:
- O(log n) due to halving the exponent at each recursive step.
Week 5 Lec 13 14 15 Page 2
A Queue is a linear data structure that follows the FIFO (First In, First Out) principle. This
means the element inserted first is the one removed first—like a line of people waiting for a
service.
Characteristics of a Queue:
- Enqueue: Add an element to the rear.
- Dequeue: Remove an element from the front.
- Peek/Front: View the front element without removing it.
- IsEmpty: Check if the queue is empty.
class Node {
int data;
Node next;
public Node(int data) {
[Link] = data;
[Link] = null;
}
}
class Queue {
private Node front, rear;
public Queue() {
[Link] = [Link] = null;
}
// Enqueue operation
public void enqueue(int data) {
Node newNode = new Node(data);
if (rear == null) {
front = rear = newNode;
return;
}
[Link] = newNode;
rear = newNode;
}
// Dequeue operation
public int dequeue() {
if (front == null) {
throw new RuntimeException("Queue is empty");
}
int value = [Link];
front = [Link];
if (front == null)
rear = null;
return value;
}
// Peek operation
public int peek() {
if (front == null) {
throw new RuntimeException("Queue is empty");
Week 5 Lec 13 14 15 Page 3
throw new RuntimeException("Queue is empty");
}
return [Link];
}
// Check if queue is empty
public boolean isEmpty() {
return front == null;
}
}
public class QueueUsingLinkedList {
public static void main(String[] args) {
Queue q = new Queue();
[Link](10);
[Link](20);
[Link](30);
[Link]("Front element: " + [Link]());
[Link]("Dequeued: " + [Link]());
[Link]("Front after dequeue: " + [Link]());
}
}
A Priority Queue is an advanced type of queue where each element is associated with a
priority, and elements are dequeued based on their priority rather than their insertion order.
The highest priority element is served before others, regardless of when it was added.
How It Works:
Internally, a priority queue is typically implemented using a heap data structure:
• Min-Heap: The smallest element (highest priority) is at the root.
• Max-Heap: The largest element (highest priority) is at the root.
Java’s built-in class uses a min-heap by default.
Min Heap
import [Link];
public class PriorityQueueExample {
public static void main(String[] args) {
// Min-heap by default
PriorityQueue<Integer> pq = new PriorityQueue<>();
[Link](30);
[Link](10);
[Link](20);
[Link]("Priority Queue elements (min-heap):");
while (![Link]()) {
[Link]([Link]()); // retrieves and removes the head
}
}
}
Week 5 Lec 13 14 15 Page 4
}
Use Cases:
- Job scheduling
- Dijkstra’s shortest path algorithm
- Huffman coding
- Event-driven simulations
Max Heap
import [Link];
import [Link];
public class MaxHeapExample {
public static void main(String[] args) {
// Max Heap using reverse order comparator
PriorityQueue<Integer> maxHeap = new PriorityQueue<>([Link]());
// Insert elements
[Link](40);
[Link](10);
[Link](30);
[Link](20);
// Display and remove elements in descending order
[Link]("Max Heap elements:");
while (![Link]()) {
[Link]([Link]()); // removes and returns the largest element
}
}
}
• Find the Kth Smallest/Largest Element in an unsorted Array: Write a function to find the Kth
smallest or largest element in an array.
import [Link];
import [Link];
public class KthElementFinder {
// Kth Smallest using Min-Heap
public static int findKthSmallest(int[] arr, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : arr) {
[Link](num);
}
for (int i = 1; i < k; i++) {
[Link](); // remove smallest k-1 times
Week 5 Lec 13 14 15 Page 5
[Link](); // remove smallest k-1 times
}
return [Link](); // kth smallest
}
// Kth Largest using Max-Heap
public static int findKthLargest(int[] arr, int k) {
PriorityQueue<Integer> maxHeap = new PriorityQueue<>([Link]());
for (int num : arr) {
[Link](num);
}
for (int i = 1; i < k; i++) {
[Link](); // remove largest k-1 times
}
return [Link](); // kth largest
}
public static void main(String[] args) {
int[] array = {7, 10, 4, 3, 20, 15};
int k = 3;
[Link]("Kth Smallest: " + findKthSmallest(array, k));
[Link]("Kth Largest: " + findKthLargest(array, k));
}
}
Reverse a Linked List
class Node {
int data;
Node next;
Node(int data) {
[Link] = data;
[Link] = null;
}
}
class LinkedList {
Node head;
// Reverse the linked list iteratively
public void reverseIterative() {
Node prev = null;
Node current = head;
Node next;
while (current != null) {
next = [Link]; // store next node
[Link] = prev; // reverse pointer
prev = current; // move prev forward
current = next; // move current forward
}
head = prev; // update head to new front
Week 5 Lec 13 14 15 Page 6
prev = current; // move prev forward
current = next; // move current forward
}
head = prev; // update head to new front
}
// Print the list
public void printList() {
Node temp = head;
while (temp != null) {
[Link]([Link] + " ");
temp = [Link];
}
[Link]();
}
}
Implementation of Queue
// Node class for linked list
class Node {
int data;
Node next;
public Node(int data) {
[Link] = data;
[Link] = null;
}
}
// Queue class using linked list
class Queue {
private Node front, rear;
public Queue() {
[Link] = [Link] = null;
}
// Enqueue: Add element to rear
public void enqueue(int data) {
Node newNode = new Node(data);
if (rear == null) {
front = rear = newNode;
return;
}
[Link] = newNode;
rear = newNode;
}
// Dequeue: Remove element from front
public int dequeue() {
if (front == null) {
throw new RuntimeException("Queue is empty");
}
int value = [Link];
Week 5 Lec 13 14 15 Page 7
int value = [Link];
front = [Link];
if (front == null) rear = null;
return value;
}
// Peek: View front element
public int peek() {
if (front == null) {
throw new RuntimeException("Queue is empty");
}
return [Link];
}
// Check if queue is empty
public boolean isEmpty() {
return front == null;
}
// Print queue elements
public void printQueue() {
Node temp = front;
while (temp != null) {
[Link]([Link] + " ");
temp = [Link];
}
[Link]();
}
}
// Main class to test the queue
public class QueueImplementation {
public static void main(String[] args) {
Queue q = new Queue();
[Link](10);
[Link](20);
[Link](30);
[Link]("Queue contents:");
[Link]();
[Link]("Dequeued: " + [Link]());
[Link]("Front element: " + [Link]());
[Link]("Is queue empty? " + [Link]());
}
}
Queue using two stacks
import [Link];
// Class to implement a Queue using two Stacks
public class QueueUsingStacks {
// Stack to handle enqueue operations
private Stack<Integer> stack_in = new Stack<>();
Week 5 Lec 13 14 15 Page 8
// Class to implement a Queue using two Stacks
public class QueueUsingStacks {
// Stack to handle enqueue operations
private Stack<Integer> stack_in = new Stack<>();
// Stack to handle dequeue operations
private Stack<Integer> stack_out = new Stack<>();
// Enqueue operation: push element into stack_in
public void enqueue(int x) {
stack_in.push(x);
[Link]("Enqueued: " + x);
}
// Dequeue operation: pop element from stack_out
public int dequeue() {
// If stack_out is empty, transfer all elements from stack_in
if (stack_out.isEmpty()) {
while (!stack_in.isEmpty()) {
stack_out.push(stack_in.pop());
}
}
// If stack_out is still empty, queue is empty
if (stack_out.isEmpty()) {
throw new RuntimeException("Queue is empty");
}
int removed = stack_out.pop();
[Link]("Dequeued: " + removed);
return removed;
}
// Peek operation: view front element without removing
public int peek() {
if (stack_out.isEmpty()) {
while (!stack_in.isEmpty()) {
stack_out.push(stack_in.pop());
}
}
if (stack_out.isEmpty()) {
throw new RuntimeException("Queue is empty");
}
return stack_out.peek();
}
// Check if queue is empty
public boolean isEmpty() {
return stack_in.isEmpty() && stack_out.isEmpty();
}
// Main method to test the queue
public static void main(String[] args) {
QueueUsingStacks queue = new QueueUsingStacks();
[Link](10);
Week 5 Lec 13 14 15 Page 9
[Link](10);
[Link](20);
[Link](30);
[Link]("Front element: " + [Link]()); // Should print 10
[Link](); // Removes 10
[Link](); // Removes 20
[Link](40);
[Link]("Front element: " + [Link]()); // Should print 30
[Link](); // Removes 30
[Link](); // Removes 40
[Link]("Is queue empty? " + [Link]()); // Should print true
}
}
Stack using Queues
import [Link];
import [Link];
// Class to implement a Stack using two Queues
public class StackUsingQueues {
// Two queues to simulate stack behavior
private Queue<Integer> queue1 = new LinkedList<>();
private Queue<Integer> queue2 = new LinkedList<>();
// Push operation: add element to queue1
public void push(int x) {
[Link]("Pushed: " + x);
[Link](x); // Step 1: Add new element to queue2
// Step 2: Move all elements from queue1 to queue2
while (![Link]()) {
[Link]([Link]());
}
// Step 3: Swap queue1 and queue2
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
// Pop operation: remove and return top element
public int pop() {
if ([Link]()) {
throw new RuntimeException("Stack is empty");
}
int removed = [Link]();
[Link]("Popped: " + removed);
return removed;
}
// Peek operation: view top element without removing
public int peek() {
Week 5 Lec 13 14 15 Page 10
public int peek() {
if ([Link]()) {
throw new RuntimeException("Stack is empty");
}
return [Link]();
}
// Check if stack is empty
public boolean isEmpty() {
return [Link]();
}
// Main method to test the stack
public static void main(String[] args) {
StackUsingQueues stack = new StackUsingQueues();
[Link](10);
[Link](20);
[Link](30);
[Link]("Top element: " + [Link]()); // Should print 30
[Link](); // Removes 30
[Link](); // Removes 20
[Link](40);
[Link]("Top element: " + [Link]()); // Should print 40
[Link](); // Removes 40
[Link](); // Removes 10
[Link]("Is stack empty? " + [Link]()); // Should print true
}
}
Week 5 Lec 13 14 15 Page 11