The Queue Abstract Data Type (ADT) is a collection of elements that follows a specific order for operations. It’s primarily used for managing data in a first-in, first-out (FIFO) manner, meaning that the first element added to the queue will be the first one to be removed.

Key Operations

1. Enqueue: Adds an element to the back of the queue.
2. Dequeue: Removes and returns the element from the front of the queue.
3. Peek/Front: Returns the element at the front of the queue without removing it.
4. IsEmpty: Checks if the queue is empty.
5. Size: Returns the number of elements in the queue.

Applications

• Task Scheduling: Managing tasks in operating systems (like CPU scheduling).
• Breadth-First Search (BFS): In graph algorithms, queues help keep track of nodes to explore.
• Print Queue: Managing print jobs sent to a printer.
• Event Handling: Queues are often used in event-driven programming to manage events.

Implementation

Queues can be implemented using various data structures, including:

• Arrays: Fixed size, can lead to inefficient resizing.
• Linked Lists: Dynamic size, allows for efficient insertions and deletions.
• Circular Buffers: Efficient use of space in a fixed-size array.

Example Queue Implementation Using Array

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

#define MAX 5 // Maximum size of the queue

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

// Function to create a queue
Queue* createQueue() {
Queue* q = (Queue*)malloc(sizeof(Queue));
q->front = -1;
q->rear = -1;
return q;
}

// Check if the queue is full
bool isFull(Queue* q) {
return (q->rear + 1) % MAX == q->front;
}

// Check if the queue is empty
bool isEmpty(Queue* q) {
return q->front == -1;
}

// Add an item to the queue
void enqueue(Queue* 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(“Enqueued: %d\n”, value);
}

// Remove an item from the queue
int dequeue(Queue* q) {
if (isEmpty(q)) {
printf(“Queue is empty!\n”);
return -1; // Indicating queue is empty
}
int value = q->items[q->front];
if (q->front == q->rear) {
q->front = -1; // Queue is now empty
q->rear = -1;
} else {
q->front = (q->front + 1) % MAX;
}
printf(“Dequeued: %d\n”, value);
return value;
}

// Peek at the front item of the queue
int peek(Queue* q) {
if (isEmpty(q)) {
printf(“Queue is empty!\n”);
return -1; // Indicating queue is empty
}
return q->items[q->front];
}

// Free the queue
void freeQueue(Queue* q) {
free(q);
}

// Main function to demonstrate the queue
int main() {
Queue* q = createQueue();

enqueue(q, 10);
enqueue(q, 20);
enqueue(q, 30);
enqueue(q, 40);
enqueue(q, 50);
enqueue(q, 60); // This will indicate that the queue is full

printf(“Front item is: %d\n”, peek(q));

dequeue(q);
dequeue(q);

printf(“Front item is: %d\n”, peek(q));

freeQueue(q);
return 0;
}

 

Explanation

1. Queue Structure: The Queue structure holds an array for the items, and indices for the front and rear.
2. Functions:
   • createQueue: Initializes the queue.
   • isFull and isEmpty: Check the queue’s state.
   • enqueue: Adds an element to the rear of the queue.
   • dequeue: Removes an element from the front of the queue.
   • peek: Returns the front element without removing it.
3. Main Function: Demonstrates usage of the queue, including enqueuing and dequeuing elements.