Queues

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:

1. Enqueue: Adds an element to the rear (end) of the queue.
2. Dequeue: Removes and returns the element from the front of the queue.
3. Front: Returns the element at the front of the queue without removing it.
4. Rear (or Back): Returns the element at the rear of the queue without removing it.
5. isEmpty: Checks if the queue is empty.
6. 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

Code Explanation

1. Include Header Files

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

• stdio.h: Provides input/output functions like printf.
• stdlib.h: Provides memory allocation functions like malloc and free.

2. Define the Queue Structure

#define MAX_SIZE 100
 
struct Queue {
    int array[MAX_SIZE];
    int front, rear;
};

• A Queue structure is defined with two members:
  • array: An array to store the queue elements.
  • front: An integer that tracks the index of the front element.
  • rear: An integer that tracks the index of the rear element.
• MAX_SIZE is defined as 100, which is the maximum capacity of the queue.

3. Function: initialize

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
}

• Purpose: Initializes the queue by setting front and rear to -1.
• Parameters:
  • queue: A pointer to the queue.

4. Function: isEmpty

int isEmpty(struct Queue *queue) {
    return (queue->front == -1 && queue->rear == -1); // If both front and rear are -1, queue is empty
}

• Purpose: Checks if the queue is empty.
• Parameters:
  • queue: A pointer to the queue.
• Returns:
  • 1 if the queue is empty (front == -1 and rear == -1).
  • 0 otherwise.

5. Function: isFull

int isFull(struct Queue *queue) {
    return (queue->rear == MAX_SIZE - 1); // If rear is at the maximum index, queue is full
}

• Purpose: Checks if the queue is full.
• Parameters:
  • queue: A pointer to the queue.
• Returns:
  • 1 if the queue is full (rear == MAX_SIZE - 1).
  • 0 otherwise.

6. Function: enqueue

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
}

• Purpose: Adds an element to the rear of the queue.
• Parameters:
  • queue: A pointer to the queue.
  • item: The element to be added.
• Steps:
  1. Check if the queue is full (rear == MAX_SIZE - 1).
     • If full, print “Queue Overflow” and return.
  2. If the queue is empty (front == -1 and rear == -1), set front to 0.
  3. Increment rear and add the element to the array at the rear index.

7. Function: dequeue

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
}

• Purpose: Removes and returns the front element from the queue.
• Parameters:
  • queue: A pointer to the queue.
• Steps:
  1. Check if the queue is empty (front == -1 and rear == -1).
     • If empty, print “Queue Underflow” and return -1.
  2. Retrieve the data of the front element.
  3. If the queue has only one element (front == rear), reset front and rear to -1.
  4. Otherwise, increment front.
  5. Return the retrieved data.

8. Function: front

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
}

• Purpose: Returns the front element of the queue without removing it.
• Parameters:
  • queue: A pointer to the queue.
• Steps:
  1. Check if the queue is empty (front == -1 and rear == -1).
     • If empty, print “Queue is empty” and return -1.
  2. Return the data of the front element.

9. Function: rear

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
}

• Purpose: Returns the rear element of the queue without removing it.
• Parameters:
  • queue: A pointer to the queue.
• Steps:
  1. Check if the queue is empty (front == -1 and rear == -1).
     • If empty, print “Queue is empty” and return -1.
  2. Return the data of the rear element.

10. Main Function

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;
}

• Steps:
  1. Initialize the queue.
  2. Enqueue elements 10, 20, and 30 into the queue.
  3. Print the front element (10) and rear element (30) of the queue.
  4. Dequeue all elements from the queue and print them (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

Code Explanation

1. Define the Node Structure

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

• A Node structure is defined with two members:
  • data: Stores the integer value of the node.
  • next: A pointer to the next node in the linked list.

2. Define the Queue Structure

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

• A Queue structure is defined with two members:
  • front: A pointer to the front node of the queue.
  • rear: A pointer to the rear node of the queue.

3. Function: initialize

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
}

• Purpose: Initializes the queue by setting front and rear to NULL.
• Parameters:
  • queue: A pointer to the queue.

4. Function: isEmpty

int isEmpty(struct Queue *queue) {
    return (queue->front == NULL); // If front is NULL, queue is empty
}

• Purpose: Checks if the queue is empty.
• Parameters:
  • queue: A pointer to the queue.
• Returns:
  • 1 if the queue is empty (front == NULL).
  • 0 otherwise.

5. Function: enqueue

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;
}

• Purpose: Adds an element to the rear of the queue.
• Parameters:
  • queue: A pointer to the queue.
  • item: The element to be added.
• Steps:
  1. Allocate memory for a new node.
  2. Assign item to the data field of the new node.
  3. Set the next of the new node to NULL.
  4. If the queue is empty (front == NULL), set both front and rear to the new node.
  5. Otherwise, add the new node to the end of the queue and update rear.

6. Function: dequeue

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
}

• Purpose: Removes and returns the front element from the queue.
• Parameters:
  • queue: A pointer to the queue.
• Steps:
  1. Check if the queue is empty (front == NULL).
     • If empty, print “Queue Underflow” and return -1.
  2. Retrieve the data of the front element.
  3. Store the front node in a temporary pointer.
  4. Move front to the next node.
  5. Free the memory of the removed node.
  6. If the queue becomes empty (front == NULL), set rear to NULL.
  7. Return the retrieved data.

7. Function: front

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
}

• Purpose: Returns the front element of the queue without removing it.
• Parameters:
  • queue: A pointer to the queue.
• Steps:
  1. Check if the queue is empty (front == NULL).
     • If empty, print “Queue is empty” and return -1.
  2. Return the data of the front element.

9. Function: rear

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
}

• Purpose: Returns the rear element of the queue without removing it.
• Parameters:
  • queue: A pointer to the queue.
• Steps:
  1. Check if the queue is empty (front == NULL).
     • If empty, print “Queue is empty” and return -1.
  2. Return the data of the rear element

10. Main Function

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;
}

• Steps:
  1. Initialize the queue.
  2. Enqueue elements 10, 20, and 30 into the queue.
  3. Print the front element (10) and rear element (30) of the queue.
  4. Dequeue all elements from the queue and print them (10, 20, 30).