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
Enqueue: Adding an element to the end (rear) of the queue.
Dequeue: Removing an element from the front of the queue.
Peek/Front: Accessing the front element of the queue without removing it.
isEmpty: Checking if the queue is empty.
isFull: Checking if the queue is full (in case of fixed-size implementations).
Types of Queues
Simple Queue (Linear Queue): The basic FIFO structure.
Circular Queue: Connects the end of the queue back to the front, forming a circle. This allows better utilization of storage.
Priority Queue: Each element has a priority, and elements with higher priority are dequeued before those with lower priority.
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
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.
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.
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.
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.
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
Operating Systems: Managing tasks, processes, and threads.
Network Routers: Handling data packets for transmission.
Printers: Managing print jobs.
Web Servers: Handling multiple client requests.
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
Initialization: The queue is initialized with
front
andrear
set to -1, indicating that the queue is empty.isFull and isEmpty: These functions are helper functions to check the state of the queue.
isFull
checks ifrear
has reached the maximum size, andisEmpty
checks if there are no elements in the queue.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 atitems[rear]
. If the queue was empty, it setsfront
to 0.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 thefront
index. If the queue becomes empty after the dequeue operation, it resets thefront
andrear
indices.Peek Operation: This function returns the element at the
front
of the queue without removing it.Display Function: This function iterates through the queue from
front
torear
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
Node Structure
- A
Node
structure is defined to represent each element in the queue. It contains an integerdata
to store the value and a pointernext
to point to the next node in the queue.
- A
Queue Structure
- A
Queue
structure is defined to manage the queue. It contains two pointers:front
to point to the front node andrear
to point to the rear node.
- A
createNode Function
- This function creates a new node with the given data, initializes its
next
pointer toNULL
, and returns the node. If memory allocation fails, it prints an error message and returnsNULL
.
- This function creates a new node with the given data, initializes its
initializeQueue Function
- This function initializes the queue by setting both
front
andrear
pointers toNULL
, indicating an empty queue.
- This function initializes the queue by setting both
isEmpty Function
- This function checks if the queue is empty by returning
true
iffront
isNULL
, otherwisefalse
.
- This function checks if the queue is empty by returning
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
andrear
to the new node. Otherwise, it sets thenext
pointer of the currentrear
node to the new node and updates therear
pointer to the new node.
- 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
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 thefront
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 setsrear
toNULL
.
- 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
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
.
- This function returns the data of the front node without removing it. If the queue is empty, it prints an error message and returns
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.
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
Deque Structure
- A
Deque
structure is defined with an arrayitems
to store elements, and three integers:front
to point to the front of the deque,rear
to point to the rear of the deque, andsize
to keep track of the number of elements.
- A
initializeDeque Function
- This function initializes the deque by setting
front
to -1,rear
to 0, andsize
to 0, indicating an empty deque.
- This function initializes the deque by setting
isFull Function
- This function checks if the deque is full by comparing
size
toMAX
.
- This function checks if the deque is full by comparing
isEmpty Function
- This function checks if the deque is empty by checking if
size
is 0.
- This function checks if the deque is empty by checking if
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
andrear
to 0. Iffront
is at the beginning of the array, it wraps around to the end. Otherwise, it decrementsfront
. The new element is then added toitems[front]
, andsize
is incremented.
- 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
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
andrear
to 0. Ifrear
is at the end of the array, it wraps around to the beginning. Otherwise, it incrementsrear
. The new element is then added toitems[rear]
, andsize
is incremented.
- 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
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
. Iffront
is the same asrear
, it sets bothfront
andrear
to -1, indicating an empty deque. Iffront
is at the end of the array, it wraps around to the beginning. Otherwise, it incrementsfront
. The removed element's data is stored and returned, andsize
is decremented.
- 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
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
. Iffront
is the same asrear
, it sets bothfront
andrear
to -1, indicating an empty deque. Ifrear
is at the beginning of the array, it wraps around to the end. Otherwise, it decrementsrear
. The removed element's data is stored and returned, andsize
is decremented.
- 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
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
.
- This function returns the data of the front element without removing it. If the deque is empty, it prints an error message and returns
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
.
- This function returns the data of the rear element without removing it. If the deque is empty, it prints an error message and returns
displayDeque Function
- This function prints all the elements in the deque from
front
torear
. It handles wrapping around the end of the array by using the modulo operator%
.
- This function prints all the elements in the deque from
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.
- The
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
Basic Queue Operations
- Implement a queue using an array. Perform basic operations: enqueue, dequeue, peek, and isEmpty.
Print Queue Elements
- Write a program to print all elements of a queue.
Queue Size
- Modify the queue implementation to include a function that returns the current size of the queue.
Circular Queue
- Implement a circular queue using an array. Handle wrap-around conditions properly.
Queue Reversal
- Write a function to reverse the elements of a queue.
Intermediate Level
Queue Using Linked List
- Implement a queue using a linked list. Perform basic operations: enqueue, dequeue, peek, and isEmpty.
Generate Binary Numbers from 1 to N
- Write a program that uses a queue to generate binary numbers from 1 to N.
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.
Sum of Elements in Queue
- Write a function to find the sum of all elements in a queue.
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
Design a Circular Deque
- Implement a circular deque using an array. Perform all basic operations: insertFront, insertRear, deleteFront, deleteRear, getFront, getRear, isEmpty, and isFull.
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.
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.
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.
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
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.
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.
Check for Palindrome using Queue
- Write a function to check if the given string is a palindrome using a queue.
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.
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
Basic Queue Operations
Approach: Use an array to implement a queue and maintain two pointers,
front
andrear
, to track the positions for dequeuing and enqueuing elements respectively. Theenqueue
operation adds elements to the position pointed byrear
and incrementsrear
. Thedequeue
operation removes elements from the position pointed byfront
and incrementsfront
. Thepeek
operation returns the element at thefront
without removing it. Check for an empty queue by verifying iffront
exceedsrear
, and for a full queue ifrear
exceeds the array size.Hints: Initialize
front
to 0 andrear
to -1. Incrementrear
when enqueuing and incrementfront
when dequeuing. Ensure to check for underflow and overflow conditions.
Print Queue Elements
Approach: Traverse the queue from
front
torear
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
torear
and print the elements. Ensure that the queue is not empty before starting the loop.
Queue Size
Approach: Maintain a variable
size
to keep track of the number of elements in the queue. Incrementsize
onenqueue
and decrementsize
ondequeue
. Create a function to return the value ofsize
.Hints: Initialize
size
to 0. Modify theenqueue
anddequeue
operations to updatesize
accordingly. The function to get the size simply returns thesize
variable.
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 theenqueue
anddequeue
operations to handle the wrap-around using the modulo operator.Hints: Use
(rear + 1) % MAX
for theenqueue
operation and(front + 1) % MAX
for thedequeue
operation. Ensure to handle the cases when the queue becomes full or empty appropriately.
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
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
andrear
, to track the first and last nodes of the queue.Hints: Initialize
front
andrear
to NULL. Forenqueue
, create a new node and updaterear
's next pointer. Fordequeue
, updatefront
to the next node. Handle edge cases when the queue becomes empty.
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.
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.
Sum of Elements in Queue
Approach: Traverse the queue from
front
torear
and calculate the sum of all elements.Hints: Initialize a sum variable to 0. Iterate through the queue elements from
front
torear
and add each element to the sum variable.
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
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
andrear
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.
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.
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.
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.
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
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.
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.
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.
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.
Multiple Queues in a Single Array
Approach: Implement multiple queues within a single array by dividing the array into segments and managing separate
front
andrear
pointers for each queue.Hints: Calculate the starting index and size for each queue segment. Manage
front
andrear
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:
Initialize an empty queue.
Enqueue elements: 10, 20, 30, 40, 50.
Peek at the front element, which is 10.
Dequeue two elements: 10 and 20.
Enqueue elements: 60 and 70.
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:
Initialize an empty queue.
Enqueue elements: 10, 20, 30.
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:
Initialize an empty queue with a size counter.
Enqueue elements: 10, 20, 30.
Print the size of the queue.
Dequeue one element.
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:
Initialize an empty circular queue.
Enqueue elements: 10, 20, 30, 40, 50.
Dequeue one element (10) and enqueue another (60).
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:
Initialize an empty queue.
Enqueue elements: 10, 20, 30, 40, 50.
Print the queue.
Reverse the queue elements.
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:
Initialize an empty queue using a linked list.
Enqueue elements: 10, 20, 30.
Display the queue elements.
Dequeue one element (10).
Display the queue elements again.
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:
Initialize an empty queue.
Enqueue the string "1".
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:
Initialize an empty queue.
Enqueue elements: 1, 2, 3, 4, 5.
Print the queue.
Interleave the first half of the queue with the second half.
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:
Initialize an empty queue.
Enqueue elements: 10, 20, 30, 40, 50.
Print the queue.
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:
Initialize two empty queues and one empty merged queue.
Enqueue elements: 10, 20 in the first queue, and 30, 40 in the second queue.
Print both queues.
Merge the two queues into the merged queue.
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:
Initialize an empty circular deque.
Insert elements at the rear and front: 10, 20 at the rear, and 5 at the front.
Print the deque elements.
Delete one element from the front (5) and one from the rear (30).
Print the deque elements again.
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:
Initialize an empty deque.
For the first window, insert indices of elements into the deque while maintaining decreasing order.
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.
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:
Initialize a frequency array and an empty queue.
For each character in the stream, enqueue it and update its frequency.
Dequeue characters from the front while their frequency is greater than 1.
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:
Initialize an empty queue.
Enqueue elements: 10, 20, 30, 40, 50.
Print the queue.
Reverse the first k elements of the queue.
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:
Initialize two empty deques for tracking minimum and maximum values.
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.
Sum the minimum and maximum values for each subarray.
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:
Initialize a frequency array and an empty queue.
For each task, update its frequency.
Use a queue to manage the cooldown period and track tasks that can be scheduled next.
Dequeue tasks from the queue if they have cooled down and can be scheduled again.
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:
Initialize the start and end indices and the current petrol balance.
Loop through the petrol pumps, adjusting the start index and current petrol balance when the balance is negative.
Continue until the tour is completed or it is determined that no solution exists.
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:
Initialize an empty queue.
Enqueue all characters of the string into the queue.
Dequeue characters and compare them with the original string in reverse order.
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:
Initialize an empty queue and visited matrix.
Enqueue all cells containing 1 with distance 0 and mark them as visited.
For each dequeued cell, enqueue its unvisited neighbors with distance incremented by 1.
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:
Initialize two queues within a single array, each using half of the array.
Enqueue elements: 10, 20 in the first queue, and 30, 40 in the second queue.
Print both queues.
Dequeue one element from each queue.
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