Реализация CircularQueue с использованием связанного списка в C++
В настоящее время я делаю проект, который потребует от меня реализации структуры данных CircularQueue в C++. Вот что у меня так далеко:
template<typename Type> class CircularQueue {
template<typename Type> struct CQNode {
Type head;
CQNode* tail;
CQNode() {
this->head = NULL;
this->tail = NULL;
}
CQNode(Type head, CQNode* tail = NULL) {
this->head = head;
this->tail = tail;
}
};
private:
CQNode<Type>* front;
CQNode<Type>* rear;
CQNode<Type>** circularQueue = NULL;
int MAX = 0;
int currentSize = 0;
protected:
public:
/**********************************************************/
/********************** CONSTRUCTORS **********************/
/**********************************************************/
/**
* @brief
*
* [DETAILED DESCRIPTION]
*
* @param capacity integer size capacity of CircularQueue object to be instantiated
*/
CircularQueue(int capacity) {
// Set the maximum queue capacity to the size passed to constructor
this->MAX = capacity;
// Locally set the limit (to be used as array of CQNode size) to MAX
const int limit = this->MAX;
// Create a pointer array of CQNode with size limit and assign to this->circularQueue
this->circularQueue = new CQNode<Type>*[limit];
// Loop over queue capacity, implementing CircularQueue type structure
for (int i = 0; i < limit; i++) {
// set i'th element of circularQueue array to a new CQNode struct
this->circularQueue[i] = new CQNode<Type>();
// if the value of i is greater than 0, assign the tail of the (i-1)'th element
// of circularQueue to i'th element of circularQueue, thereby implementing the Queue
// FIFO type data structure
if (i > 0) {
this->circularQueue[i - 1] = this->circularQueue[i];
}
// otherwise, if i is equal to the capacity - 1 (i.e. the last elementt of circularQueue array),
// then set the tail of the last element of circularQueue to the first element of circularQueue,
// thereby implementing the circular nature of this queue data structure
else if (i == (limit - 1)) {
this->circularQueue[i - 1]->tail = this->circularQueue[0];
}
}
this->front = NULL;
this->rear = NULL;
}
/**********************************************************/
/********************** DESTRUCTORS ***********************/
/**********************************************************/
/**
* @brief
*
* [DETAILED DESCRIPTION]
*
*/
~CircularQueue() {
//TODO: Destroy Queue
}
/********************************************************/
/*********************** GETTERS ************************/
/********************************************************/
CQNode<Type>* peekFront() {
return this->front;
}
CQNode<Type>* peekRear() {
return this->rear;
}
Type peekHeadOfFront() {
if (this->front != NULL)
return this->front->head;
}
int getCurrentSize() {
return this->currentSize;
}
bool isEmpty() {
return this->rear == NULL;
}
/**********************************************/
/****************** TOSTRING ******************/
/**********************************************/
/**
* @brief
*
* [DETAILED DESCRIPTION]
*
* @return string representation of this CircularQueue object
*/
string toString() {
string temp = "[";
CQNode<Type>* tempNode = this->front;
int i = 0;
while (tempNode != NULL && i < this->currentSize) {
i++;
//cout << temp << endl;
if (tempNode->tail != NULL) {
temp += std::to_string(tempNode->head) + ", ";
}
else {
temp += std::to_string(tempNode->head);
}
tempNode = tempNode->tail;
}
temp += "]";
return temp;
}
/********************************************************/
/******************* QUEUE OPERATIONS *******************/
/********************************************************/
/**
* @brief
*
* [DETAILED DESCRIPTION]
*
* @param item Object to enqueue to this instance of CircularQueue
* @return The item of data structure "Type" enqueued upon this CircularQueue instance
*/
Type enqueue(Type item) {
// if the currentSize is greater than the maximum allowed capacity,
// throw a CircularQueueException
if (this->currentSize == this->MAX) {
throw CircularQueueException("Circular queue is full, cannot enqueue any more objects!");
}
// if the front of this CQ object is null, assign first element of circularQueue array to
// front of queue and set the rear to the front (single-element queue)
if (this->front == NULL) {
//this->front = new CQNode<Type>(item);
this->front = this->circularQueue[0];
this->rear = this->front;
}
// else if the front is not-null, assign the tail of the rear of this CQ object
// to a new CQNode with head = item, and shift the new rear to tail of old rear
else {
this->rear->tail = new CQNode<Type>(item);
this->rear = this->rear->tail;
if (this->currentSize == (this->MAX - 1))
this->rear->tail = this->front;
}
this->currentSize++;
return item;
}
/**
* @brief
*
* [DETAILED DESCRIPTION]
*
* @return The item of data structure "Type" dequeued from this CircularQueue instance
*/
Type dequeue() {
// Create a pointer to a CQNode initialised as NULL
// this variavle will store the dequeued node
CQNode<Type>* dequeuedNode = NULL;
// if rear is empty, throw a CircularQueueException
if (this->rear == NULL) {
throw CircularQueueException("Circular queue is already empty, cannot dequeue any objects!");
}
else {
// decrement currentSize of this CircularQueue instance by 1
this->currentSize--;
// assign front of this CircularQueue to dequeuedNode
dequeuedNode = this->front;
// set the new front of the queue to the tail of the current front
this->front = this->front->tail;
}
return dequeuedNode->head;
}
};
Это хорошая реализация для такой структуры до сих пор? Пожалуйста, укажите любые плохие методы кодирования или потенциальные проблемы, которые вы можете увидеть с этим кодом.
Обратите внимание, что моя функция toString() предназначена для печати только одного "круга" очереди, если есть лучший способ сделать toString() для CircularQueue, тогда, пожалуйста, упомяните об этом.