DSA: Queues

A queue is a linear data structure that follows the First In First Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed. It can be visualized as a line of people waiting to buy tickets: the person who arrives first gets served first, and new arrivals join the end of the line.

Basic Operations

1. Enqueue: Adding an element to the end (rear) of the queue.

2. Dequeue: Removing an element from the front of the queue.

3. Peek/Front: Accessing the front element of the queue without removing it.

4. isEmpty: Checking if the queue is empty.

5. isFull: Checking if the queue is full (in case of fixed-size implementations).

Types of Queues

1. Simple Queue (Linear Queue): The basic FIFO structure.

2. Circular Queue: Connects the end of the queue back to the front, forming a circle. This allows better utilization of storage.

3. Priority Queue: Each element has a priority, and elements with higher priority are dequeued before those with lower priority.

4. Deque (Double-Ended Queue): Allows insertion and deletion of elements from both ends of the queue.

We will explore simple queues and deques in this article. The rest will be covered in subsequent topics.

Significance in Data Structures

1. Order Maintenance: Queues are essential for maintaining order in systems where tasks need to be processed sequentially. Examples include scheduling tasks in operating systems, managing requests in web servers, and handling tasks in print queues.

2. Buffering: Queues serve as buffers in many applications, such as IO streams, network data packet management, and asynchronous data transfers between processes. This helps in managing and controlling the flow of data.

3. Breadth-First Search (BFS): In graph algorithms, queues are crucial for implementing BFS, which explores nodes level by level. This is essential for finding the shortest path in unweighted graphs and for exploring all possible paths.

4. Simulation: Queues are used in simulation problems to model real-world scenarios where entities are processed in the order of their arrival, such as customer service simulations, traffic management systems, and event-driven simulations.

5. Resource Management: Queues help in managing resources by organizing tasks into a waiting line, ensuring fair allocation and preventing resource contention. Examples include job scheduling in printers and managing processes in a CPU.

Applications of Queues

1. Operating Systems: Managing tasks, processes, and threads.

2. Network Routers: Handling data packets for transmission.

3. Printers: Managing print jobs.

4. Web Servers: Handling multiple client requests.

5. Customer Service Systems: Managing customer service requests and interactions.

Simple Queue (Linear Queue) Implementation in C

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

#define MAX 100 // Maximum size of the queue

typedef struct {
    int items[MAX];
    int front;
    int rear;
} Queue;

// Function to create an empty queue
void initializeQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

// Function to check if the queue is full
bool isFull(Queue *q) {
    return q->rear == MAX - 1;
}

// Function to check if the queue is empty
bool isEmpty(Queue *q) {
    return q->front == -1 || q->front > q->rear;
}

// Function to add an element to the queue (enqueue)
void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear++;
    q->items[q->rear] = value;
    printf("Inserted %d\n", value);
}

// Function to remove an element from the queue (dequeue)
int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int item = q->items[q->front];
    q->front++;
    if (isEmpty(q)) {
        initializeQueue(q); // Reset the queue if it's empty after dequeue
    }
    return item;
}

// Function to get the front element of the queue
int peek(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    return q->items[q->front];
}

// Function to display the queue elements
void displayQueue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return;
    }
    printf("Queue elements are: ");
    for (int i = q->front; i <= q->rear; i++) {
        printf("%d ", q->items[i]);
    }
    printf("\n");
}

int main() {
    Queue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    enqueue(&q, 40);

    displayQueue(&q);

    printf("Dequeued: %d\n", dequeue(&q));
    printf("Dequeued: %d\n", dequeue(&q));

    displayQueue(&q);

    printf("Front element is: %d\n", peek(&q));

    return 0;
}

Explanation

1. Initialization: The queue is initialized with front and rear set to -1, indicating that the queue is empty.

2. isFull and isEmpty: These functions are helper functions to check the state of the queue. isFull checks if rear has reached the maximum size, and isEmpty checks if there are no elements in the queue.

3. Enqueue Operation: When adding an element, the function first checks if the queue is full. If not, it updates the rear index and inserts the new element at items[rear]. If the queue was empty, it sets front to 0.

4. Dequeue Operation: When removing an element, the function first checks if the queue is empty. If not, it returns the element at items[front] and increments the front index. If the queue becomes empty after the dequeue operation, it resets the front and rear indices.

5. Peek Operation: This function returns the element at the front of the queue without removing it.

6. Display Function: This function iterates through the queue from front to rear and prints each element.

Example:

Initial State
Queue: [ _ , _ , _ , _ , _ ]
Front: -1
Rear: -1

Enqueue 10
Queue: [ 10 , _ , _ , _ , _ ]
Front: 0
Rear: 0

Enqueue 20
Queue: [ 10 , 20 , _ , _ , _ ]
Front: 0
Rear: 1

Enqueue 30
Queue: [ 10 , 20 , 30 , _ , _ ]
Front: 0
Rear: 2

Dequeue (Removes 10)
Queue: [ _ , 20 , 30 , _ , _ ]
Front: 1
Rear: 2

Enqueue 40
Queue: [ _ , 20 , 30 , 40 , _ ]
Front: 1
Rear: 3

Enqueue 50
Queue: [ _ , 20 , 30 , 40 , 50 ]
Front: 1
Rear: 4

Dequeue (Removes 20)
Queue: [ _ , _ , 30 , 40 , 50 ]
Front: 2
Rear: 4

Dequeue (Removes 30)
Queue: [ _ , _ , _ , 40 , 50 ]
Front: 3
Rear: 4

Enqueue 60
Queue: [ 60 , _ , _ , 40 , 50 ]
Front: 3
Rear: 0

Enqueue 70
Queue: [ 60 , 70 , _ , 40 , 50 ]
Front: 3
Rear: 1

Dequeue (Removes 40)
Queue: [ 60 , 70 , _ , _ , 50 ]
Front: 4
Rear: 1

Enqueue 80
Queue: [ 60 , 70 , 80 , _ , 50 ]
Front: 4
Rear: 2

Dequeue (Removes 50)
Queue: [ 60 , 70 , 80 , _ , _ ]
Front: 0
Rear: 2

Dequeue (Removes 60)
Queue: [ _ , 70 , 80 , _ , _ ]
Front: 1
Rear: 2

Enqueue 90
Queue: [ _ , 70 , 80 , 90 , _ ]
Front: 1
Rear: 3

Enqueue 100
Queue: [ _ , 70 , 80 , 90 , 100 ]
Front: 1
Rear: 4

Dequeue (Removes 70)
Queue: [ _ , _ , 80 , 90 , 100 ]
Front: 2
Rear: 4

Dequeue (Removes 80)
Queue: [ _ , _ , _ , 90 , 100 ]
Front: 3
Rear: 4

Dequeue (Removes 90)
Queue: [ _ , _ , _ , _ , 100 ]
Front: 4
Rear: 4

Enqueue 110
Queue: [ 110 , _ , _ , _ , 100 ]
Front: 4
Rear: 0

Enqueue 120
Queue: [ 110 , 120 , _ , _ , 100 ]
Front: 4
Rear: 1

Simple Queue Implementation using Linked Lists in C

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

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

// Queue structure
typedef struct {
    Node* front;
    Node* rear;
} Queue;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to initialize the queue
void initializeQueue(Queue* q) {
    q->front = NULL;
    q->rear = NULL;
}

// Function to check if the queue is empty
bool isEmpty(Queue* q) {
    return q->front == NULL;
}

// Function to add an element to the queue (enqueue)
void enqueue(Queue* q, int data) {
    Node* newNode = createNode(data);
    if (!newNode) return;

    if (isEmpty(q)) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
    printf("Inserted %d\n", data);
}

// Function to remove an element from the queue (dequeue)
int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    Node* temp = q->front;
    int data = temp->data;
    q->front = q->front->next;

    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return data;
}

// Function to get the front element of the queue
int peek(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    return q->front->data;
}

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

int main() {
    Queue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    enqueue(&q, 40);

    displayQueue(&q);

    printf("Dequeued: %d\n", dequeue(&q));
    printf("Dequeued: %d\n", dequeue(&q));

    displayQueue(&q);

    printf("Front element is: %d\n", peek(&q));

    return 0;
}

Explanation

1. Node Structure

   • A Node structure is defined to represent each element in the queue. It contains an integer data to store the value and a pointer next to point to the next node in the queue.

2. Queue Structure

   • A Queue structure is defined to manage the queue. It contains two pointers: front to point to the front node and rear to point to the rear node.

3. createNode Function

   • This function creates a new node with the given data, initializes its next pointer to NULL, and returns the node. If memory allocation fails, it prints an error message and returns NULL.

4. initializeQueue Function

   • This function initializes the queue by setting both front and rear pointers to NULL, indicating an empty queue.

5. isEmpty Function

   • This function checks if the queue is empty by returning true if front is NULL, otherwise false.

6. enqueue Function

   • This function adds a new element to the rear of the queue. It creates a new node and checks if the queue is empty. If the queue is empty, it sets both front and rear to the new node. Otherwise, it sets the next pointer of the current rear node to the new node and updates the rear pointer to the new node.

7. dequeue Function

   • This function removes and returns the element at the front of the queue. It first checks if the queue is empty. If it is, it prints an error message and returns -1. Otherwise, it stores the data of the front node, updates the front pointer to the next node, frees the old front node, and returns the stored data. If the queue becomes empty after the dequeue operation, it sets rear to NULL.

8. peek Function

   • This function returns the data of the front node without removing it. If the queue is empty, it prints an error message and returns -1.

9. displayQueue Function

   • This function prints all the elements in the queue from the front to the rear. If the queue is empty, it prints an appropriate message.

10. main Function

• The main function demonstrates the usage of the queue by performing several enqueue and dequeue operations and displaying the queue elements at each step. It initializes the queue, enqueues several elements, displays the queue, dequeues a few elements, displays the queue again, and finally prints the front element.

Deque (Double-Ended Queue) Implementation using Arrays in C

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

#define MAX 100 // Maximum size of the deque

typedef struct {
    int items[MAX];
    int front;
    int rear;
    int size;
} Deque;

// Function to initialize the deque
void initializeDeque(Deque* dq) {
    dq->front = -1;
    dq->rear = 0;
    dq->size = 0;
}

// Function to check if the deque is full
int isFull(Deque* dq) {
    return dq->size == MAX;
}

// Function to check if the deque is empty
int isEmpty(Deque* dq) {
    return dq->size == 0;
}

// Function to insert an element at the front of the deque
void insertFront(Deque* dq, int value) {
    if (isFull(dq)) {
        printf("Deque is full\n");
        return;
    }
    if (dq->front == -1) {
        dq->front = 0;
        dq->rear = 0;
    } else if (dq->front == 0) {
        dq->front = MAX - 1;
    } else {
        dq->front = dq->front - 1;
    }
    dq->items[dq->front] = value;
    dq->size++;
    printf("Inserted %d at front\n", value);
}

// Function to insert an element at the rear of the deque
void insertRear(Deque* dq, int value) {
    if (isFull(dq)) {
        printf("Deque is full\n");
        return;
    }
    if (dq->front == -1) {
        dq->front = 0;
        dq->rear = 0;
    } else if (dq->rear == MAX - 1) {
        dq->rear = 0;
    } else {
        dq->rear = dq->rear + 1;
    }
    dq->items[dq->rear] = value;
    dq->size++;
    printf("Inserted %d at rear\n", value);
}

// Function to delete an element from the front of the deque
int deleteFront(Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return -1;
    }
    int data = dq->items[dq->front];
    if (dq->front == dq->rear) {
        dq->front = -1;
        dq->rear = -1;
    } else if (dq->front == MAX - 1) {
        dq->front = 0;
    } else {
        dq->front = dq->front + 1;
    }
    dq->size--;
    printf("Deleted %d from front\n", data);
    return data;
}

// Function to delete an element from the rear of the deque
int deleteRear(Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return -1;
    }
    int data = dq->items[dq->rear];
    if (dq->front == dq->rear) {
        dq->front = -1;
        dq->rear = -1;
    } else if (dq->rear == 0) {
        dq->rear = MAX - 1;
    } else {
        dq->rear = dq->rear - 1;
    }
    dq->size--;
    printf("Deleted %d from rear\n", data);
    return data;
}

// Function to get the front element of the deque
int getFront(Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return -1;
    }
    return dq->items[dq->front];
}

// Function to get the rear element of the deque
int getRear(Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return -1;
    }
    return dq->items[dq->rear];
}

// Function to display the deque elements
void displayDeque(Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return;
    }
    int i = dq->front;
    printf("Deque elements are: ");
    while (1) {
        printf("%d ", dq->items[i]);
        if (i == dq->rear) {
            break;
        }
        i = (i + 1) % MAX;
    }
    printf("\n");
}

int main() {
    Deque dq;
    initializeDeque(&dq);

    insertRear(&dq, 10);
    insertRear(&dq, 20);
    insertFront(&dq, 5);
    insertRear(&dq, 30);

    displayDeque(&dq);

    printf("Deleted from front: %d\n", deleteFront(&dq));
    printf("Deleted from rear: %d\n", deleteRear(&dq));

    displayDeque(&dq);

    printf("Front element: %d\n", getFront(&dq));
    printf("Rear element: %d\n", getRear(&dq));

    return 0;
}

Explanation

1. Deque Structure

   • A Deque structure is defined with an array items to store elements, and three integers: front to point to the front of the deque, rear to point to the rear of the deque, and size to keep track of the number of elements.

2. initializeDeque Function

   • This function initializes the deque by setting front to -1, rear to 0, and size to 0, indicating an empty deque.

3. isFull Function

   • This function checks if the deque is full by comparing size to MAX.

4. isEmpty Function

   • This function checks if the deque is empty by checking if size is 0.

5. insertFront Function

   • This function inserts a new element at the front of the deque. If the deque is full, it prints an error message. If the deque is empty, it sets both front and rear to 0. If front is at the beginning of the array, it wraps around to the end. Otherwise, it decrements front. The new element is then added to items[front], and size is incremented.

6. insertRear Function

   • This function inserts a new element at the rear of the deque. If the deque is full, it prints an error message. If the deque is empty, it sets both front and rear to 0. If rear is at the end of the array, it wraps around to the beginning. Otherwise, it increments rear. The new element is then added to items[rear], and size is incremented.

7. deleteFront Function

   • This function removes and returns the element at the front of the deque. If the deque is empty, it prints an error message and returns -1. If front is the same as rear, it sets both front and rear to -1, indicating an empty deque. If front is at the end of the array, it wraps around to the beginning. Otherwise, it increments front. The removed element's data is stored and returned, and size is decremented.

8. deleteRear Function

   • This function removes and returns the element at the rear of the deque. If the deque is empty, it prints an error message and returns -1. If front is the same as rear, it sets both front and rear to -1, indicating an empty deque. If rear is at the beginning of the array, it wraps around to the end. Otherwise, it decrements rear. The removed element's data is stored and returned, and size is decremented.

9. getFront Function

   • This function returns the data of the front element without removing it. If the deque is empty, it prints an error message and returns -1.

10. getRear Function

    • This function returns the data of the rear element without removing it. If the deque is empty, it prints an error message and returns -1.

11. displayDeque Function

    • This function prints all the elements in the deque from front to rear. It handles wrapping around the end of the array by using the modulo operator %.

12. main Function

    • The main function demonstrates the usage of the deque by performing several insert and delete operations and displaying the deque elements at each step. It initializes the deque, inserts several elements at both ends, deletes a few elements from both ends, and prints the front and rear elements.

Example

Initial State
Deque: [ _ , _ , _ , _ , _ ]
Front: -1
Rear: -1

Insert 10 at rear
Deque: [ 10 , _ , _ , _ , _ ]
Front: 0
Rear: 0

Insert 20 at front
Deque: [ 10 , _ , _ , _ , 20 ]
Front: 4
Rear: 0

Insert 30 at rear
Deque: [ 10 , 30 , _ , _ , 20 ]
Front: 4
Rear: 1

Delete from front
Deque: [ 10 , 30 , _ , _ , _ ]
Front: 0
Rear: 1

Insert 40 at front
Deque: [ 10 , 30 , _ , 40 , _ ]
Front: 3
Rear: 1

Insert 50 at rear
Deque: [ 10 , 30 , 50 , 40 , _ ]
Front: 3
Rear: 2

Delete from rear
Deque: [ 10 , 30 , _ , 40 , _ ]
Front: 3
Rear: 1

Insert 60 at rear
Deque: [ 10 , 30 , 60 , 40 , _ ]
Front: 3
Rear: 2

Insert 70 at front
Deque: [ 10 , 30 , 60 , 40 , 70 ]
Front: 4
Rear: 2

Delete from front
Deque: [ 10 , 30 , 60 , 40 , _ ]
Front: 0
Rear: 2

Problems

Beginner Level

1. Basic Queue Operations

   • Implement a queue using an array. Perform basic operations: enqueue, dequeue, peek, and isEmpty.

2. Print Queue Elements

   • Write a program to print all elements of a queue.

3. Queue Size

   • Modify the queue implementation to include a function that returns the current size of the queue.

4. Circular Queue

   • Implement a circular queue using an array. Handle wrap-around conditions properly.

5. Queue Reversal

   • Write a function to reverse the elements of a queue.

Intermediate Level

1. Queue Using Linked List

   • Implement a queue using a linked list. Perform basic operations: enqueue, dequeue, peek, and isEmpty.

2. Generate Binary Numbers from 1 to N

   • Write a program that uses a queue to generate binary numbers from 1 to N.

3. Interleave the First Half of the Queue with the Second Half

   • Given a queue of integers, interleave the first half of the queue with the second half.

4. Sum of Elements in Queue

   • Write a function to find the sum of all elements in a queue.

5. Merge Two Queues

   • Write a function to merge two queues into a single queue. The function should take two queues as input and return a new queue that contains all elements of the two input queues.

Advanced Level

1. Design a Circular Deque

   • Implement a circular deque using an array. Perform all basic operations: insertFront, insertRear, deleteFront, deleteRear, getFront, getRear, isEmpty, and isFull.

2. Sliding Window Maximum

   • Given an array of integers and a number k, find the maximum value in each sliding window of size k using a deque.

3. First Non-Repeating Character in a Stream

   • Given a stream of characters, find the first non-repeating character at any point in the stream using a queue.

4. Reverse First k Elements of Queue

   • Given an integer k and a queue of integers, reverse the order of the first k elements of the queue, leaving the other elements in the same relative order.

5. Sum of Minimum and Maximum Elements of All Subarrays of Size k

   • Given an array of integers and an integer k, find the sum of the minimum and maximum elements of all subarrays of size k using a deque.

Expert Level

1. Task Scheduling with Cooldown

   • Given a list of tasks and a cooldown period, find the minimum time required to complete all tasks without executing the same task within the cooldown period. Use a queue to simulate the process.

2. Circular Tour Problem

   • Given n petrol pumps arranged in a circle where each petrol pump has a certain amount of petrol and a certain distance to the next petrol pump, find the starting petrol pump index from where you can complete the circular tour.

3. Check for Palindrome using Queue

   • Write a function to check if the given string is a palindrome using a queue.

4. Distance of Nearest Cell Having 1 in a Binary Matrix

   • Given a binary matrix, find the distance of the nearest cell having 1 for each cell. The distance is calculated as the number of cells in the shortest path from a cell to the nearest cell having value 1. Use a queue to solve this problem.

5. Multiple Queues in a Single Array

   • Implement multiple queues in a single array. Ensure that you can perform enqueue and dequeue operations independently on each queue.

Hints

Beginner Level

1. Basic Queue Operations

   • Approach: Use an array to implement a queue and maintain two pointers, front and rear, to track the positions for dequeuing and enqueuing elements respectively. The enqueue operation adds elements to the position pointed by rear and increments rear. The dequeue operation removes elements from the position pointed by front and increments front. The peek operation returns the element at the front without removing it. Check for an empty queue by verifying if front exceeds rear, and for a full queue if rear exceeds the array size.

   • Hints: Initialize front to 0 and rear to -1. Increment rear when enqueuing and increment front when dequeuing. Ensure to check for underflow and overflow conditions.

2. Print Queue Elements

   • Approach: Traverse the queue from front to rear and print each element. This will display all elements currently in the queue in their order of insertion.

   • Hints: Use a loop to iterate from front to rear and print the elements. Ensure that the queue is not empty before starting the loop.

3. Queue Size

   • Approach: Maintain a variable size to keep track of the number of elements in the queue. Increment size on enqueue and decrement size on dequeue. Create a function to return the value of size.

   • Hints: Initialize size to 0. Modify the enqueue and dequeue operations to update size accordingly. The function to get the size simply returns the size variable.

4. Circular Queue

   • Approach: Use an array to implement a circular queue, where the rear wraps around to the start of the array when it reaches the end. Modify the enqueue and dequeue operations to handle the wrap-around using the modulo operator.

   • Hints: Use (rear + 1) % MAX for the enqueue operation and (front + 1) % MAX for the dequeue operation. Ensure to handle the cases when the queue becomes full or empty appropriately.

5. Queue Reversal

   • Approach: Use an auxiliary array or list to temporarily store the elements while dequeuing them from the queue, and then re-enqueue them back to the queue in reverse order.

   • Hints: Dequeue all elements and store them in a temporary array. Then, enqueue elements from the temporary array back to the queue in reverse order.

Intermediate Level

1. Queue Using Linked List

   • Approach: Implement a queue using a linked list where each node contains the data and a pointer to the next node. Maintain two pointers, front and rear, to track the first and last nodes of the queue.

   • Hints: Initialize front and rear to NULL. For enqueue, create a new node and update rear's next pointer. For dequeue, update front to the next node. Handle edge cases when the queue becomes empty.

2. Generate Binary Numbers from 1 to N

   • Approach: Use a queue to generate binary numbers by enqueuing "1" initially and then generating the next numbers by appending "0" and "1" to the dequeued number.

   • Hints: Enqueue the string "1". For each number, dequeue it, print it, and then enqueue the numbers formed by appending "0" and "1" to it. Repeat this until you generate N numbers.

3. Interleave the First Half of the Queue with the Second Half

   • Approach: Split the queue into two halves using a secondary queue. Reinsert elements from the secondary queue in an interleaved manner with the remaining elements in the original queue.

   • Hints: Dequeue the first half of the elements and enqueue them into a secondary queue. Then, alternate dequeuing from both queues and enqueuing back to the original queue.

4. Sum of Elements in Queue

   • Approach: Traverse the queue from front to rear and calculate the sum of all elements.

   • Hints: Initialize a sum variable to 0. Iterate through the queue elements from front to rear and add each element to the sum variable.

5. Merge Two Queues

   • Approach: Create a new queue and alternate elements from the two input queues until both are empty. Enqueue elements from each queue into the new queue.

   • Hints: Use a loop to dequeue elements from both queues and enqueue them into the new queue. Handle cases when one queue becomes empty before the other.

Advanced Level

1. Design a Circular Deque

   • Approach: Use an array to implement a circular deque with operations to insert and delete elements from both ends. Maintain front and rear pointers that wrap around using the modulo operator.

   • Hints: For insertions and deletions at the front, use (front - 1 + MAX) % MAX. For insertions and deletions at the rear, use (rear + 1) % MAX. Handle full and empty conditions appropriately.

2. Sliding Window Maximum

   • Approach: Use a deque to maintain indices of useful elements for each window. Remove elements not within the current window and ensure the deque contains elements in decreasing order.

   • Hints: Traverse the array and for each element, remove elements from the deque that are out of the current window and maintain the order by removing elements smaller than the current element from the rear.

3. First Non-Repeating Character in a Stream

   • Approach: Use a queue to maintain the order of characters and a frequency array to keep track of counts. For each character, enqueue it and update its frequency. Dequeue characters from the front until the front of the queue is non-repeating.

   • Hints: Use an array to store character frequencies. Enqueue characters as they appear and dequeue from the front if they become repeating.

4. Reverse First k Elements of Queue

   • Approach: Use an auxiliary array to store the first k elements while dequeuing them, and then re-enqueue these elements back to the queue in reverse order. Finally, re-enqueue the remaining elements.

   • Hints: Dequeue the first k elements into an auxiliary array. Enqueue elements from the array back to the queue in reverse order. Then, re-enqueue the remaining elements.

5. Sum of Minimum and Maximum Elements of All Subarrays of Size k

   • Approach: Use two deques to find the minimum and maximum elements in each subarray of size k. Sum these values for all subarrays.

   • Hints: Maintain two deques for minimum and maximum values. For each new element, update the deques by removing out-of-window elements and maintaining the order for minimum and maximum values. Compute the sum for each window.

Expert Level

1. Task Scheduling with Cooldown

   • Approach: Use a queue to manage the cooldown period of tasks. Enqueue tasks and maintain the order of execution while respecting the cooldown period.

   • Hints: Use a queue to track the cooldown period. Dequeue and re-enqueue tasks after processing if they have a remaining cooldown. Ensure that a task is only executed again after its cooldown period has expired.

2. Circular Tour Problem

   • Approach: Use a queue to simulate the tour starting from each petrol pump. Track the net petrol balance and determine if a complete tour is possible from a given starting point.

   • Hints: Initialize a starting point and use a loop to track the petrol balance while simulating the tour. Adjust the starting point based on the petrol balance.

3. Check for Palindrome using Queue

   • Approach: Use a queue to store characters of a string and compare them in reverse order to check if the string is a palindrome.

   • Hints: Enqueue characters of the string into the queue. Dequeue characters and compare them with the characters from the end of the string.

4. Distance of Nearest Cell Having 1 in a Binary Matrix

   • Approach: Use a queue to perform a Breadth-First Search (BFS) from each cell containing a 1 to calculate the shortest distance to all other cells.

   • Hints: Enqueue all cells containing 1 initially. Use BFS to update the distances of neighboring cells iteratively.

5. Multiple Queues in a Single Array

   • Approach: Implement multiple queues within a single array by dividing the array into segments and managing separate front and rear pointers for each queue.

   • Hints: Calculate the starting index and size for each queue segment. Manage front and rear pointers independently for each segment within the array. Handle enqueue and dequeue operations within the designated segments.

Solutions

Beginner Level

1. Basic Queue Operations

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

#define MAX 5

typedef struct {
    int items[MAX];
    int front;
    int rear;
} Queue;

void initializeQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

bool isFull(Queue *q) {
    return q->rear == MAX - 1;
}

bool isEmpty(Queue *q) {
    return q->front == -1 || q->front > q->rear;
}

void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear++;
    q->items[q->rear] = value;
    printf("Inserted %d\n", value);
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int item = q->items[q->front];
    q->front++;
    if (isEmpty(q)) {
        initializeQueue(q); // Reset the queue if it's empty after dequeue
    }
    return item;
}

int peek(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    return q->items[q->front];
}

int main() {
    Queue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    enqueue(&q, 40);
    enqueue(&q, 50);

    printf("Front element is %d\n", peek(&q));
    printf("Dequeued %d\n", dequeue(&q));
    printf("Dequeued %d\n", dequeue(&q));

    enqueue(&q, 60);
    enqueue(&q, 70);

    while (!isEmpty(&q)) {
        printf("Dequeued %d\n", dequeue(&q));
    }

    return 0;
}

Explanation with Example:

1. Initialize an empty queue.

2. Enqueue elements: 10, 20, 30, 40, 50.

3. Peek at the front element, which is 10.

4. Dequeue two elements: 10 and 20.

5. Enqueue elements: 60 and 70.

6. Dequeue all remaining elements.

Initial State:
Queue: [ _ , _ , _ , _ , _ ]
Front: -1
Rear: -1

Enqueue 10:
Queue: [ 10 , _ , _ , _ , _ ]
Front: 0
Rear: 0

Enqueue 20:
Queue: [ 10 , 20 , _ , _ , _ ]
Front: 0
Rear: 1

Enqueue 30:
Queue: [ 10 , 20 , 30 , _ , _ ]
Front: 0
Rear: 2

Enqueue 40:
Queue: [ 10 , 20 , 30 , 40 , _ ]
Front: 0
Rear: 3

Enqueue 50:
Queue: [ 10 , 20 , 30 , 40 , 50 ]
Front: 0
Rear: 4

Peek:
Front element is 10

Dequeue:
Dequeued 10
Queue: [ _ , 20 , 30 , 40 , 50 ]
Front: 1
Rear: 4

Dequeue:
Dequeued 20
Queue: [ _ , _ , 30 , 40 , 50 ]
Front: 2
Rear: 4

Enqueue 60:
Queue: [ _ , _ , 30 , 40 , 50 , 60 ]
Front: 2
Rear: 0

Enqueue 70:
Queue: [ 70 , _ , 30 , 40 , 50 , 60 ]
Front: 2
Rear: 1

Final Dequeue:
Dequeued 30
Dequeued 40
Dequeued 50
Dequeued 60
Dequeued 70
Queue: [ _ , _ , _ , _ , _ ]
Front: -1
Rear: -1

2. Print Queue Elements

#include <stdio.h>
#include <stdbool.h>

#define MAX 5

typedef struct {
    int items[MAX];
    int front;
    int rear;
} Queue;

void initializeQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

bool isEmpty(Queue *q) {
    return q->front == -1 || q->front > q->rear;
}

void enqueue(Queue *q, int value) {
    if (q->rear == MAX - 1) {
        printf("Queue is full\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear++;
    q->items[q->rear] = value;
    printf("Inserted %d\n", value);
}

void printQueue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return;
    }
    printf("Queue elements: ");
    for (int i = q->front; i <= q->rear; i++) {
        printf("%d ", q->items[i]);
    }
    printf("\n");
}

int main() {
    Queue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    printQueue(&q);

    return 0;
}

Explanation with Example:

1. Initialize an empty queue.

2. Enqueue elements: 10, 20, 30.

3. Print the elements in the queue.

Initial State:
Queue: [ _ , _ , _ , _ , _ ]
Front: -1
Rear: -1

Enqueue 10:
Queue: [ 10 , _ , _ , _ , _ ]
Front: 0
Rear: 0

Enqueue 20:
Queue: [ 10 , 20 , _ , _ , _ ]
Front: 0
Rear: 1

Enqueue 30:
Queue: [ 10 , 20 , 30 , _ , _ ]
Front: 0
Rear: 2

Print Queue:
Queue elements: 10 20 30

3. Queue Size

#include <stdio.h>
#include <stdbool.h>

#define MAX 5

typedef struct {
    int items[MAX];
    int front;
    int rear;
    int size;
} Queue;

void initializeQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
    q->size = 0;
}

bool isEmpty(Queue *q) {
    return q->front == -1 || q->front > q->rear;
}

void enqueue(Queue *q, int value) {
    if (q->rear == MAX - 1) {
        printf("Queue is full\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear++;
    q->items[q->rear] = value;
    q->size++;
    printf("Inserted %d\n", value);
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int item = q->items[q->front];
    q->front++;
    q->size--;
    if (isEmpty(q)) {
        initializeQueue(q); // Reset the queue if it's empty after dequeue
    }
    return item;
}

int queueSize(Queue *q) {
    return q->size;
}

int main() {
    Queue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    printf("Queue size: %d\n", queueSize(&q));

    dequeue(&q);

    printf("Queue size after one dequeue: %d\n", queueSize(&q));

    return 0;
}

Explanation with Example:

1. Initialize an empty queue with a size counter.

2. Enqueue elements: 10, 20, 30.

3. Print the size of the queue.

4. Dequeue one element.

5. Print the size of the queue again.

Initial State:
Queue: [ _ , _ , _ , _ , _ ]
Front: -1
Rear: -1
Size: 0

Enqueue 10:
Queue: [ 10 , _ , _ , _ , _ ]
Front: 0
Rear: 0
Size: 1

Enqueue 20:
Queue: [ 10 , 20 , _ , _ , _ ]
Front: 0
Rear: 1
Size: 2

Enqueue 30:
Queue: [ 10 , 20 , 30 , _ , _ ]
Front: 0
Rear: 2
Size: 3

Queue Size:
Queue size: 3

Dequeue:
Dequeued 10
Queue: [ _ , 20 , 

30 , _ , _ ]
Front: 1
Rear: 2
Size: 2

Queue Size:
Queue size after one dequeue: 2

4. Circular Queue

#include <stdio.h>
#include <stdbool.h>

#define MAX 5

typedef struct {
    int items[MAX];
    int front;
    int rear;
} CircularQueue;

void initializeQueue(CircularQueue *q) {
    q->front = -1;
    q->rear = -1;
}

bool isFull(CircularQueue *q) {
    return (q->rear + 1) % MAX == q->front;
}

bool isEmpty(CircularQueue *q) {
    return q->front == -1;
}

void enqueue(CircularQueue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear = (q->rear + 1) % MAX;
    q->items[q->rear] = value;
    printf("Inserted %d\n", value);
}

int dequeue(CircularQueue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int item = q->items[q->front];
    if (q->front == q->rear) {
        initializeQueue(q); // Reset the queue if it's empty after dequeue
    } else {
        q->front = (q->front + 1) % MAX;
    }
    return item;
}

int main() {
    CircularQueue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    enqueue(&q, 40);
    enqueue(&q, 50);

    printf("Dequeued %d\n", dequeue(&q));
    enqueue(&q, 60);

    while (!isEmpty(&q)) {
        printf("Dequeued %d\n", dequeue(&q));
    }

    return 0;
}

Explanation with Example:

1. Initialize an empty circular queue.

2. Enqueue elements: 10, 20, 30, 40, 50.

3. Dequeue one element (10) and enqueue another (60).

4. Dequeue all remaining elements.

Initial State:
Queue: [ _ , _ , _ , _ , _ ]
Front: -1
Rear: -1

Enqueue 10:
Queue: [ 10 , _ , _ , _ , _ ]
Front: 0
Rear: 0

Enqueue 20:
Queue: [ 10 , 20 , _ , _ , _ ]
Front: 0
Rear: 1

Enqueue 30:
Queue: [ 10 , 20 , 30 , _ , _ ]
Front: 0
Rear: 2

Enqueue 40:
Queue: [ 10 , 20 , 30 , 40 , _ ]
Front: 0
Rear: 3

Enqueue 50:
Queue: [ 10 , 20 , 30 , 40 , 50 ]
Front: 0
Rear: 4

Dequeue:
Dequeued 10
Queue: [ _ , 20 , 30 , 40 , 50 ]
Front: 1
Rear: 4

Enqueue 60:
Queue: [ 60 , 20 , 30 , 40 , 50 ]
Front: 1
Rear: 0

Final Dequeue:
Dequeued 20
Dequeued 30
Dequeued 40
Dequeued 50
Dequeued 60
Queue: [ _ , _ , _ , _ , _ ]
Front: -1
Rear: -1

5. Queue Reversal

#include <stdio.h>
#include <stdbool.h>

#define MAX 5

typedef struct {
    int items[MAX];
    int front;
    int rear;
} Queue;

void initializeQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

bool isEmpty(Queue *q) {
    return q->front == -1;
}

void enqueue(Queue *q, int value) {
    if ((q->rear + 1) % MAX == q->front) {
        printf("Queue is full\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear = (q->rear + 1) % MAX;
    q->items[q->rear] = value;
    printf("Inserted %d\n", value);
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int item = q->items[q->front];
    if (q->front == q->rear) {
        initializeQueue(q); // Reset the queue if it's empty after dequeue
    } else {
        q->front = (q->front + 1) % MAX;
    }
    return item;
}

void reverseQueue(Queue *q) {
    if (isEmpty(q)) {
        return;
    }
    int temp[MAX];
    int i = 0;
    while (!isEmpty(q)) {
        temp[i++] = dequeue(q);
    }
    for (int j = i - 1; j >= 0; j--) {
        enqueue(q, temp[j]);
    }
}

void printQueue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return;
    }
    printf("Queue elements: ");
    int i = q->front;
    while (true) {
        printf("%d ", q->items[i]);
        if (i == q->rear) break;
        i = (i + 1) % MAX;
    }
    printf("\n");
}

int main() {
    Queue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    enqueue(&q, 40);
    enqueue(&q, 50);

    printQueue(&q);

    reverseQueue(&q);

    printQueue(&q);

    return 0;
}

Explanation with Example:

1. Initialize an empty queue.

2. Enqueue elements: 10, 20, 30, 40, 50.

3. Print the queue.

4. Reverse the queue elements.

5. Print the reversed queue.

Initial State:
Queue: [ _ , _ , _ , _ , _ ]
Front: -1
Rear: -1

Enqueue 10:
Queue: [ 10 , _ , _ , _ , _ ]
Front: 0
Rear: 0

Enqueue 20:
Queue: [ 10 , 20 , _ , _ , _ ]
Front: 0
Rear: 1

Enqueue 30:
Queue: [ 10 , 20 , 30 , _ , _ ]
Front: 0
Rear: 2

Enqueue 40:
Queue: [ 10 , 20 , 30 , 40 , _ ]
Front: 0
Rear: 3

Enqueue 50:
Queue: [ 10 , 20 , 30 , 40 , 50 ]
Front: 0
Rear: 4

Print Queue:
Queue elements: 10 20 30 40 50

Reverse Queue:
Queue: [ 50 , 40 , 30 , 20 , 10 ]
Front: 0
Rear: 4

Print Queue:
Queue elements: 50 40 30 20 10

Intermediate Level

1. Queue Using Linked List

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

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

// Queue structure
typedef struct {
    Node* front;
    Node* rear;
} Queue;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to initialize the queue
void initializeQueue(Queue* q) {
    q->front = q->rear = NULL;
}

// Function to check if the queue is empty
bool isEmpty(Queue* q) {
    return q->front == NULL;
}

// Function to add an element to the queue (enqueue)
void enqueue(Queue* q, int data) {
    Node* newNode = createNode(data);
    if (!newNode) return;

    if (isEmpty(q)) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
    printf("Inserted %d\n", data);
}

// Function to remove an element from the queue (dequeue)
int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    Node* temp = q->front;
    int data = temp->data;
    q->front = q->front->next;

    if (q->front == NULL) {
        q->

rear = NULL;
    }
    free(temp);
    return data;
}

// Function to get the front element of the queue
int peek(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    return q->front->data;
}

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

int main() {
    Queue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    displayQueue(&q);

    printf("Dequeued: %d\n", dequeue(&q));

    displayQueue(&q);

    printf("Front element is: %d\n", peek(&q));

    return 0;
}

Explanation with Example:

1. Initialize an empty queue using a linked list.

2. Enqueue elements: 10, 20, 30.

3. Display the queue elements.

4. Dequeue one element (10).

5. Display the queue elements again.

6. Peek at the front element.

Initial State:
Queue: NULL
Front: NULL
Rear: NULL

Enqueue 10:
Queue: 10 -> NULL
Front: 10
Rear: 10

Enqueue 20:
Queue: 10 -> 20 -> NULL
Front: 10
Rear: 20

Enqueue 30:
Queue: 10 -> 20 -> 30 -> NULL
Front: 10
Rear: 30

Display Queue:
Queue elements are: 10 20 30

Dequeue:
Dequeued: 10
Queue: 20 -> 30 -> NULL
Front: 20
Rear: 30

Display Queue:
Queue elements are: 20 30

Peek:
Front element is: 20

2. Generate Binary Numbers from 1 to N

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

typedef struct Node {
    char data[100];
    struct Node* next;
} Node;

typedef struct {
    Node* front;
    Node* rear;
} Queue;

Node* createNode(char* data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    strcpy(newNode->data, data);
    newNode->next = NULL;
    return newNode;
}

void initializeQueue(Queue* q) {
    q->front = q->rear = NULL;
}

int isEmpty(Queue* q) {
    return q->front == NULL;
}

void enqueue(Queue* q, char* data) {
    Node* newNode = createNode(data);
    if (!newNode) return;

    if (isEmpty(q)) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

char* dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return NULL;
    }
    Node* temp = q->front;
    char* data = temp->data;
    q->front = q->front->next;

    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return data;
}

void generateBinaryNumbers(int N) {
    Queue q;
    initializeQueue(&q);
    enqueue(&q, "1");

    for (int i = 1; i <= N; i++) {
        char* front = dequeue(&q);
        printf("%s\n", front);

        char next1[100], next2[100];
        strcpy(next1, front);
        strcat(next1, "0");
        strcpy(next2, front);
        strcat(next2, "1");

        enqueue(&q, next1);
        enqueue(&q, next2);
    }
}

int main() {
    int N = 10;
    printf("Binary numbers from 1 to %d are:\n", N);
    generateBinaryNumbers(N);

    return 0;
}

Explanation with Example:

1. Initialize an empty queue.

2. Enqueue the string "1".

3. For each number from 1 to N, dequeue the front, print it, and enqueue the numbers formed by appending "0" and "1" to the dequeued number.

Initial State:
Queue: NULL
Front: NULL
Rear: NULL

Enqueue "1":
Queue: "1" -> NULL
Front: "1"
Rear: "1"

Generate Binary Numbers:
Dequeue: "1"
Queue: NULL
Front: NULL
Rear: NULL
Print: 1
Enqueue "10":
Queue: "10" -> NULL
Front: "10"
Rear: "10"
Enqueue "11":
Queue: "10" -> "11" -> NULL
Front: "10"
Rear: "11"

Dequeue: "10"
Queue: "11" -> NULL
Front: "11"
Rear: "11"
Print: 10
Enqueue "100":
Queue: "11" -> "100" -> NULL
Front: "11"
Rear: "100"
Enqueue "101":
Queue: "11" -> "100" -> "101" -> NULL
Front: "11"
Rear: "101"

...

Final Output:
1
10
11
100
101
110
111
1000
1001
1010

3. Interleave the First Half of the Queue with the Second Half

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

#define MAX 5

typedef struct {
    int items[MAX];
    int front;
    int rear;
} Queue;

void initializeQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

int isEmpty(Queue *q) {
    return q->front == -1;
}

void enqueue(Queue *q, int value) {
    if ((q->rear + 1) % MAX == q->front) {
        printf("Queue is full\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear = (q->rear + 1) % MAX;
    q->items[q->rear] = value;
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int item = q->items[q->front];
    if (q->front == q->rear) {
        initializeQueue(q); // Reset the queue if it's empty after dequeue
    } else {
        q->front = (q->front + 1) % MAX;
    }
    return item;
}

void interleaveQueue(Queue *q) {
    if (isEmpty(q)) return;

    int halfSize = (q->rear - q->front + 1) / 2;
    Queue tempQueue;
    initializeQueue(&tempQueue);

    for (int i = 0; i < halfSize; i++) {
        enqueue(&tempQueue, dequeue(q));
    }

    while (!isEmpty(&tempQueue)) {
        enqueue(q, dequeue(&tempQueue));
        if (!isEmpty(q)) {
            enqueue(q, dequeue(q));
        }
    }
}

void printQueue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return;
    }
    printf("Queue elements: ");
    int i = q->front;
    while (true) {
        printf("%d ", q->items[i]);
        if (i == q->rear) break;
        i = (i + 1) % MAX;
    }
    printf("\n");
}

int main() {
    Queue q;
    initializeQueue(&q);

    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    enqueue(&q, 4);
    enqueue(&q, 5);

    printQueue(&q);

    interleaveQueue(&q);

    printQueue(&q);

    return 0;
}

Explanation with Example:

1. Initialize an empty queue.

2. Enqueue elements: 1, 2, 3, 4, 5.

3. Print the queue.

4. Interleave the first half of the queue with the second half.

5. Print the interleaved queue.

Initial State:
Queue: [ _ , _ , _ , _ , _ ]
Front: -1
Rear: -1

Enqueue 1:
Queue: [ 1 , _ , _ , _ , _ ]
Front: 0
Rear: 0

Enqueue 2:
Queue: [ 1 , 2 , _ , _ , _ ]
Front: 0
Rear: 1

Enqueue 3:
Queue: [ 1 , 2 , 3 , _ , _ ]
Front: 0
Rear: 2

Enqueue 4:
Queue: [ 1 , 2 , 3 , 4

 , _ ]
Front: 0
Rear: 3

Enqueue 5:
Queue: [ 1 , 2 , 3 , 4 , 5 ]
Front: 0
Rear: 4

Print Queue:
Queue elements: 1 2 3 4 5

Interleave Queue:
Queue: [ 1 , 4 , 2 , 5 , 3 ]
Front: 0
Rear: 4

Print Queue:
Queue elements: 1 4 2 5 3

4. Sum of Elements in Queue

#include <stdio.h>
#include <stdbool.h>

#define MAX 5

typedef struct {
    int items[MAX];
    int front;
    int rear;
} Queue;

void initializeQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

bool isEmpty(Queue *q) {
    return q->front == -1;
}

void enqueue(Queue *q, int value) {
    if ((q->rear + 1) % MAX == q->front) {
        printf("Queue is full\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear = (q->rear + 1) % MAX;
    q->items[q->rear] = value;
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int item = q->items[q->front];
    if (q->front == q->rear) {
        initializeQueue(q); // Reset the queue if it's empty after dequeue
    } else {
        q->front = (q->front + 1) % MAX;
    }
    return item;
}

int sumQueue(Queue *q) {
    if (isEmpty(q)) {
        return 0;
    }
    int sum = 0;
    int i = q->front;
    while (true) {
        sum += q->items[i];
        if (i == q->rear) break;
        i = (i + 1) % MAX;
    }
    return sum;
}

void printQueue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return;
    }
    printf("Queue elements: ");
    int i = q->front;
    while (true) {
        printf("%d ", q->items[i]);
        if (i == q->rear) break;
        i = (i + 1) % MAX;
    }
    printf("\n");
}

int main() {
    Queue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    enqueue(&q, 40);
    enqueue(&q, 50);

    printQueue(&q);

    printf("Sum of queue elements: %d\n", sumQueue(&q));

    return 0;
}

Explanation with Example:

1. Initialize an empty queue.

2. Enqueue elements: 10, 20, 30, 40, 50.

3. Print the queue.

4. Calculate and print the sum of the elements in the queue.

Initial State:
Queue: [ _ , _ , _ , _ , _ ]
Front: -1
Rear: -1

Enqueue 10:
Queue: [ 10 , _ , _ , _ , _ ]
Front: 0
Rear: 0

Enqueue 20:
Queue: [ 10 , 20 , _ , _ , _ ]
Front: 0
Rear: 1

Enqueue 30:
Queue: [ 10 , 20 , 30 , _ , _ ]
Front: 0
Rear: 2

Enqueue 40:
Queue: [ 10 , 20 , 30 , 40 , _ ]
Front: 0
Rear: 3

Enqueue 50:
Queue: [ 10 , 20 , 30 , 40 , 50 ]
Front: 0
Rear: 4

Print Queue:
Queue elements: 10 20 30 40 50

Sum of Queue:
Sum of queue elements: 150

5. Merge Two Queues

#include <stdio.h>
#include <stdbool.h>

#define MAX 5

typedef struct {
    int items[MAX];
    int front;
    int rear;
} Queue;

void initializeQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

bool isEmpty(Queue *q) {
    return q->front == -1;
}

void enqueue(Queue *q, int value) {
    if ((q->rear + 1) % MAX == q->front) {
        printf("Queue is full\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear = (q->rear + 1) % MAX;
    q->items[q->rear] = value;
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int item = q->items[q->front];
    if (q->front == q->rear) {
        initializeQueue(q); // Reset the queue if it's empty after dequeue
    } else {
        q->front = (q->front + 1) % MAX;
    }
    return item;
}

void mergeQueues(Queue *q1, Queue *q2, Queue *mergedQueue) {
    while (!isEmpty(q1)) {
        enqueue(mergedQueue, dequeue(q1));
    }
    while (!isEmpty(q2)) {
        enqueue(mergedQueue, dequeue(q2));
    }
}

void printQueue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return;
    }
    printf("Queue elements: ");
    int i = q->front;
    while (true) {
        printf("%d ", q->items[i]);
        if (i == q->rear) break;
        i = (i + 1) % MAX;
    }
    printf("\n");
}

int main() {
    Queue q1, q2, mergedQueue;
    initializeQueue(&q1);
    initializeQueue(&q2);
    initializeQueue(&mergedQueue);

    enqueue(&q1, 10);
    enqueue(&q1, 20);
    enqueue(&q2, 30);
    enqueue(&q2, 40);

    printf("Queue 1:\n");
    printQueue(&q1);
    printf("Queue 2:\n");
    printQueue(&q2);

    mergeQueues(&q1, &q2, &mergedQueue);

    printf("Merged Queue:\n");
    printQueue(&mergedQueue);

    return 0;
}

Explanation with Example:

1. Initialize two empty queues and one empty merged queue.

2. Enqueue elements: 10, 20 in the first queue, and 30, 40 in the second queue.

3. Print both queues.

4. Merge the two queues into the merged queue.

5. Print the merged queue.

Initial State:
Queue 1: [ _ , _ , _ , _ , _ ]
Queue 2: [ _ , _ , _ , _ , _ ]
Merged Queue: [ _ , _ , _ , _ , _ ]

Enqueue 10 in Queue 1:
Queue 1: [ 10 , _ , _ , _ , _ ]
Front: 0
Rear: 0

Enqueue 20 in Queue 1:
Queue 1: [ 10 , 20 , _ , _ , _ ]
Front: 0
Rear: 1

Enqueue 30 in Queue 2:
Queue 2: [ 30 , _ , _ , _ , _ ]
Front: 0
Rear: 0

Enqueue 40 in Queue 2:
Queue 2: [ 30 , 40 , _ , _ , _ ]
Front: 0
Rear: 1

Print Queues:
Queue 1 elements: 10 20
Queue 2 elements: 30 40

Merge Queues:
Merged Queue: [ 10 , 20 , 30 , 40 , _ ]
Front: 0
Rear: 3

Print Merged Queue:
Merged Queue elements: 10 20 30 40

Advanced Level

1. Design a Circular Deque

#include <stdio.h>
#include <stdbool.h>

#define MAX 5

typedef struct {
    int items[MAX];
    int front;
    int rear;
    int size;
} Deque;

void initializeDeque(Deque* dq) {
    dq->front = -1;
    dq->rear = 0;
    dq->size = 0;
}

bool isFull(Deque* dq) {
    return dq->size == MAX;
}

bool isEmpty(Deque* dq) {
    return dq->size == 0;
}

void insertFront(Deque* dq, int value) {
    if (isFull(dq)) {
        printf("Deque is full\n");
        return;
    }
    if (isEmpty(dq)) {
        dq->front = 0;
        dq->rear = 0;
    } else if (dq->front == 0) {


 dq->front = MAX - 1;
    } else {
        dq->front = dq->front - 1;
    }
    dq->items[dq->front] = value;
    dq->size++;
    printf("Inserted %d at front\n", value);
}

void insertRear(Deque* dq, int value) {
    if (isFull(dq)) {
        printf("Deque is full\n");
        return;
    }
    if (isEmpty(dq)) {
        dq->front = 0;
        dq->rear = 0;
    } else if (dq->rear == MAX - 1) {
        dq->rear = 0;
    } else {
        dq->rear = dq->rear + 1;
    }
    dq->items[dq->rear] = value;
    dq->size++;
    printf("Inserted %d at rear\n", value);
}

int deleteFront(Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return -1;
    }
    int data = dq->items[dq->front];
    if (dq->front == dq->rear) {
        initializeDeque(dq); // Reset the deque if it's empty after deletion
    } else if (dq->front == MAX - 1) {
        dq->front = 0;
    } else {
        dq->front = dq->front + 1;
    }
    dq->size--;
    printf("Deleted %d from front\n", data);
    return data;
}

int deleteRear(Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return -1;
    }
    int data = dq->items[dq->rear];
    if (dq->front == dq->rear) {
        initializeDeque(dq); // Reset the deque if it's empty after deletion
    } else if (dq->rear == 0) {
        dq->rear = MAX - 1;
    } else {
        dq->rear = dq->rear - 1;
    }
    dq->size--;
    printf("Deleted %d from rear\n", data);
    return data;
}

int getFront(Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return -1;
    }
    return dq->items[dq->front];
}

int getRear(Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return -1;
    }
    return dq->items[dq->rear];
}

void printDeque(Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return;
    }
    printf("Deque elements: ");
    int i = dq->front;
    while (true) {
        printf("%d ", dq->items[i]);
        if (i == dq->rear) break;
        i = (i + 1) % MAX;
    }
    printf("\n");
}

int main() {
    Deque dq;
    initializeDeque(&dq);

    insertRear(&dq, 10);
    insertRear(&dq, 20);
    insertFront(&dq, 5);
    insertRear(&dq, 30);

    printDeque(&dq);

    printf("Deleted from front: %d\n", deleteFront(&dq));
    printf("Deleted from rear: %d\n", deleteRear(&dq));

    printDeque(&dq);

    printf("Front element: %d\n", getFront(&dq));
    printf("Rear element: %d\n", getRear(&dq));

    return 0;
}

Explanation with Example:

1. Initialize an empty circular deque.

2. Insert elements at the rear and front: 10, 20 at the rear, and 5 at the front.

3. Print the deque elements.

4. Delete one element from the front (5) and one from the rear (30).

5. Print the deque elements again.

6. Get and print the front and rear elements.

Initial State:
Deque: [ _ , _ , _ , _ , _ ]
Front: -1
Rear: 0

Insert 10 at rear:
Deque: [ 10 , _ , _ , _ , _ ]
Front: 0
Rear: 0

Insert 20 at rear:
Deque: [ 10 , 20 , _ , _ , _ ]
Front: 0
Rear: 1

Insert 5 at front:
Deque: [ 10 , 20 , _ , _ , 5 ]
Front: 4
Rear: 1

Insert 30 at rear:
Deque: [ 10 , 20 , 30 , _ , 5 ]
Front: 4
Rear: 2

Print Deque:
Deque elements: 5 10 20 30

Delete from front:
Deleted from front: 5
Deque: [ 10 , 20 , 30 , _ , _ ]
Front: 0
Rear: 2

Delete from rear:
Deleted from rear: 30
Deque: [ 10 , 20 , _ , _ , _ ]
Front: 0
Rear: 1

Print Deque:
Deque elements: 10 20

Front element:
Front element: 10

Rear element:
Rear element: 20

2. Sliding Window Maximum

#include <stdio.h>

#define MAX 100

typedef struct {
    int items[MAX];
    int front;
    int rear;
} Deque;

void initializeDeque(Deque* dq) {
    dq->front = -1;
    dq->rear = -1;
}

int isEmpty(Deque* dq) {
    return dq->front == -1;
}

int isFull(Deque* dq) {
    return (dq->rear + 1) % MAX == dq->front;
}

void insertRear(Deque* dq, int value) {
    if (isFull(dq)) {
        return;
    }
    if (isEmpty(dq)) {
        dq->front = 0;
        dq->rear = 0;
    } else {
        dq->rear = (dq->rear + 1) % MAX;
    }
    dq->items[dq->rear] = value;
}

void deleteFront(Deque* dq) {
    if (isEmpty(dq)) {
        return;
    }
    if (dq->front == dq->rear) {
        initializeDeque(dq);
    } else {
        dq->front = (dq->front + 1) % MAX;
    }
}

void deleteRear(Deque* dq) {
    if (isEmpty(dq)) {
        return;
    }
    if (dq->front == dq->rear) {
        initializeDeque(dq);
    } else {
        dq->rear = (dq->rear - 1 + MAX) % MAX;
    }
}

int getFront(Deque* dq) {
    if (isEmpty(dq)) {
        return -1;
    }
    return dq->items[dq->front];
}

int getRear(Deque* dq) {
    if (isEmpty(dq)) {
        return -1;
    }
    return dq->items[dq->rear];
}

void slidingWindowMaximum(int arr[], int n, int k) {
    Deque dq;
    initializeDeque(&dq);

    for (int i = 0; i < k; i++) {
        while (!isEmpty(&dq) && arr[i] >= arr[getRear(&dq)]) {
            deleteRear(&dq);
        }
        insertRear(&dq, i);
    }

    for (int i = k; i < n; i++) {
        printf("%d ", arr[getFront(&dq)]);

        while (!isEmpty(&dq) && getFront(&dq) <= i - k) {
            deleteFront(&dq);
        }

        while (!isEmpty(&dq) && arr[i] >= arr[getRear(&dq)]) {
            deleteRear(&dq);
        }

        insertRear(&dq, i);
    }

    printf("%d\n", arr[getFront(&dq)]);
}

int main() {
    int arr[] = {1, 3, -1, -3, 5, 3, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    slidingWindowMaximum(arr, n, k);

    return 0;
}

Explanation with Example:

1. Initialize an empty deque.

2. For the first window, insert indices of elements into the deque while maintaining decreasing order.

3. For each subsequent element, print the front of the deque (maximum of the current window), remove elements not in the current window, and insert the current element's index.

4. Print the maximum for the final window.

Array: [1, 3, -1, -3, 5, 3, 6, 7]
k = 3

Initial Window:
Insert 0 (1): [0]
Insert 1 (3): [1]
Insert 2 (-1): [1, 2]

Sliding Window:
Window [0, 1, 2]: Max = 3

Remove 0: [1, 2]
Insert 3 (-3): [1, 2, 3]
Window [1, 2, 3]: Max = 3

Remove 1: [2, 3]
Insert 4 (5): [4]
Window [2, 3, 4]: Max = 5

Insert 5 (3): [4

, 5]
Window [3, 4, 5]: Max = 5

Insert 6 (6): [6]
Window [4, 5, 6]: Max = 6

Insert 7 (7): [7]
Window [5, 6, 7]: Max = 7

3. First Non-Repeating Character in a Stream

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

#define MAX 256

typedef struct Node {
    char data;
    struct Node* next;
} Node;

typedef struct {
    Node* front;
    Node* rear;
} Queue;

Node* createNode(char data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void initializeQueue(Queue* q) {
    q->front = q->rear = NULL;
}

int isEmpty(Queue* q) {
    return q->front == NULL;
}

void enqueue(Queue* q, char data) {
    Node* newNode = createNode(data);
    if (!newNode) return;

    if (isEmpty(q)) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

char dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return '\0';
    }
    Node* temp = q->front;
    char data = temp->data;
    q->front = q->front->next;

    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return data;
}

void firstNonRepeating(char* stream) {
    int freq[MAX] = {0};
    Queue q;
    initializeQueue(&q);

    for (int i = 0; stream[i] != '\0'; i++) {
        char ch = stream[i];
        enqueue(&q, ch);
        freq[ch]++;

        while (!isEmpty(&q) && freq[q.front->data] > 1) {
            dequeue(&q);
        }

        if (isEmpty(&q)) {
            printf("# ");
        } else {
            printf("%c ", q.front->data);
        }
    }
    printf("\n");
}

int main() {
    char stream[] = "aabc";
    firstNonRepeating(stream);

    return 0;
}

Explanation with Example:

1. Initialize a frequency array and an empty queue.

2. For each character in the stream, enqueue it and update its frequency.

3. Dequeue characters from the front while their frequency is greater than 1.

4. Print the front character (first non-repeating) or '#' if the queue is empty.

Stream: "aabc"

Initial State:
Queue: NULL
Front: NULL
Rear: NULL
Freq: [0, 0, 0, ...]

Insert 'a':
Queue: 'a' -> NULL
Front: 'a'
Rear: 'a'
Freq: [1, 0, 0, ...]

Print: a

Insert 'a':
Queue: 'a' -> 'a' -> NULL
Front: 'a'
Rear: 'a'
Freq: [2, 0, 0, ...]

Dequeue 'a':
Queue: 'a' -> NULL
Front: 'a'
Rear: 'a'

Dequeue 'a':
Queue: NULL
Front: NULL
Rear: NULL

Print: #

Insert 'b':
Queue: 'b' -> NULL
Front: 'b'
Rear: 'b'
Freq: [2, 1, 0, ...]

Print: b

Insert 'c':
Queue: 'b' -> 'c' -> NULL
Front: 'b'
Rear: 'c'
Freq: [2, 1, 1, ...]

Print: b

Output: a # b b

4. Reverse First k Elements of Queue

#include <stdio.h>
#include <stdbool.h>

#define MAX 5

typedef struct {
    int items[MAX];
    int front;
    int rear;
} Queue;

void initializeQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

bool isEmpty(Queue *q) {
    return q->front == -1;
}

void enqueue(Queue *q, int value) {
    if ((q->rear + 1) % MAX == q->front) {
        printf("Queue is full\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear = (q->rear + 1) % MAX;
    q->items[q->rear] = value;
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int item = q->items[q->front];
    if (q->front == q->rear) {
        initializeQueue(q); // Reset the queue if it's empty after dequeue
    } else {
        q->front = (q->front + 1) % MAX;
    }
    return item;
}

void reverseQueue(Queue *q, int k) {
    if (isEmpty(q) || k > q->rear - q->front + 1) {
        return;
    }
    int temp[MAX];
    int i;
    for (i = 0; i < k; i++) {
        temp[i] = dequeue(q);
    }
    for (int j = i - 1; j >= 0; j--) {
        enqueue(q, temp[j]);
    }
    for (int j = k; j < q->rear - q->front + 1 + k; j++) {
        enqueue(q, dequeue(q));
    }
}

void printQueue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return;
    }
    printf("Queue elements: ");
    int i = q->front;
    while (true) {
        printf("%d ", q->items[i]);
        if (i == q->rear) break;
        i = (i + 1) % MAX;
    }
    printf("\n");
}

int main() {
    Queue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    enqueue(&q, 40);
    enqueue(&q, 50);

    printQueue(&q);

    reverseQueue(&q, 3);

    printQueue(&q);

    return 0;
}

Explanation with Example:

1. Initialize an empty queue.

2. Enqueue elements: 10, 20, 30, 40, 50.

3. Print the queue.

4. Reverse the first k elements of the queue.

5. Print the reversed queue.

Initial State:
Queue: [ _ , _ , _ , _ , _ ]
Front: -1
Rear: -1

Enqueue 10:
Queue: [ 10 , _ , _ , _ , _ ]
Front: 0
Rear: 0

Enqueue 20:
Queue: [ 10 , 20 , _ , _ , _ ]
Front: 0
Rear: 1

Enqueue 30:
Queue: [ 10 , 20 , 30 , _ , _ ]
Front: 0
Rear: 2

Enqueue 40:
Queue: [ 10 , 20 , 30 , 40 , _ ]
Front: 0
Rear: 3

Enqueue 50:
Queue: [ 10 , 20 , 30 , 40 , 50 ]
Front: 0
Rear: 4

Print Queue:
Queue elements: 10 20 30 40 50

Reverse First 3 Elements:
Dequeue 10, 20, 30 -> Temp: [10, 20, 30]
Enqueue 30, 20, 10 -> Queue: [30, 20, 10, 40, 50]
Reorder remaining -> Queue: [30, 20, 10, 40, 50]

Print Queue:
Queue elements: 30 20 10 40 50

5. Sum of Minimum and Maximum Elements of All Subarrays of Size k

#include <stdio.h>

#define MAX 100

typedef struct {
    int items[MAX];
    int front;
    int rear;
} Deque;

void initializeDeque(Deque* dq) {
    dq->front = -1;
    dq->rear = -1;
}

int isEmpty(Deque* dq) {
    return dq->front == -1;
}

int isFull(Deque* dq) {
    return (dq->rear + 1) % MAX == dq->front;
}

void insertRear(Deque* dq, int value) {
    if (isFull(dq)) {
        return;
    }
    if (isEmpty(dq)) {
        dq->front = 0;
        dq->rear = 0;
    } else {
        dq->rear = (dq->rear + 1) % MAX;
    }
    dq->items[dq->rear] = value;
}

void deleteFront(Deque*

 dq) {
    if (isEmpty(dq)) {
        return;
    }
    if (dq->front == dq->rear) {
        initializeDeque(dq);
    } else {
        dq->front = (dq->front + 1) % MAX;
    }
}

void deleteRear(Deque* dq) {
    if (isEmpty(dq)) {
        return;
    }
    if (dq->front == dq->rear) {
        initializeDeque(dq);
    } else {
        dq->rear = (dq->rear - 1 + MAX) % MAX;
    }
}

int getFront(Deque* dq) {
    if (isEmpty(dq)) {
        return -1;
    }
    return dq->items[dq->front];
}

int getRear(Deque* dq) {
    if (isEmpty(dq)) {
        return -1;
    }
    return dq->items[dq->rear];
}

int sumOfMinAndMax(int arr[], int n, int k) {
    Deque minDq, maxDq;
    initializeDeque(&minDq);
    initializeDeque(&maxDq);
    int sum = 0;

    for (int i = 0; i < k; i++) {
        while (!isEmpty(&minDq) && arr[i] <= arr[getRear(&minDq)]) {
            deleteRear(&minDq);
        }
        while (!isEmpty(&maxDq) && arr[i] >= arr[getRear(&maxDq)]) {
            deleteRear(&maxDq);
        }
        insertRear(&minDq, i);
        insertRear(&maxDq, i);
    }

    for (int i = k; i < n; i++) {
        sum += arr[getFront(&minDq)] + arr[getFront(&maxDq)];

        while (!isEmpty(&minDq) && getFront(&minDq) <= i - k) {
            deleteFront(&minDq);
        }
        while (!isEmpty(&maxDq) && getFront(&maxDq) <= i - k) {
            deleteFront(&maxDq);
        }

        while (!isEmpty(&minDq) && arr[i] <= arr[getRear(&minDq)]) {
            deleteRear(&minDq);
        }
        while (!isEmpty(&maxDq) && arr[i] >= arr[getRear(&maxDq)]) {
            deleteRear(&maxDq);
        }

        insertRear(&minDq, i);
        insertRear(&maxDq, i);
    }

    sum += arr[getFront(&minDq)] + arr[getFront(&maxDq)];
    return sum;
}

int main() {
    int arr[] = {2, 5, -1, 7, -3, -1, -2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    int result = sumOfMinAndMax(arr, n, k);
    printf("Sum of minimum and maximum elements of all subarrays of size %d is: %d\n", k, result);

    return 0;
}

Explanation with Example:

1. Initialize two empty deques for tracking minimum and maximum values.

2. For each subarray of size k, maintain the deques such that the front of the min deque has the minimum element and the front of the max deque has the maximum element.

3. Sum the minimum and maximum values for each subarray.

4. Print the total sum.

Array: [2, 5, -1, 7, -3, -1, -2]
k = 3

Initial Window:
MinDeque: [2]
MaxDeque: [2]

Insert 5:
MinDeque: [2, 5]
MaxDeque: [5]

Insert -1:
MinDeque: [-1]
MaxDeque: [5, -1]

Sliding Window:
Window [0, 1, 2]: Min = -1, Max = 5, Sum = 4

Remove 2:
MinDeque: [-1]
MaxDeque: [5, -1]

Insert 7:
MinDeque: [-1, 7]
MaxDeque: [7]

Window [1, 2, 3]: Min = -1, Max = 7, Sum = 6

...

Final Output:
Sum of minimum and maximum elements of all subarrays of size 3 is: 18

Expert Level

1. Task Scheduling with Cooldown

#include <stdio.h>
#include <stdbool.h>

#define MAX 26

typedef struct {
    int items[MAX];
    int front;
    int rear;
    int size;
} Queue;

void initializeQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
    q->size = 0;
}

bool isEmpty(Queue *q) {
    return q->front == -1;
}

bool isFull(Queue *q) {
    return q->size == MAX;
}

void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
        q->rear = 0;
    } else {
        q->rear = (q->rear + 1) % MAX;
    }
    q->items[q->rear] = value;
    q->size++;
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int item = q->items[q->front];
    if (q->front == q->rear) {
        initializeQueue(q); // Reset the queue if it's empty after dequeue
    } else {
        q->front = (q->front + 1) % MAX;
    }
    q->size--;
    return item;
}

void taskScheduler(char tasks[], int n, int cooldown) {
    int freq[MAX] = {0};
    for (int i = 0; i < n; i++) {
        freq[tasks[i] - 'A']++;
    }

    Queue q;
    initializeQueue(&q);
    int time = 0;

    while (true) {
        int maxFreq = 0;
        int maxTask = -1;
        for (int i = 0; i < MAX; i++) {
            if (freq[i] > maxFreq) {
                maxFreq = freq[i];
                maxTask = i;
            }
        }

        if (maxTask == -1) {
            break;
        }

        time++;
        freq[maxTask]--;

        enqueue(&q, maxTask);
        if (q.size > cooldown) {
            int cooledTask = dequeue(&q);
            if (cooledTask != -1 && freq[cooledTask] > 0) {
                enqueue(&q, cooledTask);
            }
        }
    }

    printf("Minimum time required to complete all tasks: %d\n", time);
}

int main() {
    char tasks[] = {'A', 'A', 'A', 'B', 'B', 'B'};
    int n = sizeof(tasks) / sizeof(tasks[0]);
    int cooldown = 2;

    taskScheduler(tasks, n, cooldown);

    return 0;
}

Explanation with Example:

1. Initialize a frequency array and an empty queue.

2. For each task, update its frequency.

3. Use a queue to manage the cooldown period and track tasks that can be scheduled next.

4. Dequeue tasks from the queue if they have cooled down and can be scheduled again.

5. Print the minimum time required to complete all tasks.

Tasks: ['A', 'A', 'A', 'B', 'B', 'B']
Cooldown: 2

Initial State:
Freq: [3, 3, 0, ..., 0]
Queue: NULL
Time: 0

Schedule 'A':
Freq: [2, 3, 0, ..., 0]
Queue: 'A' -> NULL
Time: 1

Schedule 'B':
Freq: [2, 2, 0, ..., 0]
Queue: 'A' -> 'B' -> NULL
Time: 2

Schedule 'A':
Freq: [1, 2, 0, ..., 0]
Queue: 'A' -> 'B' -> 'A' -> NULL
Time: 3

Dequeue 'A':
Queue: 'B' -> 'A' -> NULL

Schedule 'B':
Freq: [1, 1, 0, ..., 0]
Queue: 'B' -> 'A' -> 'B' -> NULL
Time: 4

Dequeue 'B':
Queue: 'A' -> 'B' -> NULL

...

Final Output:
Minimum time required to complete all tasks: 7

2. Circular Tour Problem

#include <stdio.h>

typedef struct {
    int petrol;
    int distance;
} PetrolPump;

int circularTour(PetrolPump pumps[], int n) {
    int start = 0;
    int end = 1;
    int currPetrol = pumps[start].petrol - pumps[start].distance;

    while (end != start || currPetrol < 0) {
        while (currPetrol < 0 && start != end) {
            currPetrol -= pumps[start].petrol - pumps[start].distance;
            start = (start + 1) % n;

            if (start == 0) {
                return -1;
            }
        }

        currPetrol += pumps[end].petrol - pumps[end].distance;
        end = (end + 1) % n;
    }

    return start;
}

int main() {
    PetrolPump pumps[] = {{4, 6}, {6, 5}, {7, 3}, {4, 5}};
    int n = sizeof(pumps) / sizeof(pumps[0]);

    int start = circularTour(pumps, n);

    if (start == -1) {
        printf("No solution\n");
    } else {
        printf("Start at petrol pump %d\n", start);
    }

    return 0;
}

Explanation with Example:

1. Initialize the start and end indices and the current petrol balance.

2. Loop through the petrol pumps, adjusting the start index and current petrol balance when the balance is negative.

3. Continue until the tour is completed or it is determined that no solution exists.

4. Print the starting petrol pump index or "No solution".

Petrol Pumps: [{4, 6}, {6, 5}, {7, 3}, {4, 5}]
n = 4

Initial State:
Start: 0
End: 1
CurrPetrol: -2

Move Start to 1:
Start: 1
CurrPetrol: 0

Move End to 2:
End: 2
CurrPetrol: 4

Move End to 3:
End: 3
CurrPetrol: 5

Move End to 0:
End: 0
CurrPetrol: 4

Move End to 1:
End: 1
CurrPetrol: 3

Final Output:
Start at petrol pump 1

3. Check for Palindrome using Queue

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

#define MAX 100

typedef struct Node {
    char data;
    struct Node* next;
} Node;

typedef struct {
    Node* front;
    Node* rear;
} Queue;

Node* createNode(char data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void initializeQueue(Queue* q) {
    q->front = q->rear = NULL;
}

int isEmpty(Queue* q) {
    return q->front == NULL;
}

void enqueue(Queue* q, char data) {
    Node* newNode = createNode(data);
    if (!newNode) return;

    if (isEmpty(q)) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

char dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return '\0';
    }
    Node* temp = q->front;
    char data = temp->data;
    q->front = q->front->next;

    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return data;
}

int isPalindrome(char* str) {
    int n = strlen(str);
    Queue q;
    initializeQueue(&q);

    for (int i = 0; i < n; i++) {
        enqueue(&q, str[i]);
    }

    for (int i = 0; i < n / 2; i++) {
        if (str[i] != dequeue(&q)) {
            return 0;
        }
    }

    return 1;
}

int main() {
    char str[] = "racecar";

    if (isPalindrome(str)) {
        printf("The string is a palindrome\n");
    } else {
        printf("The string is not a palindrome\n");
    }

    return 0;
}

Explanation with Example:

1. Initialize an empty queue.

2. Enqueue all characters of the string into the queue.

3. Dequeue characters and compare them with the original string in reverse order.

4. Print whether the string is a palindrome or not.

String: "racecar"
n = 7

Initial State:
Queue: NULL
Front: NULL
Rear: NULL

Enqueue 'r':
Queue: 'r' -> NULL
Front: 'r'
Rear: 'r'

Enqueue 'a':
Queue: 'r' -> 'a' -> NULL
Front: 'r'
Rear: 'a'

Enqueue 'c':
Queue: 'r' -> 'a' -> 'c' -> NULL
Front: 'r'
Rear: 'c'

Enqueue 'e':
Queue: 'r' -> 'a' -> 'c' -> 'e' -> NULL
Front: 'r'
Rear: 'e'

...

Check Palindrome:
Dequeue 'r', compare with 'r' -> Match
Dequeue 'a', compare with 'a' -> Match
Dequeue 'c', compare with 'c' -> Match

Final Output:
The string is a palindrome

4. Distance of Nearest Cell Having 1 in a Binary Matrix

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

#define ROW 3
#define COL 3

typedef struct {
    int x, y;
} Point;

typedef struct {
    Point point;
    int distance;
} QueueNode;

typedef struct {
    QueueNode *array;
    int front, rear, size;
    unsigned capacity;
} Queue;

Queue* createQueue(unsigned capacity) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->capacity = capacity;
    queue->front = queue->size = 0;
    queue->rear = capacity - 1;
    queue->array = (QueueNode*)malloc(queue->capacity * sizeof(QueueNode));
    return queue;
}

int isFull(Queue* queue) {
    return (queue->size == queue->capacity);
}

int isEmpty(Queue* queue) {
    return (queue->size == 0);
}

void enqueue(Queue* queue, Point point, int distance) {
    if (isFull(queue))
        return;
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->array[queue->rear].point = point;
    queue->array[queue->rear].distance = distance;
    queue->size = queue->size + 1;
}

QueueNode dequeue(Queue* queue) {
    QueueNode node = {{-1, -1}, -1};
    if (isEmpty(queue))
        return node;
    node = queue->array[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size = queue->size - 1;
    return node;
}

int isValid(int row, int col) {
    return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL);
}

int rowNum[] = {-1, 0, 0, 1};
int colNum[] = {0, -1, 1, 0};

void printMatrix(int mat[ROW][COL]) {
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            printf("%d ", mat[i][j]);
        }
        printf("\n");
    }
}

void findNearestCell(int mat[ROW][COL]) {
    int result[ROW][COL];
    int visited[ROW][COL];

    Queue* queue = createQueue(ROW * COL);

    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            result[i][j] = -1;
            visited[i][j] = 0;
            if (mat[i][j] == 1) {
                enqueue(queue, (Point){i, j}, 0);
                visited[i][j] = 1;
            }
        }
    }

    while (!isEmpty(queue)) {
        QueueNode curr = dequeue(queue);

        for (int i = 0; i < 4; i++) {
            int row = curr.point.x + rowNum[i];
            int col = curr.point.y + colNum[i];

            if (isValid(row, col) && !visited[row][col]) {
                visited[row][col] = 1;
                result[row][col] = curr.distance + 1;
                enqueue(queue, (Point){row, col}, curr.distance + 1);
            }
        }
    }

    printMatrix(result);
}

int main() {
    int mat[ROW][COL] = {
        {0, 0, 0},
        {0, 1, 0},
        {0, 0, 0}
    };

    findNearestCell(mat);

    return 0;
}

Explanation with Example:

1. Initialize an empty queue and visited matrix.

2. Enqueue all cells containing 1 with distance 0 and mark them as visited.

3. For each dequeued cell, enqueue its unvisited neighbors with distance incremented by 1.

4. Print the result matrix containing distances to the nearest cell with 1.

Matrix: [[

0, 0, 0],
         [0, 1, 0],
         [0, 0, 0]]
ROW = 3, COL = 3

Initial State:
Queue: NULL
Visited: [[0, 0, 0],
          [0, 1, 0],
          [0, 0, 0]]

Enqueue (1, 1) with distance 0:
Queue: [(1, 1, 0)]
Visited: [[0, 0, 0],
          [0, 1, 0],
          [0, 0, 0]]

Process (1, 1):
Dequeue (1, 1, 0)
Enqueue (0, 1, 1), (1, 0, 1), (1, 2, 1), (2, 1, 1):
Queue: [(0, 1, 1), (1, 0, 1), (1, 2, 1), (2, 1, 1)]
Visited: [[0, 1, 0],
          [1, 1, 1],
          [0, 1, 0]]

...

Final Output:
[[2, 1, 2],
 [1, 0, 1],
 [2, 1, 2]]

5. Multiple Queues in a Single Array

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

#define MAX 10

typedef struct {
    int items[MAX];
    int front[2];
    int rear[2];
} MultipleQueues;

void initializeQueues(MultipleQueues* q) {
    q->front[0] = -1;
    q->rear[0] = -1;
    q->front[1] = MAX / 2 - 1;
    q->rear[1] = MAX / 2 - 1;
}

int isEmpty(int queueNum, MultipleQueues* q) {
    if (queueNum == 0) {
        return q->front[queueNum] == -1;
    } else {
        return q->front[queueNum] == MAX / 2 - 1;
    }
}

int isFull(int queueNum, MultipleQueues* q) {
    if (queueNum == 0) {
        return q->rear[queueNum] == MAX / 2 - 1;
    } else {
        return q->rear[queueNum] == MAX - 1;
    }
}

void enqueue(int queueNum, MultipleQueues* q, int value) {
    if (isFull(queueNum, q)) {
        printf("Queue %d is full\n", queueNum);
        return;
    }
    if (isEmpty(queueNum, q)) {
        if (queueNum == 0) {
            q->front[queueNum] = 0;
            q->rear[queueNum] = 0;
        } else {
            q->front[queueNum] = MAX / 2;
            q->rear[queueNum] = MAX / 2;
        }
    } else {
        q->rear[queueNum] = (q->rear[queueNum] + 1);
    }
    q->items[q->rear[queueNum]] = value;
    printf("Inserted %d into Queue %d\n", value, queueNum);
}

int dequeue(int queueNum, MultipleQueues* q) {
    if (isEmpty(queueNum, q)) {
        printf("Queue %d is empty\n", queueNum);
        return -1;
    }
    int item = q->items[q->front[queueNum]];
    if (q->front[queueNum] == q->rear[queueNum]) {
        initializeQueues(q); // Reset the queue if it's empty after dequeue
    } else {
        q->front[queueNum] = (q->front[queueNum] + 1);
    }
    return item;
}

void printQueue(int queueNum, MultipleQueues* q) {
    if (isEmpty(queueNum, q)) {
        printf("Queue %d is empty\n", queueNum);
        return;
    }
    printf("Queue %d elements: ", queueNum);
    int i = q->front[queueNum];
    while (true) {
        printf("%d ", q->items[i]);
        if (i == q->rear[queueNum]) break;
        i = (i + 1);
    }
    printf("\n");
}

int main() {
    MultipleQueues q;
    initializeQueues(&q);

    enqueue(0, &q, 10);
    enqueue(0, &q, 20);
    enqueue(1, &q, 30);
    enqueue(1, &q, 40);

    printQueue(0, &q);
    printQueue(1, &q);

    printf("Dequeued from Queue 0: %d\n", dequeue(0, &q));
    printf("Dequeued from Queue 1: %d\n", dequeue(1, &q));

    printQueue(0, &q);
    printQueue(1, &q);

    return 0;
}

Explanation with Example:

1. Initialize two queues within a single array, each using half of the array.

2. Enqueue elements: 10, 20 in the first queue, and 30, 40 in the second queue.

3. Print both queues.

4. Dequeue one element from each queue.

5. Print both queues again.

Initial State:
Queue 0: [ _ , _ , _ , _ , _ ]
Queue 1: [ _ , _ , _ , _ , _ ]
Front: -1, Rear: -1 for both queues

Enqueue 10 in Queue 0:
Queue 0: [ 10 , _ , _ , _ , _ ]
Front: 0, Rear: 0

Enqueue 20 in Queue 0:
Queue 0: [ 10 , 20 , _ , _ , _ ]
Front: 0, Rear: 1

Enqueue 30 in Queue 1:
Queue 1: [ _ , _ , _ , _ , _ , 30 , _ , _ , _ , _ ]
Front: 5, Rear: 5

Enqueue 40 in Queue 1:
Queue 1: [ _ , _ , _ , _ , _ , 30 , 40 , _ , _ , _ ]
Front: 5, Rear: 6

Print Queues:
Queue 0 elements: 10 20
Queue 1 elements: 30 40

Dequeue from Queue 0:
Dequeued from Queue 0: 10
Queue 0: [ 10 , 20 , _ , _ , _ ]
Front: 1, Rear: 1

Dequeue from Queue 1:
Dequeued from Queue 1: 30
Queue 1: [ _ , _ , _ , _ , _ , 30 , 40 , _ , _ , _ ]
Front: 6, Rear: 6

Print Queues:
Queue 0 elements: 20
Queue 1 elements: 40