Index
Queue
A queue is a fundamental data structure that follows the First-In, First-Out (FIFO) principle, meaning that the first element added to the queue is the first one to be removed. It operates on two main operations: enqueue and dequeue.
Here’s an overview of queue operations:
- Enqueue: Adds an element to the rear (end) of the queue.
- Dequeue: Removes and returns the element from the front of the queue.
- Front: Returns the element at the front of the queue without removing it.
- Rear (or Back): Returns the element at the rear of the queue without removing it.
- isEmpty: Checks if the queue is empty.
- isFull: Checks if the queue is full (for fixed-size queues).
Queues are commonly used in various computer science applications, including:
- Job scheduling: Managing tasks or processes waiting to be executed.
- Breadth-first search (BFS): Exploring nodes level by level in graph traversal algorithms.
- Buffering: Storing and processing data in a sequential order.
- Printer queues: Managing print jobs in printers.
- Bounded buffers: Implementing producer-consumer scenarios in concurrent programming.
Queues can be implemented using various underlying data structures, including arrays, linked lists, and circular buffers. The choice of implementation depends on factors like memory constraints, performance requirements, and the specific application context.
Queue Implementation using Array
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Define a structure for the queue
struct Queue {
int array[MAX_SIZE];
int front, rear;
};
// Function to initialize the queue
void initialize(struct Queue *queue) {
queue->front = -1; // Initialize front to -1 to indicate an empty queue
queue->rear = -1; // Initialize rear to -1 to indicate an empty queue
}
// Function to check if the queue is empty
int isEmpty(struct Queue *queue) {
return (queue->front == -1 && queue->rear == -1); // If both front and rear are -1, queue is empty
}
// Function to check if the queue is full
int isFull(struct Queue *queue) {
return (queue->rear == MAX_SIZE - 1); // If rear is at the maximum index, queue is full
}
// Function to enqueue (add) an element to the queue
void enqueue(struct Queue *queue, int item) {
if (isFull(queue)) {
printf("Queue Overflow\n");
return;
} else if (isEmpty(queue)) {
queue->front = 0; // Set front to 0 when the queue is empty
}
queue->rear++; // Increment rear
queue->array[queue->rear] = item; // Place the item at the rear of the queue
}
// Function to dequeue (remove) an element from the queue
int dequeue(struct Queue *queue) {
if (isEmpty(queue)) {
printf("Queue Underflow\n");
return -1; // Return an error value
}
int item = queue->array[queue->front]; // Retrieve the item at the front of the queue
if (queue->front == queue->rear) {
queue->front = -1; // Reset front and rear to -1 when the queue becomes empty
queue->rear = -1;
} else {
queue->front++; // Increment front
}
return item; // Return the dequeued item
}
// Function to get the front element of the queue without removing it
int front(struct Queue *queue) {
if (isEmpty(queue)) {
printf("Queue is empty\n");
return -1; // Return an error value
}
return queue->array[queue->front]; // Return the item at the front of the queue
}
// Function to get the rear element of the queue without removing it
int rear(struct Queue *queue) {
if (isEmpty(queue)) {
printf("Queue is empty\n");
return -1; // Return an error value
}
return queue->array[queue->rear]; // Return the item at the rear of the queue
}
int main() {
struct Queue queue;
initialize(&queue);
// Enqueue elements into the queue
enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
// Print the front and rear elements of the queue
printf("Front element of the queue: %d\n", front(&queue));
printf("Rear element of the queue: %d\n", rear(&queue));
// Dequeue elements from the queue and print them
printf("Elements dequeued from the queue:\n");
while (!isEmpty(&queue)) {
printf("%d\n", dequeue(&queue));
}
return 0;
}
Output:
Front element of the queue: 10
Rear element of the queue: 30
Elements dequeued from the queue:
10
20
30
Queue Implementation using Linked List
#include <stdio.h>
#include <stdlib.h>
// Define a structure for the node
struct Node {
int data;
struct Node* next;
};
// Define a structure for the queue
struct Queue {
struct Node* front;
struct Node* rear;
};
// Function to initialize the queue
void initialize(struct Queue *queue) {
queue->front = NULL; // Initialize front to NULL to indicate an empty queue
queue->rear = NULL; // Initialize rear to NULL to indicate an empty queue
}
// Function to check if the queue is empty
int isEmpty(struct Queue *queue) {
return (queue->front == NULL); // If front is NULL, queue is empty
}
// Function to enqueue (add) an element to the queue
void enqueue(struct Queue *queue, int item) {
// Create a new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
return;
}
// Assign data to the new node
newNode->data = item;
newNode->next = NULL;
// If the queue is empty, both front and rear point to the new node
if (isEmpty(queue)) {
queue->front = newNode;
queue->rear = newNode;
return;
}
// Otherwise, add the new node to the end of the queue and update the rear pointer
queue->rear->next = newNode;
queue->rear = newNode;
}
// Function to dequeue (remove) an element from the queue
int dequeue(struct Queue *queue) {
if (isEmpty(queue)) {
printf("Queue Underflow\n");
return -1; // Return an error value
}
int item = queue->front->data; // Retrieve the item at the front of the queue
struct Node* temp = queue->front; // Store the current front node
queue->front = queue->front->next; // Move the front pointer to the next node
free(temp); // Free the memory of the removed node
// If the queue becomes empty, update the rear pointer to NULL
if (queue->front == NULL) {
queue->rear = NULL;
}
return item; // Return the dequeued item
}
// Function to get the front element of the queue without removing it
int front(struct Queue *queue) {
if (isEmpty(queue)) {
printf("Queue is empty\n");
return -1; // Return an error value
}
return queue->front->data; // Return the item at the front of the queue
}
// Function to get the rear element of the queue without removing it
int rear(struct Queue *queue) {
if (isEmpty(queue)) {
printf("Queue is empty\n");
return -1; // Return an error value
}
return queue->rear->data; // Return the item at the rear of the queue
}
int main() {
struct Queue queue;
initialize(&queue);
// Enqueue elements into the queue
enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
// Print the front and rear elements of the queue
printf("Front element of the queue: %d\n", front(&queue));
printf("Rear element of the queue: %d\n", rear(&queue));
// Dequeue elements from the queue and print them
printf("Elements dequeued from the queue:\n");
while (!isEmpty(&queue)) {
printf("%d\n", dequeue(&queue));
}
return 0;
}
Output:
Front element of the queue: 10
Rear element of the queue: 30
Elements dequeued from the queue:
10
20
30
