Implement Circular Queue using array

Circular Queue

A circular queue is extended version of normal queue. It uses fixed-size buffer where the last element is connected to the first element.

WIKIPEDIA - Circular buffer

How to Implement a Circular Queue

A circular queue can be implemented using two data structures

• Array
• Linked List

Complexity

• Time Complexity
  • Enqueue : \(O(1)\) 
  • Dequeue: \(O(1)\)
• Space Complexity : \(O(n)\) as the queue is size of \(n\)

Implement Circular Queue using Array

header

//
//  CircularQueue.hpp
//  c++
//

#ifndef CircularQueue_hpp
#define CircularQueue_hpp

#include <iostream>

namespace CircularArrayQueue {
template <typename T>
class Queue {
private:
	// rear of the queue
	int rear;
	// front of the queue
	int front;
	// size of the queue
	int size;
	// array to store the queue
	T* arr;
	
public:
	// constructor
	Queue(int size);
	// destructor
	~Queue();
	// check if the queue is empty
	bool isEmpty();
	// check if the queue is full
	bool isFull();
	// enqueue a value
	void enqueue(T value);
	// dequeue a value
	T dequeue();
	// print all values in the queue
	void printAll();
};
}

#endif /* CircularQueue_hpp */

implementation

//
//  CircularQueue.cpp
//  c++
//

#include "CircularQueue.hpp"
using namespace CircularArrayQueue;

template <typename T>
Queue<T>::Queue(int size) {
	this->rear = 0;
	this->front = 0;
	// The place where front points is always empty.
	// because it is used to determine if it is full.
	// so the real size is size + 1
	this->size = size + 1;
	this->arr = new T[size + 1];
}

template <typename T>
Queue<T>::~Queue(){
	delete[] arr;
}

template <typename T>
bool Queue<T>::isEmpty() {
	return front == rear;
}

template <typename T>
bool Queue<T>::isFull() {
	return (rear + 1) % size == front;
}

template <typename T>
void Queue<T>::enqueue(T value) {
	if(isFull()) return;
	rear = (rear + 1) % size;
	arr[rear] = value;
}

template <typename T>
T Queue<T>::dequeue() {
	if(isEmpty()) return NULL;
	T value = arr[front];
	front = (front + 1) % size;
	return value;
}

template <typename T>
void Queue<T>::printAll() {
	if(isEmpty()) return;
	int i = front;
	while(i != rear) {
		i = (i + 1) % size;
		std::cout << arr[i] << " ";
	}
	std::cout << std::endl;
}