Concept of Hashing & Collision Resolution Techniques

1️⃣ What is Hashing?

🔹 Hashing is a technique used to store and retrieve data efficiently using a hash function.
🔹 Instead of searching through an array, hashing directly maps a key to an index in a hash table.
🔹 Time Complexity:

• Best Case: O(1) (Direct access using hash function)
• Worst Case: O(n) (If many collisions occur)

---

2️⃣ Hash Table & Hash Function

• Hash Table: A data structure that stores key-value pairs.
• Hash Function: A function that converts a key into an index in the hash table.

🔹 Properties of a Good Hash Function

✔ Minimizes Collisions (assigns unique indices)
✔ Evenly distributes data across the table
✔ Efficient computation (Fast to calculate)

✅ Example Hash Function (Modulo Method)

index = key % table_size;

If table_size = 10 and key = 25, then:

index = 25 % 10 = 5

The key 25 is stored at index 5 in the hash table.

---

3️⃣ What is Collision in Hashing?

🔹 Collision occurs when two different keys get mapped to the same index.
🔹 Example: If both 25 and 35 are mapped to index 5, a collision happens.

How to Resolve Collisions?

🔹 There are multiple Collision Resolution Techniques, including:
1️⃣ Open Addressing (Linear Probing, Quadratic Probing, Double Hashing)
2️⃣ Chaining (Separate Chaining with Linked Lists)

---

4️⃣ Collision Resolution Techniques

1️⃣ Open Addressing (Storing Elements in the Hash Table Itself)

✔ If a collision occurs, find the next available slot within the table.

🔹 (A) Linear Probing

✅ Finds the next available slot sequentially (next index).
❌ Primary clustering (elements get grouped together).

index = (hash(key) + i) % table_size;

Example: If index = 5 is occupied, try 6, 7, 8, etc.

🔹 (B) Quadratic Probing

✅ Checks in quadratic steps (1², 2², 3², ...).
❌ Secondary clustering may still happen.

index = (hash(key) + i²) % table_size;

Example: If index = 5 is occupied, try 6, 9, 14, etc.

🔹 (C) Double Hashing

✅ Uses a second hash function for resolving collisions.
✅ Avoids clustering completely.

index = (hash1(key) + i * hash2(key)) % table_size;

Example:

hash1(key) = key % 10;
hash2(key) = 7 - (key % 7);  // Ensures different probing sequence

---

2️⃣ Chaining (Separate Chaining with Linked Lists)

✅ Each index in the hash table contains a linked list to store multiple values.
✅ Efficient if the number of collisions is high.
❌ Requires extra memory for linked lists.

✅ C Program: Hashing with Chaining

#include <stdio.h>
#include <stdlib.h>

#define TABLE_SIZE 10

// Structure for linked list node
struct Node {
    int key;
    struct Node* next;
};

// Hash table array of linked lists
struct Node* hashTable[TABLE_SIZE];

// Hash function
int hashFunction(int key) {
    return key % TABLE_SIZE;
}

// Insert function
void insert(int key) {
    int index = hashFunction(key);
    
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->key = key;
    newNode->next = hashTable[index]; // Insert at beginning
    hashTable[index] = newNode;
}

// Search function
int search(int key) {
    int index = hashFunction(key);
    struct Node* temp = hashTable[index];
    
    while (temp) {
        if (temp->key == key)
            return 1; // Key found
        temp = temp->next;
    }
    return 0; // Key not found
}

// Display function
void display() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        printf("Index %d: ", i);
        struct Node* temp = hashTable[i];
        while (temp) {
            printf("%d -> ", temp->key);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

// Main function
int main() {
    insert(10);
    insert(20);
    insert(30);
    insert(25);
    insert(35);
    
    display();
    
    if (search(25))
        printf("Element found\n");
    else
        printf("Element not found\n");

    return 0;
}

✅ Handles collisions well
✅ Efficient for large datasets
❌ Extra memory required for linked lists

---

5️⃣ Comparison: Open Addressing vs. Chaining

Feature	Open Addressing	Chaining (Linked List)
Memory Usage	No extra memory needed	Extra memory for linked lists
Speed	Slower if the table is full	Faster in case of collisions
Load Factor	Performance degrades as load increases	Handles load well
Implementation	Complex but saves space	Simple but uses more memory

 

 Binary Search in Data Structures

1️⃣ What is Binary Search?

🔹 Binary Search is an efficient searching algorithm used for sorted data.
🔹 It follows a divide-and-conquer approach by repeatedly dividing the search space in half.
🔹 Time Complexity:

• Best Case: O(1) (if the middle element is the target).
• Worst Case: O(log n) (reduces search space by half in each step).
  🔹 Best for: Large datasets that are sorted.

---

2️⃣ How Binary Search Works

Steps:

1️⃣ Find the middle element of the array.
2️⃣ If the middle element matches the key, return its position.
3️⃣ If the key is smaller than the middle element, search in the left half.
4️⃣ If the key is greater than the middle element, search in the right half.
5️⃣ Repeat the process until the element is found or the search space is empty.

---

3️⃣ Binary Search Implementation in C

✅ Iterative Approach

#include <stdio.h>

// Function to perform Binary Search
int binarySearch(int arr[], int left, int right, int key) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == key) return mid;  // Element found

        if (arr[mid] < key) left = mid + 1;  // Search right half
        else right = mid - 1;  // Search left half
    }
    return -1;  // Element not found
}

int main() {
    int arr[] = {2, 4, 5, 7, 8, 9, 12};  // Sorted array
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 7;

    int index = binarySearch(arr, 0, n - 1, key);
    if (index != -1)
        printf("Element found at index %d\n", index);
    else
        printf("Element not found\n");

    return 0;
}

✅ Iterative approach avoids extra memory usage from recursion.
❌ More complex than linear search but much faster for large datasets.

---

✅ Recursive Approach

#include <stdio.h>

// Recursive Binary Search Function
int binarySearchRecursive(int arr[], int left, int right, int key) {
    if (left > right) return -1;  // Base case: Not found

    int mid = left + (right - left) / 2;

    if (arr[mid] == key) return mid;  // Element found

    if (arr[mid] < key)  // Search right half
        return binarySearchRecursive(arr, mid + 1, right, key);

    return binarySearchRecursive(arr, left, mid - 1, key);  // Search left half
}

int main() {
    int arr[] = {2, 4, 5, 7, 8, 9, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 8;

    int index = binarySearchRecursive(arr, 0, n - 1, key);
    if (index != -1)
        printf("Element found at index %d\n", index);
    else
        printf("Element not found\n");

    return 0;
}

✅ Recursive approach is easier to understand.
❌ Uses extra function calls (stack memory).

---

4️⃣ Comparison: Iterative vs Recursive Binary Search

Feature	Iterative Binary Search	Recursive Binary Search
Memory Usage	Uses a single loop (O(1) space)	Uses recursion stack (O(log n) space)
Performance	Faster (no recursive calls)	Slightly slower due to function calls
Ease of Understanding	Complex logic but efficient	More intuitive but costly in memory
Use Case	Large datasets, performance-critical apps	When simplicity is preferred

---

5️⃣ Advantages & Disadvantages

✅ Advantages

✔ Much faster than Linear Search (O(log n) vs. O(n))
✔ Works well for large datasets
✔ Efficient memory usage (Iterative approach: O(1) extra space)

❌ Disadvantages

❌ Only works on sorted arrays
❌ Requires additional steps to maintain a sorted dataset
❌ Recursive approach can lead to stack overflow for very large inputs

 

Sequential Search & Index Sequential Search

1️⃣ Sequential Search (Linear Search)

🔹 Simple searching technique that checks elements one by one.
🔹 Works on unsorted or sorted data.
🔹 Time Complexity:

• Best Case: O(1) (Element found at the first position).
• Worst Case: O(n) (Element at the last position or not present).
  🔹 Used when:
• Data is small.
• No sorting is required.
• Searching once or rarely (no need for optimizations).

✅ C Program: Sequential Search

#include <stdio.h>

// Function to perform sequential search
int sequentialSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) return i;  // Element found
    }
    return -1;  // Element not found
}

int main() {
    int arr[] = {12, 5, 7, 9, 1, 15};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 7;

    int index = sequentialSearch(arr, n, key);
    if (index != -1)
        printf("Element found at index %d\n", index);
    else
        printf("Element not found\n");

    return 0;
}

✅ Works on unsorted data
❌ Slow for large datasets

---

2️⃣ Index Sequential Search

🔹 Optimized form of Sequential Search.
🔹 Used when data is large and sorted.
🔹 Divides data into blocks, creating an index table for quick lookups.
🔹 Steps:

1. Create an index table containing references to certain elements in the data.
2. Search in the index table to locate the approximate block.
3. Perform Sequential Search in that block.
   🔹 Time Complexity:

• Best Case: O(1) (if found in index).
• Worst Case: O(√n) (if searched element is at the end).

---

✅ C Program: Index Sequential Search

#include <stdio.h>

#define SIZE 10
#define INDEX_SIZE 3  // Number of index entries

// Structure to store index
struct IndexTable {
    int key;
    int position;
};

// Function to perform index sequential search
int indexSequentialSearch(int arr[], struct IndexTable index[], int key) {
    int i, start, end;
    
    // Step 1: Find the index block
    for (i = 0; i < INDEX_SIZE; i++) {
        if (index[i].key >= key) break;
    }

    // Define the search range
    if (i == 0) start = 0;
    else start = index[i - 1].position;
    
    end = index[i].position;

    // Step 2: Perform sequential search in the found block
    for (int j = start; j < end; j++) {
        if (arr[j] == key) return j;
    }
    
    return -1;  // Element not found
}

int main() {
    int arr[SIZE] = {1, 3, 5, 7, 9, 12, 15, 18, 21, 25};

    // Creating an index table
    struct IndexTable index[INDEX_SIZE] = {
        {5, 2},  // First block starts at index 0
        {12, 5}, // Second block starts at index 2
        {21, 8}  // Third block starts at index 5
    };

    int key = 12;

    int indexPos = indexSequentialSearch(arr, index, key);
    if (indexPos != -1)
        printf("Element found at index %d\n", indexPos);
    else
        printf("Element not found\n");

    return 0;
}

✅ Faster than Sequential Search
✅ Efficient for large datasets
❌ Needs sorted data and index table

---

3️⃣ Comparison: Sequential vs. Index Sequential Search

Feature	Sequential Search	Index Sequential Search
Data Requirement	Works on unsorted & sorted data	Works only on sorted data
Time Complexity (Worst Case)	O(n)	O(√n)
Best for	Small datasets	Large datasets
Memory Usage	No extra memory required	Extra memory for index table
Performance	Slower for large data	Faster due to indexing

Concept of Searching in Data Structures

 

What is Searching?

Searching is the process of finding a specific element in a collection of data. It is one of the fundamental operations in computer science and plays a crucial role in various applications such as databases, operating systems, and information retrieval.

🔹 Types of Searching Techniques

Searching techniques are broadly classified into two categories: 1️⃣ Linear Search (Sequential Search)
2️⃣ Binary Search (Efficient search for sorted data)

---

1️⃣ Linear Search

🔹 Simple but inefficient method.
🔹 Searches for an element sequentially from the beginning to the end.
🔹 Time Complexity: O(n) (Worst-case scenario: search the entire list).
🔹 Best for small or unsorted data.

✅ C Program: Linear Search

#include <stdio.h>

// Function to perform linear search
int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) return i;  // Element found at index i
    }
    return -1;  // Element not found
}

int main() {
    int arr[] = {5, 3, 8, 4, 2, 9, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 4;

    int index = linearSearch(arr, n, key);
    if (index != -1)
        printf("Element found at index %d\n", index);
    else
        printf("Element not found\n");

    return 0;
}

✅ Simple to implement
❌ Slow for large datasets

---

2️⃣ Binary Search (For Sorted Data)

🔹 Faster and more efficient than linear search.
🔹 Works only on sorted data by dividing the search space in half.
🔹 Time Complexity: O(log n) (Each step reduces the problem size by half).
🔹 Best for large datasets with sorted data.

✅ C Program: Binary Search

#include <stdio.h>

// Function to perform binary search
int binarySearch(int arr[], int left, int right, int key) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == key) return mid;  // Element found

        if (arr[mid] < key) left = mid + 1;  // Search right half
        else right = mid - 1;  // Search left half
    }
    return -1;  // Element not found
}

int main() {
    int arr[] = {2, 4, 5, 7, 8, 9, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 7;

    int index = binarySearch(arr, 0, n - 1, key);
    if (index != -1)
        printf("Element found at index %d\n", index);
    else
        printf("Element not found\n");

    return 0;
}

✅ Much faster than linear search
❌ Requires sorted data

---

3️⃣ Comparison: Linear vs Binary Search

Feature	Linear Search	Binary Search
Data Requirement	Works on unsorted data	Requires sorted data
Time Complexity	O(n)	O(log n)
Performance on Large Data	Slow	Fast
Best Case Complexity	O(1) (if first element is found)	O(1) (if middle element is found)
Worst Case Complexity	O(n)	O(log n)
Use Case	Small datasets, unsorted data	Large datasets, sorted data

 

📌 Deque and Priority Queue in C

1️⃣ Deque (Double-Ended Queue)

A Deque (Double-Ended Queue) is a special type of queue where elements can be added or removed from both the front and the rear.

🔹 Types of Deques:
1️⃣ Input-Restricted Deque – Insertions allowed only at rear, but deletions allowed at both ends.
2️⃣ Output-Restricted Deque – Deletions allowed only from front, but insertions allowed at both ends.

---

✅ C Program: Deque Using Array

#include <stdio.h>
#define SIZE 5  // Define the max size

int deque[SIZE], front = -1, rear = -1;

// Check if deque is full
int isFull() {
    return ((front == 0 && rear == SIZE - 1) || (front == rear + 1));
}

// Check if deque is empty
int isEmpty() {
    return (front == -1);
}

// Insert at the front
void insertFront(int value) {
    if (isFull()) {
        printf("Deque Overflow!\n");
        return;
    }
    if (isEmpty()) front = rear = 0;
    else if (front == 0) front = SIZE - 1;
    else front--;

    deque[front] = value;
    printf("Inserted %d at Front\n", value);
}

// Insert at the rear
void insertRear(int value) {
    if (isFull()) {
        printf("Deque Overflow!\n");
        return;
    }
    if (isEmpty()) front = rear = 0;
    else if (rear == SIZE - 1) rear = 0;
    else rear++;

    deque[rear] = value;
    printf("Inserted %d at Rear\n", value);
}

// Delete from the front
void deleteFront() {
    if (isEmpty()) {
        printf("Deque Underflow!\n");
        return;
    }
    printf("Deleted %d from Front\n", deque[front]);
    if (front == rear) front = rear = -1;
    else if (front == SIZE - 1) front = 0;
    else front++;
}

// Delete from the rear
void deleteRear() {
    if (isEmpty()) {
        printf("Deque Underflow!\n");
        return;
    }
    printf("Deleted %d from Rear\n", deque[rear]);
    if (front == rear) front = rear = -1;
    else if (rear == 0) rear = SIZE - 1;
    else rear--;
}

// Display Deque
void display() {
    if (isEmpty()) {
        printf("Deque is empty!\n");
        return;
    }
    printf("Deque: ");
    int i = front;
    while (1) {
        printf("%d ", deque[i]);
        if (i == rear) break;
        i = (i + 1) % SIZE;
    }
    printf("\n");
}

int main() {
    insertRear(10);
    insertRear(20);
    insertFront(5);
    display();
    
    deleteFront();
    display();
    
    insertFront(15);
    deleteRear();
    display();
    
    return 0;
}

✅ Efficient operations at both ends
✅ Useful for complex data structures (e.g., Palindrome checking, Undo/Redo functionality, etc.)

---

2️⃣ Priority Queue

A Priority Queue is a queue where each element has a priority.
🔹 Higher-priority elements are dequeued before lower-priority elements.
🔹 Can be implemented using arrays, linked lists, or heaps.

---

✅ C Program: Priority Queue Using Array

#include <stdio.h>
#define SIZE 5

struct PriorityQueue {
    int data;
    int priority;
} pq[SIZE];

int count = 0;

// Insert an element into priority queue
void insert(int value, int priority) {
    if (count == SIZE) {
        printf("Priority Queue Overflow!\n");
        return;
    }
    int i = count - 1;
    while (i >= 0 && pq[i].priority > priority) {
        pq[i + 1] = pq[i];
        i--;
    }
    pq[i + 1].data = value;
    pq[i + 1].priority = priority;
    count++;
    printf("Inserted %d with priority %d\n", value, priority);
}

// Remove highest-priority element
void delete() {
    if (count == 0) {
        printf("Priority Queue Underflow!\n");
        return;
    }
    printf("Removed %d with priority %d\n", pq[0].data, pq[0].priority);
    for (int i = 0; i < count - 1; i++) {
        pq[i] = pq[i + 1];
    }
    count--;
}

// Display priority queue
void display() {
    if (count == 0) {
        printf("Priority Queue is empty!\n");
        return;
    }
    printf("Priority Queue: ");
    for (int i = 0; i < count; i++) {
        printf("(%d, P:%d) ", pq[i].data, pq[i].priority);
    }
    printf("\n");
}

int main() {
    insert(10, 2);
    insert(20, 1);
    insert(30, 3);
    display();
    
    delete();
    display();
    
    return 0;
}

✅ Processes high-priority elements first
✅ Used in scheduling, networking, AI algorithms

---

3️⃣ Comparison: Deque vs Priority Queue

Feature	Deque	Priority Queue
Insertion	Both ends	Based on priority
Deletion	Both ends	Always removes highest priority
Order	FIFO (both sides)	Priority-based
Implementation	Array, Linked List	Array, Heap, Linked List
Use Case	Undo/Redo, Palindrome checking	Scheduling, Dijkstra’s Algorithm

 

📌 Array and Linked List Implementation of Queues in C

A Queue is a FIFO (First-In, First-Out) data structure. It allows elements to be added from the rear and removed from the front.

---

1️⃣ Queue Using Arrays

🔹 Fixed size, which can lead to space wastage.
🔹 Uses a circular approach to optimize space.

✅ C Program: Queue Using Array

#include <stdio.h>
#define SIZE 5  // Define queue size

int queue[SIZE], front = -1, rear = -1;

// Check if queue is empty
int isEmpty() {
    return (front == -1);
}

// Check if queue is full
int isFull() {
    return (rear == SIZE - 1);
}

// Enqueue operation
void enqueue(int value) {
    if (isFull()) {
        printf("Queue Overflow! Cannot insert %d\n", value);
        return;
    }
    if (front == -1) front = 0;  // Initialize front if queue is empty
    queue[++rear] = value;
    printf("Enqueued: %d\n", value);
}

// Dequeue operation
void dequeue() {
    if (isEmpty()) {
        printf("Queue Underflow! No element to remove\n");
        return;
    }
    printf("Dequeued: %d\n", queue[front]);
    if (front == rear) front = rear = -1;  // Reset queue when empty
    else front++;
}

// Display the queue
void display() {
    if (isEmpty()) {
        printf("Queue is empty!\n");
        return;
    }
    printf("Queue: ");
    for (int i = front; i <= rear; i++)
        printf("%d ", queue[i]);
    printf("\n");
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    display();
    
    dequeue();
    display();
    
    enqueue(40);
    enqueue(50);
    enqueue(60);
    display();
    
    return 0;
}

✅ Simple implementation
❌ Fixed size & memory wastage after deletions

---

2️⃣ Queue Using Linked List

🔹 Dynamic size, so no space wastage.
🔹 Requires additional memory for pointers.

✅ C Program: Queue Using Linked List

#include <stdio.h>
#include <stdlib.h>

// Define Node structure
struct Node {
    int data;
    struct Node* next;
};

struct Node *front = NULL, *rear = NULL;

// Check if queue is empty
int isEmpty() {
    return (front == NULL);
}

// Enqueue operation
void enqueue(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    if (isEmpty()) {
        front = rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
    printf("Enqueued: %d\n", value);
}

// Dequeue operation
void dequeue() {
    if (isEmpty()) {
        printf("Queue Underflow! No element to remove\n");
        return;
    }
    struct Node* temp = front;
    printf("Dequeued: %d\n", front->data);
    front = front->next;
    free(temp);

    if (front == NULL) rear = NULL;  // Reset rear when queue is empty
}

// Display the queue
void display() {
    if (isEmpty()) {
        printf("Queue is empty!\n");
        return;
    }
    struct Node* temp = front;
    printf("Queue: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    display();
    
    dequeue();
    display();
    
    enqueue(40);
    enqueue(50);
    display();
    
    return 0;
}

✅ Efficient memory usage
✅ No size restriction
❌ Extra memory needed for pointers

---

3️⃣ Comparison: Array vs Linked List Implementation

Feature	Array Implementation	Linked List Implementation
Memory Usage	Fixed size (wastes space)	Dynamic size (efficient)
Time Complexity (Enqueue/Dequeue)	O(1)	O(1)
Implementation Complexity	Simple	More complex (requires pointers)
Memory Overhead	No extra memory needed	Extra memory for pointers
Speed	Faster (better cache locality)	Slightly slower

 

📌 Circular Queue: Creation, Addition, Deletion, Full & Empty Conditions

A Circular Queue is an improved version of a simple queue, where the last position is connected to the first to form a circle. This avoids wastage of space seen in normal queue implementations.

---

1️⃣ Why Use a Circular Queue?

🔹 Efficient Memory Utilization – Unlike linear queues, no space is wasted after deletions.
🔹 Circular Connections – The rear can wrap around to the front when space is available.
🔹 Used in Operating Systems, CPU Scheduling, Buffer Management.

---

2️⃣ Basic Operations on Circular Queue

Operation	Description
Create	Initializes an empty queue.
Enqueue (Add)	Inserts an element at the rear.
Dequeue (Delete)	Removes an element from the front.
isFull()	Checks if the queue is full.
isEmpty()	Checks if the queue is empty.
Front() / Peek()	Returns the front element without removing it.

---

3️⃣ Circular Queue Implementation in C

(a) Using Arrays

#include <stdio.h>
#define SIZE 5  // Define maximum size of queue

int queue[SIZE], front = -1, rear = -1;

// Check if the queue is empty
int isEmpty() {
    return (front == -1);
}

// Check if the queue is full
int isFull() {
    return ((rear + 1) % SIZE == front);
}

// Insert an element in Circular Queue
void enqueue(int value) {
    if (isFull()) {
        printf("Queue is Full!\n");
        return;
    }
    if (front == -1) front = 0;  // Initialize front if queue was empty
    rear = (rear + 1) % SIZE;
    queue[rear] = value;
    printf("Enqueued: %d\n", value);
}

// Remove an element from Circular Queue
void dequeue() {
    if (isEmpty()) {
        printf("Queue is Empty!\n");
        return;
    }
    printf("Dequeued: %d\n", queue[front]);
    if (front == rear) front = rear = -1;  // Reset when queue becomes empty
    else front = (front + 1) % SIZE;
}

// Display Circular Queue
void display() {
    if (isEmpty()) {
        printf("Queue is Empty!\n");
        return;
    }
    printf("Queue: ");
    int i = front;
    while (1) {
        printf("%d ", queue[i]);
        if (i == rear) break;
        i = (i + 1) % SIZE;
    }
    printf("\n");
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    enqueue(40);
    enqueue(50);
    display();
    
    dequeue();
    dequeue();
    display();
    
    enqueue(60);
    enqueue(70);
    display();
    
    return 0;
}

✅ Fixes wasted space issue of normal queues.
✅ Efficient operations with O(1) time complexity.

---

(b) Circular Queue Using Linked List

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

struct Node *front = NULL, *rear = NULL;

// Check if the queue is empty
int isEmpty() {
    return (front == NULL);
}

// Insert an element
void enqueue(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    if (isEmpty()) {
        front = rear = newNode;
        rear->next = front;  // Circular link
    } else {
        rear->next = newNode;
        rear = newNode;
        rear->next = front;  // Maintain circular connection
    }
    printf("Enqueued: %d\n", value);
}

// Remove an element
void dequeue() {
    if (isEmpty()) {
        printf("Queue is Empty!\n");
        return;
    }
    struct Node* temp = front;
    printf("Dequeued: %d\n", front->data);

    if (front == rear) {  // Single element in queue
        front = rear = NULL;
    } else {
        front = front->next;
        rear->next = front;
    }
    free(temp);
}

// Display the queue
void display() {
    if (isEmpty()) {
        printf("Queue is Empty!\n");
        return;
    }
    struct Node* temp = front;
    printf("Queue: ");
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != front);
    printf("\n");
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    display();
    
    dequeue();
    display();
    
    return 0;
}

✅ Dynamic size (no fixed limit like array)
✅ Efficient for real-time processing

---

4️⃣ When is a Circular Queue Used?

💡 Circular Queues are used when:
✔ Fixed-size storage is needed (e.g., Buffer management, CPU scheduling).
✔ We want to reuse space efficiently after deletions.
✔ Low time complexity is required (O(1) enqueue & dequeue).