Queue and Circular Queue (Array Implementation), Code ↔ Language

Queue

Creation of Queue (Array Implementation)

class Queue {
private:
    int* arr;
    int front;
    int rear;
    int capacity;

public:
    // Constructor to initialize queue
    Queue(int size) {
        arr = new int[size];
        capacity = size;
        front = -1;
        rear = -1;
    }
};

1. First, we will create a class named Queue.

2. It will contain four properties:

   • int* arr: Points to the array that will store queue elements.
   • int front: Stores the index of the front element in the queue.
   • int rear: Stores the index of the rear element in the queue.
   • int capacity: Stores the maximum number of elements the queue can hold.

3. We will declare a constructor Queue(int size):

   • It will take size as input.
   • We will dynamically allocate memory for the queue array with the given size and assign it to arr.
   • We will set the capacity to the given size.
   • We will set front and rear to -1, indicating an empty queue.

Enqueue Operation

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

We will define a method enqueue(int value):

• It will take an integer value as input, which is the value to be added to the queue.
• We will check if the queue is full (using isFull()); if so, it will print "Queue is full. Cannot enqueue." and return.
• Otherwise, it will increment the rear index and assign the value to the queue at the updated rear index.
• If the queue was empty (i.e., front was -1), it will set front to 0.

Dequeue Operation

void dequeue() {
    if (isEmpty()) {
        cout << "Queue is empty. Cannot dequeue." << endl;
        return;
    }
    front++;
    if (front > rear) {
        front = rear = -1; // Reset when the queue becomes empty
    }
}

We will define a method dequeue():

• It will remove an element from the front of the queue.
• We will check if the queue is empty (using isEmpty()); if so, it will print "Queue is empty. Cannot dequeue." and return.
• Otherwise, it will increment the front index.
• If the front index exceeds the rear index after dequeuing, indicating the queue is now empty, it will reset both front and rear to -1.

Problem with the Dequeue Operation

The above dequeue implementation is simple and efficient, with a time complexity of O(1). However, it has a significant drawback: as the front pointer keeps incrementing with each dequeue operation, it moves towards the end of the array. Eventually, the front pointer reaches the end of the array, and no further enqueues can be performed, even if there is available space at the beginning of the array. This leads to inefficient use of the array space.

Solution: Shifting Elements

To solve this issue, we can shift the elements of the array to the left whenever a dequeue operation is performed. This way, the front pointer always points to the first valid element in the queue, and the rear pointer correctly reflects the position of the last valid element. Shifting elements ensures that we can reuse the space at the beginning of the array and maintain the efficient functionality of the queue.

Dequeue Operation (Improved)

void dequeue() {
    if (isEmpty()) {
        cout << "Queue is empty. Cannot dequeue." << endl;
        return;
    }
    // Remove the element from the front of the queue
    for (int i = 0; i < rear; i++) {
        arr[i] = arr[i + 1];
    }
    rear--;

    // If the queue is empty after dequeuing, reset pointers
    if (rear == -1) {
        front = -1;
    }
}

We will define a method dequeue():

• It will remove an element from the front of the queue.
• We will check if the queue is empty (using isEmpty()); if so, it will print "Queue is empty. Cannot dequeue." and return.
• Otherwise, we will shift all elements in the array one position to the left to fill the gap left by the dequeued element.
• We will decrement the rear index.
• If the queue becomes empty after dequeuing (i.e., rear is -1), it will reset front to -1 to indicate the queue is empty.

isFull Operation

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

We will define a method isFull():

• It will return a boolean value indicating whether the queue is full.
• It will return true if rear is equal to capacity - 1, indicating that the queue has reached its maximum capacity.
• Otherwise, it will return false.

isEmpty Operation

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

We will define a method isEmpty():

• It will return a boolean value indicating whether the queue is empty.
• It will return true if front is -1, indicating that the queue is empty.
• Otherwise, it will return false.

Full Code Implementation

#include <iostream>
using namespace std;

class Queue {
private:
    int* arr;
    int front;
    int rear;
    int capacity;

public:
    // Constructor to initialize queue
    Queue(int size) {
        arr = new int[size];
        capacity = size;
        front = -1;
        rear = -1;
    }

    // Destructor to free allocated memory
    ~Queue() {
        delete[] arr;
    }

    // Enqueue operation
    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue is full. Cannot enqueue." << endl;
            return;
        }
        rear++;
        arr[rear] = value;
        if (front == -1) {
            front = 0;
        }
    }

    // Dequeue operation (Improved)
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty. Cannot dequeue." << endl;
            return;
        }
        // Remove the element from the front of the queue
        for (int i = 0; i < rear; i++) {
            arr[i] = arr[i + 1];
        }
        rear--;

        // If the queue is empty after dequeuing, reset pointers
        if (rear == -1) {
            front = -1;
        }
    }

    // Peek operation
    int peek() {
        if (isEmpty()) {
            cout << "Queue is empty." << endl;
            return -1;
        }
        return arr[front];
    }

    // Check if queue is empty
    bool isEmpty() {
        return front == -1;
    }

    // Check if queue is full
    bool isFull() {
        return rear == capacity - 1;
    }
};

Circular Queue

Creation of Circular Queue (Array Implementation)

class CircularQueue {
private:
    int* arr;
    int front;
    int rear;
    int capacity;
    int size;

public:
    // Constructor to initialize queue
    CircularQueue(int size) {
        arr = new int[size];
        capacity = size;
        front = 0;
        rear = -1;
        this->size = 0;
    }
};

1. First, we will create a class named CircularQueue.

2. It will contain five properties:

   • int* arr: Points to the array that will store queue elements.
   • int front: Stores the index of the front element in the queue.
   • int rear: Stores the index of the rear element in the queue.
   • int capacity: Stores the maximum number of elements the queue can hold.
   • int size: Keeps track of the current number of elements in the queue.

3. We will declare a constructor CircularQueue(int size):

   • It will take size as input.
   • We will dynamically allocate memory for the queue array with the given size and assign it to arr.
   • We will set the capacity to the given size.
   • We will initialize front to 0, rear to -1, and size to 0, indicating an empty queue.

Enqueue Operation

void enqueue(int item) {
    if (isFull()) {
        cout << "Queue is full. Cannot enqueue.\n";
        return;
    }
    rear = (rear + 1) % capacity;
    arr[rear] = item;
    size++;
}

We will define a method enqueue(int item):

• It will take an integer item as input, which is the value to be added to the queue.
• We will check if the queue is full (using isFull()); if so, it will print "Queue is full. Cannot enqueue." and return.
• Otherwise, we will increment the rear index in a circular manner using modulo operation (rear + 1) % capacity and assign the item to the queue at the updated rear index.
• We will then increment the size.

Dequeue Operation

int dequeue() {
    if (isEmpty()) {
        cout << "Queue is empty. Cannot dequeue.\n";
        return -1;
    }
    int item = arr[front];
    front = (front + 1) % capacity;
    size--;
    return item;
}

We will define a method dequeue():

• It will remove an element from the front of the queue.
• We will check if the queue is empty (using isEmpty()); if so, it will print "Queue is empty. Cannot dequeue." and return -1.
• Otherwise, we will retrieve the element from the front index, increment the front index in a circular manner using modulo operation (front + 1) % capacity, and decrement the size.
• We will return the removed item.

isFull Operation

bool isFull() {
    return size == capacity;
}

We will define a method isFull():

• It will return a boolean value indicating whether the queue is full.
• It will return true if size is equal to capacity, indicating that the queue has reached its maximum capacity.
• Otherwise, it will return false.

isEmpty Operation

bool isEmpty() {
    return size == 0;
}

We will define a method isEmpty():

• It will return a boolean value indicating whether the queue is empty.
• It will return true if size is 0, indicating that the queue is empty.
• Otherwise, it will return false.

Full Code Implementation

#include <iostream>
using namespace std;

class CircularQueue {
private:
    int* arr;
    int front;
    int rear;
    int capacity;
    int size;

public:
    // Constructor to initialize queue
    CircularQueue(int size) {
        arr = new int[size];
        capacity = size;
        front = 0;
        rear = -1;
        this->size = 0;
    }

    // Destructor to free allocated memory
    ~CircularQueue() {
        delete[] arr;
    }

    // Enqueue operation
    void enqueue(int item) {
        if (isFull()) {
            cout << "Queue is full. Cannot enqueue.\n";
            return;
        }
        rear = (rear + 1) % capacity;
        arr[rear] = item;
        size++;
    }

    // Dequeue operation
    int dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty. Cannot dequeue.\n";
            return -1;
        }
        int item = arr[front];
        front = (front + 1) % capacity;
        size--;
        return item;
    }

    // Check if queue is full
    bool isFull() {
        return size == capacity;
    }

    // Check if queue is empty
    bool isEmpty() {
        return size == 0;
    }
};