C - PLUS-PLUS-QUEUES - CODE

JAVA PYTHON GO KOTLIN C# RUBY C++ Java Script

Implementing Queue in C++ using Arrays

Example :

#include <iostream>

using namespace std;

static const int SIZE = 10;

class Queue {

	private :
	
    int queueArray[SIZE];

	public :
	
    int frontElement = -1;
    int rearElement = -1;

    Queue() {

    }

    void enQueue(int i) {
        if (isFull()) {
            cout <<  "Queue is Full" << endl;
        } 
        else {
            
            if (frontElement == -1)
                frontElement++;
            
            rearElement++;
            queueArray[rearElement] = i;
            cout <<  "Inserted the element " << i << " to the Queue" << endl;
        }
    }

    int deQueue() {
        int element;
        if (isEmpty()) {

            cout <<  "Queue is empty" << endl;
            return -1;
        }
        else {
            element = queueArray[frontElement];

            if (frontElement >= rearElement) {
                queueArray[frontElement] = 0;
                frontElement = -1;
                rearElement = -1;
            }
            else {
                queueArray[frontElement] = 0;
                frontElement++;

            }
            cout <<  "The element " << element << " is removed from the Queue" << endl;
            return (element);
        }
    }
    
    bool isFull() {
        if (frontElement == 0 && rearElement == (SIZE - 1))
            return true;
        else
            return false;
    }

    bool isEmpty() {
        if (frontElement == -1)
            return true;
        else
            return false;
    }

    int front() {

        if (isEmpty()) {
            cout <<  "The Queue is empty" << endl;
            return -1;
        }
        else {
            return queueArray[frontElement];
        }
    }

    int rear() {

        if (isEmpty()) {
            cout <<  "The Queue is empty";
            return -1;
        }
        else {
            return queueArray[rearElement];
        }
    }
};

int main() {

    Queue queue;

    queue.enQueue(10);
    queue.enQueue(20);
    queue.enQueue(30);

    queue.deQueue();
    queue.deQueue();
    queue.deQueue();

    queue.deQueue();
}

Output :

Inserted the element 10 to the Queue
Inserted the element 20 to the Queue
Inserted the element 30 to the Queue
The element 10 is removed from the Queue
The element 20 is removed from the Queue
The element 30 is removed from the Queue
Queue is empty

Code Explanation for Queue

So, what we have tried in the above code is, we have inserted the the elements 10, 20 and 30 to the Queue.

Then we take the elements 10, 20 and 30 from the Queue.

As we know the most important operations/methods of Queue are Enqueue and Dequeue. However, there are other methods that we will be using here.

So, we have the below methods :

void enQueue(int i)

The enQueue(int i) method puts an element into the Queue.

int deQueue()

The int deQueue() method takes an element out of the Queue.

int front()

The int front() method returns the first element of the Queue.

int rear()

The int rear() method returns the last of the Queue.

bool isEmpty()

The isEmpty() method returns true if an array is empty and returns false if the array is not empty.

So, at first, we define the array where we will be storing the elements of the Stack.

int queueArray[SIZE];

Also, we have defined a constant called SIZE where we have defined the size of the array.

static const int SIZE = 10;

And, then we have initialised the variable frontElement and rearElement with -1.

int frontElement = -1;
int rearElement = -1;

The variable frontElement always points to the first element. Initially frontElement is -1 because it is not pointing to any element yet. When it becomes 0, it should be pointing to the 0th element.

Similarly, the variable rearElement always points to the last element. Initially rearElement is also -1 because it is not pointing to any element yet. When it becomes 0, it should be pointing to the 0th element initially.

Now, let us go to the main(..) method and see the Queue in action.

So, we have represented the Queue as an Array,

int queueArray[SIZE];

So, initially we have an empty Queue.

Then we try to insert the element 10 into the Queue, using EnQueue operation,

queue.enQueue(10);

So, the enQueue(int i) method is called,

void enQueue(int i) {
	if (isFull()) {
		cout <<  "Queue is Full";
	}
	else {

		if (frontElement == -1)
			frontElement++;

		rearElement++;
		queueArray[rearElement] = i;
		cout <<  "Inserted the element " << i << " to the Queue";
	}
}

Now, the enQueue(int i) method calls the isFull() method to check if the Array is full or not.

if (isFull()) {
	cout <<  "Queue is Full";
}

In this case the Array is not full, so we come to the else part.

else {

	if (frontElement == -1)
		frontElement++;

	rearElement++;
	queueArray[rearElement] = i;
	cout <<  "Inserted the element " << i << " to the Queue";
}

Now, inside the else condition, there is an if statement, that checks,

if (frontElement == -1)

And in this case the value of frontElement is -1. So, we enter in the block of if statement,

if (frontElement == -1)
	frontElement++;

And increment the value of frontElement by 1. And the value of frontElement becomes 0. So, the frontElement would be pointing to the first location now.

Similarly, we would be incrementing the rearElement as well.

rearElement++;

Then we initialise the element that was asked to be inserted(i.e.), in the first position.

queueArray[rearElement] = i;

So, both frontElement and rearElement would be pointing to the first location now.

Just think, if there are only one element in the Array representing Queue. Then both first and last element would be the same.

Then we come to the main(..) method again and try to insert the next element 20 to the Queue.

queue.enQueue(20);

So, the enQueue(int i) method is called,

void enQueue(int i) {
	if (isFull()) {
		cout <<  "Queue is Full";
	}
	else {

		if (frontElement == -1)
			frontElement++;

		rearElement++;
		queueArray[rearElement] = i;
		cout <<  "Inserted the element " << i << " to the Queue";
	}
}

Now, the enQueue(int i) method calls the isFull() method to check if the Array is full or not.

if (isFull()) {
	cout <<  "Queue is Full";
}

In this case the Array is not full, so we come to the else part.

else {

	if (frontElement == -1)
		frontElement++;

	rearElement++;
	queueArray[rearElement] = i;
	cout <<  "Inserted the element " << i << " to the Queue";
}

Now, inside the else condition, there is an if statement, that checks,

if (frontElement == -1)

And in this case the value of frontElement is 0. So, we do not enter in the block of if statement and do not touch the frontElement.

So, we would be incrementing the rearElement only.

rearElement++;

Then we initialise the element that was asked to be inserted(i.e. 20).

queueArray[rearElement] = i;

Now, frontElement would be pointing to the first element as usual and rearElement would be pointing to the last location now.

So, we come to the main(..) method again and try to insert the next element 30 to the Queue.

queue.enQueue(30);

Now, that we have inserted all the three elements to the Queue. So, it is time for us to take the elements out of the Queue using the DeQueue operation.

And we are back in the main(..) method, where we have performed the DeQueue operation.

queue.deQueue();

And the deQueue() is called,

int deQueue() {
	int element;
	if (isEmpty()) {

		cout <<  "Queue is empty" << endl;
		return -1;
	}
	else {
		element = queueArray[frontElement];

		if (frontElement >= rearElement) {
			queueArray[frontElement] = 0;
			frontElement = -1;
			rearElement = -1;
		}
		else {
			queueArray[frontElement] = 0;
			frontElement++;

		}
		cout <<  "The element " << element << " is removed from the Queue" << endl;
		return (element);
	}
}

At first we check if the Queue is empty or not, using the isEmpty() method.

if (isEmpty()) {

	cout <<  "Queue is empty";
	return -1;
}

In this case, the Queue is not empty. So, we come to the else part.

else {
	element = queueArray[frontElement];

	if (frontElement >= rearElement) {
		queueArray[frontElement] = 0;
		frontElement = -1;
		rearElement = -1;
	}
	else {
		queueArray[frontElement] = 0;
		frontElement++;

	}
	cout <<  "The element "+element+" is removed from the Queue";
	return (element);
}

Inside the else block, we get the front element in the variable element.

Guess why?

Because we are trying to remove the front element from the Queue. So, we store the first element in a variable called element. And return it at the end of method. So, that we could know which element is removed.

Fair enough!

Now, we check if the frontElement is greater than or equal to rearElement. i.e. If both frontElement and rearElement points to the first element, then there is only one element in the Queue.

And in such case we have to remove the front element and make the Queue empty. And as we have seen, when the Queue is empty, both frontElement and rearElement is -1.

if (frontElement >= rearElement) {
	queueArray[frontElement] = 0;
	frontElement = -1;
	rearElement = -1;
}

But in this case, we are trying to remove the third element. And this condition is not satisfied and we come to the else part of it.

else {
	queueArray[frontElement] = 0;
	frontElement++;

}

Where we increase the frontElement, so that it points to the next location and replace 10 with 0.

queueArray[frontElement] = 0;
frontElement++;

Again, we come back to the main(..) method, where we have performed the DeQueue operation once again.

queue.deQueue();

And the deQueue() is called,

int deQueue() {
	int element;
	if (isEmpty()) {

		cout <<  "Queue is empty" << endl;
		return -1;
	}
	else {
		element = queueArray[frontElement];

		if (frontElement >= rearElement) {
			queueArray[frontElement] = 0;
			frontElement = -1;
			rearElement = -1;
		}
		else {
			queueArray[frontElement] = 0;
			frontElement++;

		}
		cout <<  "The element " << element << " is removed from the Queue" << endl;
		return (element);
	}
}

The same way, we check if the Queue is empty or not, using the isEmpty() method.

if (isEmpty()) {

	cout <<  "Queue is empty";
	return -1;
}

In this case, the Queue is not empty. So, we come to the else part.

else {
		element = queueArray[frontElement];

		if (frontElement >= rearElement) {
			queueArray[frontElement] = 0;
			frontElement = -1;
			rearElement = -1;
		}
		else {
			queueArray[frontElement] = 0;
			frontElement++;

		}
		cout <<  "The element " << element << " is removed from the Queue" << endl;
		return (element);
	}

Next, we come to the if statement to check, if there is only one element in the Queue or not?

if (frontElement >= rearElement) {
	queueArray[frontElement] = 0;
	frontElement = -1;
	rearElement = -1;
}

But in this case, we are trying to remove the second element. And this condition is not satisfied and we come to the else part of it.

else {
	queueArray[frontElement] = 0;
	frontElement++;
}

Where we increase the frontElement, so that it points to the next location and replace 20 with 0.

queueArray[frontElement] = 0;
frontElement++;

Now, both frontElement and rearElement is pointing to the same element i.e. 30.

So, the next time when we run the DeQueue operation.

queue.deQueue();

The below condition is satisfied,

if (frontElement >= rearElement) {
	queueArray[frontElement] = 0;
	frontElement = -1;
	rearElement = -1;
}

And both frontElement and rearElement is -1 now.

❮❮ PREV NEXT ❯❯