Queues are linear data structures that follow the First In First Out (FIFO) principle. As a result, the element that is inserted first will be removed first. A queue has two primary operations:

• Enqueue: Insert an element into the queue (at the rear).
• Dequeue: Remove an element from the queue (from the front).

The queue is typically represented by two variables, they are:

• Front: Refers to the queue's first element.‍
• Rear: Refers to the last element of the queue.

In an array-based implementation:

• The queue will be represented by an array of a fixed size.
• The front pointer points to the index of the front of the queue, and the rear pointer points to the index of the rear of the queue.

The basic operations of a queue using an array are:

Enqueue Operation (Insertion)

• Insert a new element at the position indicated by the rear pointer.
• Increment the rear pointer after the insertion.
• If the queue is full (when rear exceeds the size of the array), the insertion is not possible.

Algorithm for Enqueue Operation

1. Check if the queue is full (rear == size of the array).
2. If the queue is full, print "Queue is full" and exit.
3. If the queue is not full:
   a. Increment the rear index.
   b. Insert the new element at the rear index in the array.

Dequeue Operation (Deletion)

• Remove the element at the position indicated by the front pointer.
• Increment the front pointer after the deletion.
• If the queue is empty (front equals rear), the deletion is not possible.

Algorithm for Dequeue Operation

1. Check if the queue is empty (front == rear).
2. If the queue is empty, print "Queue is empty" and exit.
3. If the queue is not empty:
   a. Get the value at the front index of the array.
   b. Increment the front index.

Let’s use an array of size 5 to demonstrate the queue operations with an example.

Initial Setup

We start with two variables, front and rear both initialized to -1. This indicates that the queue is empty initially.

• Array: []
• front = -1 (indicates the queue is empty)
• rear = -1 (indicates the queue is empty)

Operation 1: Enqueue(10)

Before Operation: front = -1, rear = -1

We insert the value 10 at the rear of the queue. Since the queue is empty, both front and rear will point to index 0.

After Operation:

• front = 0, rear = 0
• Queue structure: [10]

Operation 2: Enqueue(20)

Before Operation: front = 0, rear = 0

We insert the value 20 at the rear of the queue. The rear is incremented to 1, and the value 20 is added at position 1.

After Operation:

• front = 0, rear = 1
• Queue structure: [10, 20]

Operation 3: Dequeue()

Before Operation: front = 0, rear = 1

We remove the value at the front of the queue, which is 10 (the value at index 0). After removing this element, the front is incremented to 1.

After Operation:

• front = 1, rear = 1
• Queue structure: [20]

Operation 4: Enqueue(30)

Before Operation: front = 1, rear = 1

We insert the value 30 at the rear of the queue. The rear is incremented to 2, and the value 30 is added at position 2.

After Operation:

• front = 1, rear = 2
• Queue structure: [20, 30]

Operation 5: Enqueue(40)

Before Operation: front = 1, rear = 2

We insert the value 40 at the rear of the queue. The rear is incremented to 3, and the value 40 is added at position 3.

After Operation:

• front = 1, rear = 3
• Queue structure: [20, 30, 40]

Operation 6: Dequeue()

Before Operation: front = 1, rear = 3

We remove the value at the front of the queue, which is 20 (the value at index 1). After removing this element, the front is incremented to 2.

After Operation:

• front = 2, rear = 3
• Queue structure: [30, 40]

Using an array to implement a queue has several advantages. Arrays are contiguous blocks of memory, which allows for easy access to elements via an index. This makes it easy to manage the front and rear of the queue efficiently. The main reasons to use an array for a queue implementation are:

• An array has a predefined size, which helps in limiting the number of elements in the queue. 
• Since arrays provide constant-time access to elements (O(1) complexity), enqueue and dequeue operations can be performed with minimal overhead.
• Implementing a queue using an array is simple, making it an ideal choice for basic queue operations.

Here is the implementation of the queue using array in C, C++, and Java languages:

C Program for Queue Using Array

Below is a simple C program to implement a queue using an array.

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

#define MAX 5

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

void initQueue(struct Queue* q) {
    q->front = -1;
    q->rear = -1;
}

int isFull(struct Queue* q) {
    return q->rear == MAX - 1;
}

int isEmpty(struct Queue* q) {
    return q->front == -1;
}

void enqueue(struct Queue* q, int value) {
    if (isFull(q)) {
        printf("Queue is full\n");
        return;
    }
    if (q->front == -1) {
        q->front = 0;
    }
    q->rear++;
    q->items[q->rear] = value;
    printf("Enqueued: %d\n", value);
}

int dequeue(struct Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int item = q->items[q->front];
    if (q->front == q->rear) {
        q->front = q->rear = -1;
    } else {
        q->front++;
    }
    return item;
}

int main() {
    struct Queue q;
    initQueue(&q);
    enqueue(&q, 10);
    enqueue(&q, 20);
enqueue(&q, 30);
    printf("Dequeued: %d\n", dequeue(&q));
    return 0;
}

Queue Using an Array in C++

#include <iostream>
using namespace std;

#define MAX 5

class Queue {
private:
    int arr[MAX];
    int front, rear;

public:
    Queue() {
        front = -1;
        rear = -1;
    }

    bool isFull() {
        return rear == MAX - 1;
    }

    bool isEmpty() {
        return front == -1;
    }

    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue is full!" << endl;
            return;
        }
        if (front == -1) front = 0;
        rear++;
        arr[rear] = value;
        cout << "Enqueued: " << value << endl;
    }

    int dequeue() {
 		if (isEmpty()) {
            cout << "Queue is empty!" << endl;
            return -1;
        }
        int dequeuedValue = arr[front];
        if (front == rear) {
            front = rear = -1;
        } else {
            front++;
        }
        return dequeuedValue;
    }
};

int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    cout << "Dequeued: " << q.dequeue() << endl;
    return 0;
}

Queue Using an Array in Java

public class Queue {
    private int[] arr;
    private int front, rear;
    private int maxSize;

    public Queue(int size) {
        arr = new int[size];
        front = -1;
        rear = -1;
        maxSize = size;
    }

    public boolean isFull() {
        return rear == maxSize - 1;
    }

    public boolean isEmpty() {
        return front == -1;
    }

    public void enqueue(int value) {
 if (isFull()) {
            System.out.println("Queue is full!");
            return;
        }
        if (front == -1) front = 0;
        rear++;
        arr[rear] = value;
        System.out.println("Enqueued: " + value);
    }

    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty!");
            return -1;
        }
        int dequeuedValue = arr[front];
        if (front == rear) {
            front = rear = -1;
        } else {
            front++;
        }
        return dequeuedValue;
    }

    public static void main(String[] args) {
        Queue q = new Queue(5);
        q.enqueue(10);
        q.enqueue(20);
        q.enqueue(30);
        System.out.println("Dequeued: " + q.dequeue());
    }
}

Here are the key applications of queue using an array:

• A queue data structure is used to manage customer orders in a store, ensuring that customers are served in the order they arrive.
• Queues are used to schedule tasks or processes for execution by the CPU, ensuring that each task is executed in the order it was received.
• Queues are used to manage disk I/O requests, prioritizing requests based on factors like request type, priority, and disk usage.
• A queue is used to manage print jobs, ensuring that each job is processed in the order it was received

Here are some of the advantages of queue using array:

• The implementation is easy to understand and provides efficient O(1) access to elements.
• Arrays are stored in contiguous blocks, allowing for efficient memory access.
• Arrays are cache-friendly, which can improve performance in systems with limited memory.

Here are the disadvantages of queue using an array:

• The queue’s capacity is fixed and equal to the array’s size, leaving unused space when the queue is partially filled.
• The dequeue operation has a time complexity of O(N), which is inefficient, especially when dealing with large datasets.
• The array-based implementation requires additional memory to store the queue’s metadata, such as front and rear pointers.
• Implementing a queue using an array can be complex, especially when handling edge cases such as queue overflow or underflow.

In conclusion, implementing a queue using an array is a simple and powerful method for managing data in a FIFO order. It is suitable for use cases where the maximum size of the queue is known and remains constant. However, for dynamic scenarios, more advanced structures like linked lists or dynamic arrays may be better suited.

1. Is the queue size fixed when using an array?

Yes, the queue size is fixed when using an array because the array is statically allocated with a predefined maximum size.

2. Can I implement a priority queue using an array?

Yes, a priority queue can be implemented using an array in programming languages like Java and C++, where elements are inserted in such a way that the highest (or lowest) priority element is always at the front.