Implementation using Queue of Arrays

What is a Queue?

A Queue is a data structure that works on the FIFO principle, which stands for First In, First Out. This means that the first element added to the queue will be the first one to be removed, just like waiting in a line—those who arrive first get served first.

• Enqueue: This operation adds an element to the end of the queue.
• Dequeue: This operation removes an element from the front of the queue.
• Peek/Front: This operation shows the element at the front of the queue without removing it.
• isEmpty: This operation checks if the queue is empty.
• isFull: This operation checks if the queue is full.

Now, let’s get into the code implementation using arrays.

Steps for Queue Implementation

1. Define the Maximum Size of the queue.
2. Create an Array to store the queue elements.
3. Initialize Front and Rear pointers.
   • front will point to the first element.
   • rear will point to the last element.
4. Implement Enqueue Operation: Add an element to the rear of the queue.
5. Implement Dequeue Operation: Remove an element from the front of the queue.
6. Implement Display Operation: Print all the elements of the queue.
7. Check for Underflow and Overflow conditions:
   • Queue is full when the rear pointer reaches the maximum size.
   • Queue is empty when no elements are present, i.e., the front pointer goes beyond the rear.

Here’s the C program to implement a Queue using arrays:

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

#define MAX 5  // Define the maximum size of the queue

// Declare the Queue structure
struct Queue {
    int items[MAX];
    int front;
    int rear;
};

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

// Check if the queue is full
int isFull(struct Queue* q) 
{
    if (q->rear == MAX - 1) 
        return 1;
    else
        return 0;
}

// Check if the queue is empty
int isEmpty(struct Queue* q) 
{
    if (q->front == -1 || q->front > q->rear) 
        return 1;
    else
        return 0;
}

// Function to add an element to the queue
void enqueue(struct Queue* q, int value) 
{
    if (isFull(q)) 
{
        printf("Queue is Full! Cannot insert %d\n", value);
    } else {
        if (q->front == -1) 
{
            q->front = 0;  // Set front to 0 if the queue was empty
        }
        q->rear++;
        q->items[q->rear] = value;
        printf("Inserted %d into the queue\n", value);
    }
}

// Function to remove an element from the queue
int dequeue(struct Queue* q) 
{
    int item;
    if (isEmpty(q)) 
{
        printf("Queue is Empty! Nothing to dequeue\n");
        return -1;
    } 
else 
{
        item = q->items[q->front];
        q->front++;
        if (q->front > q->rear)
{
            q->front = q->rear = -1;  // Reset the queue when all elements are dequeued
        }
        printf("Removed %d from the queue\n", item);
        return item;
    }
}

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

// Main function to demonstrate the operations of the queue
int main() 
{
    struct Queue q;
    createQueue(&q);
    
    // Enqueue elements
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    enqueue(&q, 40);
    enqueue(&q, 50);
    
    // Display queue
    display(&q);
    
    // Try to enqueue when queue is full
    enqueue(&q, 60);
    
    // Dequeue elements
    dequeue(&q);
    dequeue(&q);
    
    // Display queue after dequeue
    display(&q);
    
    return 0;
}

Explanation:

1. Struct Definition: The Queue structure consists of:
   • items[]: An array to store the elements of the queue.
   • front: Points to the first element in the queue.
   • rear: Points to the last element in the queue.
2. createQueue(): Initializes the queue with front and rear set to -1, indicating an empty queue.
3. isFull(): Checks if the rear pointer has reached the maximum size (MAX - 1), meaning no more elements can be inserted.
4. isEmpty(): Checks if the queue is empty by verifying whether the front is -1 or greater than rear.
5. enqueue(): Adds a new element to the queue:
   • First, check if the queue is full.
   • If not full, increment rear and add the element to the items[] array.
   • If it’s the first element being inserted, set front to 0.
6. dequeue(): Removes an element from the front of the queue:
   • First, check if the queue is empty.
   • If not, retrieve the element from items[front] and increment front.
   • If all elements are dequeued, reset front and rear to -1.
7. display(): Prints all the elements of the queue from front to rear.

Output:

Inserted 10 into the queue
Inserted 20 into the queue
Inserted 30 into the queue
Inserted 40 into the queue
Inserted 50 into the queue
Queue elements are: 10 20 30 40 50 
Queue is Full! Cannot insert 60
Removed 10 from the queue
Removed 20 from the queue
Queue elements are: 30 40 50 

This code demonstrates a simple queue using arrays and includes boundary checks for overflow (when the queue is full) and underflow (when the queue is empty).