Queue Implementation in C++ - A Step by Step Guide

A queue is an abstract data structure which contains a collection of elements. These elements can be of any type of data such as strings, characters, numbers etc.

Queue follows the FIFO (First In First Out) rule which basically means the first element that goes in and also comes out first.

Structure of Queue

To create a queue, we will need a few variables:

• An array to store queue elements.
• Track the first and last elements using Front and Rear pointers. Initially set them to -1.

class Queue {
	int *arr, front, rear, size;
public:
	Queue(int _size) {
		size = _size;
		arr = new int[size];
		front = -1;
		rear = -1;
	}
};

At this point, we can start creating different functionality. There are a few basic operations in the queue:

Enqueue

Add an element at the end of the queue. To implement enqueue follow these steps:

• Check if the queue is full.
• Set front to 0 (for the first element).
• Increment the rear and add the new element.

bool isQueueFull() {
	if (front == 0 && rear == size - 1) {
		cout << "Queue is full" << endl;
		return true;
	}
	return false;
}

void enqueue(int value) {
	if (! isQueueFull()) {
		if (front == -1) front = 0;
		rear++;
		arr[rear] = value;
	}
}

Dequeue

Delete an element from the front of the queue. To implement the dequeue follow these steps:

• Check if the queue is empty.
• Return the value at the front and Increment it.
• Reset the values for the last element.

bool isQueueEmpty() {
	if (front == -1) {
		cout << "Queue is empty" << endl;
		return true;    
	}
	return false;
}
  
int dequeue() {
	int item;
	if (! isQueueEmpty()) {
		item = arr[front];
		if (front >= rear) {
			front = -1;
			rear = -1;
		} else {
			front++;
		}
		return item;
	}
	return -1;
}

Peek:

Get the value of the front of the queue without removing it. To implement peek follow these steps:

• Check if the queue is empty.
• Return the value at the front.

int peek() {
	if (! isQueueEmpty()) {
		return arr[front];
	}
	return -1;
}

Display Queue

To display the content of our queue, let's create a function which can iterate over each element.

void print() {
	if (! isQueueEmpty()) {
		for (int i = front; i <= rear; ++i) {
			cout << arr[i] << "  ";
		}
		cout << endl;
	}
}

Congratulations, we have successfully implemented our queue.

Final code

#include <iostream>
using namespace std;

class Queue {
	int *arr, front, rear, size;
public:
	Queue(int _size) {
		size = _size;
		arr = new int[size];
		front = -1;
		rear = -1;
	}
	
	~Queue() {
        delete[] arr;
    }
    
    bool isQueueFull() {
        if (front == 0 && rear == size - 1) {
            cout << "Queue is full" << endl;
            return true;
        }
        return false;
    }

    bool isQueueEmpty() {
        if (front == -1) {
            cout << "Queue is empty" << endl;
            return true;    
        }
        return false;
    }

    void enqueue(int value) {
        if (! isQueueFull()) {
            if (front == -1) front = 0;
            rear++;
            arr[rear] = value;
        }
    }

    int dequeue() {
        int item;
        if (! isQueueEmpty()) {
	        item = arr[front];
	        if (front >= rear) {
		        front = -1;
	            rear = -1;
	        } else {
	            front++;
	        }
	        return item;
        }
        return -1;
    }
    
    int peek() {
	    if (! isQueueEmpty()) {
            return arr[front];
        }
        return -1;
    }

    void print() {
        if (! isQueueEmpty()) {
    		for (int i = front; i <= rear; ++i) {
    			cout << arr[i] << "  ";
    		}
    		cout << endl;
        }
    }
};

int main() {
    Queue q(5);
    q.dequeue(); // queue is empty
    
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.enqueue(4);
    q.enqueue(5);
    q.enqueue(6); // queue is full
    
    q.dequeue();
    q.enqueue(7);
    
    q.print(); // 2 3 4 5 7
    cout << q.peek() << endl; // 2
    q.print(); // 2 3 4 5 7

    return 0;
}