In an effort to brush up my algorithms and data structure skills I have a done a queue implementation without using built in data structures, i.e. using only arrays. Any comments on this code regarding issues, bad/ good practices and good style would be greatly appreciated.
#include <stdexcept>
#include <cassert>
#include <string>
#include <iostream>
class QueueError : public std::runtime_error {
public:
QueueError(std::string str) : std::runtime_error(str) {};
};
class Queue {
struct LLNode {
int val;
LLNode* next;
};
private:
LLNode** queue = 0;
int limit;
int currSize = 0;
LLNode* first;
LLNode* last;
void swap(const Queue& that);
void destroy();
public:
Queue(int size);
void enqueue(int val);
int dequeue();
virtual ~Queue();
Queue& operator=(const Queue& that);
Queue(const Queue& that);
int size();
};
Queue::Queue(int size) {
if (size <= 0) throw QueueError("Queue size cannot be negative or 0");
this->limit = size;
const int l = this->limit;
queue = new LLNode*[l];
// make it circular
for (int i = 0;i < l; ++i) {
queue[i] = new LLNode();
if ((i - 1) >= 0) {
queue[i-1]->next = queue[i];
}
}
queue[l-1]->next = queue[0];
first = 0;
last = 0;
}
void Queue::enqueue(int val) {
if (currSize == limit) {
throw QueueError(std::string("Queue size cannot exceed limit of queue."));
}
++currSize;
if (last != 0) {
last = last->next;
} else {
first = last = queue[0];
}
last->val = val;
}
int Queue::dequeue() {
if (currSize == 0) {
throw QueueError(std::string("Queue size is 0. Queue cannot be dequeued"));
}
currSize--;
int returnVal = first->val;
if (currSize != 0) {
first = first->next;
} else {
first = last = 0;
}
return returnVal;
}
int Queue::size() {
return currSize;
}
void Queue::destroy() {
if (queue == 0) return;
const int l = this->limit;
for (int i = 0;i < l; ++i) {
delete queue[i];
}
delete[] queue;
}
Queue::~Queue() {
destroy();
}
void Queue::swap(const Queue& that) {
this->limit = that.limit;
const int l = this->limit;
LLNode** tmpQueue = new LLNode*[l];
// make it circular
for (int i = 0;i < l; ++i) {
tmpQueue[i] = new LLNode();
tmpQueue[i]->val = that.queue[i]->val;
if ((i - 1) >= 0) {
tmpQueue[i-1]->next = tmpQueue[i];
}
}
tmpQueue[l-1]->next = tmpQueue[0];
destroy();
queue = tmpQueue;
first = that.first;
last = that.last;
currSize = that.currSize;
}
Queue::Queue(const Queue& that) {
swap(that);
}
Queue& Queue::operator=(const Queue& that) {
if (this != &that) {
Queue tmp(that);
swap(tmp);
}
return *this;
}
int main() {
const int qSize = 200;
const int addVal = 100;
Queue queue(qSize);
for (int i = 0; i < qSize; ++i) {
queue.enqueue(i + addVal);
//std::cout << i + addVal << " ";
}
std::cout << std::endl;
assert(queue.size() == qSize);
// make a copy
Queue queueCopy = queue;
// check if exception is thrown
bool exThrown = false;
try {
queue.enqueue(100);
} catch (QueueError &e) {
exThrown = true;
}
assert(exThrown);
for (int i = 0; i < qSize; ++i) {
int val = queue.dequeue();
//std::cout << val << " ";
assert(val == (i + addVal));
}
exThrown = false;
try {
queue.dequeue();
} catch (QueueError &e) {
exThrown = true;
}
assert(exThrown);
// can I enqueue again?
queue.enqueue(addVal);
assert(queue.dequeue() == addVal);
// check Copy
for (int i = 0; i < qSize; ++i) {
int val = queueCopy.dequeue();
assert(val == (i + addVal));
}
std::cout << "All queue tests run successfully" << std::endl;
}