The Linear and Circular Queue

A linear queue is a type of queue data structure where elements are arranged in a linear order by using linear array data structure. It follows the First In, First Out (FIFO) principle, meaning the element that is inserted first is the one that gets removed first. Linear queues have a fixed size and two pointers, usually referred to as FRONT and REAR, to keep track of the front and rear positions of the queue, respectively.

In a linear queue:

Front Pointer (FRONT): Points to the front element of the queue, which is the next element to be dequeued.

Rear Pointer (REAR): Points to the rear element of the queue, which is the position where the next element will be enqueued.

Key operations on a linear queue include:

• Enqueue: Adding an element to the rear end of the queue.
• Dequeue: Removing an element from the front end of the queue.
• Overflow: Occurs when trying to enqueue an element into a full queue.
• Underflow: Occurs when trying to dequeue an element from an empty queue.

(Algorithm for enqueue and dequeue operation is define in previous section)

Write C++ program to implement a linear queue using arrays.

#include<iostream>
#define SIZE 5
using namespace std;

class Queue{
    int *arr;
    int front;
    int rear;
    public:
    Queue();
    ~Queue();
    bool isEmpty();
    bool isFull();
    void display();
    void enqueue(int);
    int dequeue();
};

Queue::Queue(){
    arr = new int[SIZE];
    front = -1;
    rear = -1;
}
Queue::~Queue(){
    delete []arr;
}
bool Queue::isEmpty(){
    return (front==-1 && rear==-1);
}

bool Queue::isFull(){
    return (rear==SIZE-1);
}
int Queue::dequeue(){
    if(isEmpty()){
        cout<<"queue underflow"<<endl;
        exit(0);
    }
    else
    {
        return arr[front++];
    }
}
void Queue::display(){
    int i;
    if(isEmpty()){
        cout<<"Queue is empty"<<endl;
    }else{
        for(i=front;i<=rear;i++){
            cout<<arr[i]<<" ";
        }
        cout<<endl;
    }
}

void Queue::enqueue(int item){
    if(isFull()){
        cout<<"queue overflow"<<endl;
        exit(0);
    }
    else{
        if(isEmpty()){
            front=0;
            rear=0;
        }
        else{
            rear++;
        }
        arr[rear] = item;
    }
}

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

Limitations of Linear queue:

Fixed Size of array: The size of array is fixed at the time of its declarations. This fixed size of array can lead to memory wastage is the size of array is declared more than the requirement or if the size of array is declared less than the requirement it can lead to early overflow condition.

Memory Wastage: The condition of linear queue, the element can be inserted only at the rear end can lead to memory wastage. Let us consider a scenario in which the queue is FULL i.e rear pointer is pointing at the last index of the queue. Now, if some elements are deleted from the front end, obviously there are some spaces left before the current position of the front pointer. Even then the enqueue operation results in “OVERFLOW” condition as the rear is still pointing at the last index and the enqueue can only be done at the rear end condition.The following diagram illustrates the given concept:

Circular Queue

The above mentioned limitations of memory wastage in linear queue can be solved by a special queue data structure called Circular queue. In a circular queue, the first index comes right after the rear index. The given diagram shows circular queue:

Circular queue will be full when front = 0 and rear = max-1. Implementation of a circular queue is similar to that of a linear queue. Only the logic part that is implemented in the case of insertion and deletion is different from that in a linear queue.

Insertion in Circular queue

There are three scenarios of inserting an element in a queue.

1. If (rear + 1)%maxsize = front, the queue is full. In that case, overflow occurs and therefore, insertion can not be performed in the queue.
2. If rear != max - 1, then rear will be incremented and the new value will be inserted at the rear end of the queue.
3. If front != 0 and rear = max - 1, then it means that the queue is not full therefore, set the value of rear to 0 and insert the new element there.

Algorithm to insert element into circular queue

Algorithm: Enqueue (Insert an element into the circular queue)
Input: VAL (Element to be inserted)

Step 1: IF (REAR + 1) % MAX_SIZE = FRONT
           Write "OVERFLOW"
           Goto Step 4
       [END OF IF]

Step 2: IF FRONT = -1 and REAR = -1
           SET FRONT = REAR = 0
       ELSE IF REAR = MAX_SIZE - 1 and FRONT != 0
           SET REAR = 0
       ELSE
           SET REAR = (REAR + 1) % MAX_SIZE
       [END OF IF]

Step 3: SET QUEUE[REAR] = VAL

Step 4: EXIT

Algorithm to delete element from circular queue

To delete an element from the circular queue, we must check for the three following conditions.

1. If front = -1, then there are no elements in the queue and therefore this will be the case of an underflow condition.
2. If there is only one element in the queue, in this case, the condition rear = front holds and therefore, both are set to -1 and the queue is deleted completely.
3. If front = max -1 then, the value is deleted from the front end the value of front is set to 0.
4. Otherwise, the value of front is incremented by 1 and then delete the element at the front end

Algorithm: Dequeue (Delete an element from the circular queue)

Step 1: IF FRONT = -1
           Write "UNDERFLOW"
           Goto Step 4
       [END OF IF]

Step 2: SET VAL = QUEUE[FRONT]

Step 3: IF FRONT = REAR
           SET FRONT = REAR = -1
       ELSE
           IF FRONT = MAX_SIZE - 1
               SET FRONT = 0
           ELSE
               SET FRONT = FRONT + 1
           [END OF IF]
       [END OF IF]

Step 4: EXIT

Write a C++ program to implement circular queue:

#include <iostream>
using namespace std;

#define MAX_SIZE 5 // Change the size of the circular queue as needed

class CircularQueue {
private:
    int queue[MAX_SIZE];
    int front, rear;

public:
    // Constructor
    CircularQueue() {
        front = -1; // Initialize front pointer
        rear = -1;  // Initialize rear pointer
    }

    // Function to check if the queue is empty
    bool isEmpty() {
        return (front == -1 && rear == -1);
    }

    // Function to check if the queue is full
    bool isFull() {
        return (front == (rear + 1) % MAX_SIZE);
    }

    // Function to add an element to the queue (enqueue)
    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue Overflow: Unable to enqueue element " << value << endl;
            return;
        }
        else if (isEmpty()) {
            front = rear = 0; // Set front and rear pointers to 0 if queue is empty
        }
        else if((rear==MAX_SIZE-1) && (front!=0) )
        {
            rear = 0;
        }
        else {
            rear = (rear + 1) % MAX_SIZE; // Circular increment of rear pointer
        }
        queue[rear] = value;
        cout << "Enqueued element: " << value << endl;
    }

    // Function to remove an element from the queue (dequeue)
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue Underflow: Unable to dequeue element" << endl;
            return;
        }
        int dequeuedValue = queue[front];
        if (front == rear) {
            front = rear = -1; // Reset front and rear pointers if there's only one element in the queue
        }
        else {
            front = (front + 1) % MAX_SIZE; // Circular increment of front pointer
        }
        cout << "Dequeued element: " << dequeuedValue << endl;
    }

    // Function to display the queue
    void display() {
        if (isEmpty()) {
            cout << "Queue is empty" << endl;
            return;
        }
        cout << "Queue elements: ";
        int i = front;
        while (i != rear) {
            cout << queue[i] << " ";
            i = (i + 1) % MAX_SIZE; // Circular increment of index
        }
        cout << queue[rear] << endl; // Print the last element
    }
};

int main() {
    CircularQueue q;

    // Enqueue elements
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.enqueue(40);
    q.enqueue(50); // Filling the queue to demonstrate overflow
    q.enqueue(60); // Overflow

    // Display the queue
    q.display();

    // Dequeue elements
    q.dequeue();
    q.dequeue();
    q.enqueue(100);
    q.enqueue(120);

    // Display the queue after dequeuing
    q.display();

    return 0;
}