I'm reading through Algorithms Fourth Edition by Sedgewick and doing some of the practice exercises in C++11 instead of Java. Exercise 1.3.29 is to write a Queue that uses a circular linked list, keeping only one Node instance variable (last).
All comments are welcome, but especially ones focusing on advanced C++ techniques as well as the algorithm itself.
#ifndef QUEUE_HH
#define QUEUE_HH
#include <cstddef>
#include <stdexcept>
template<class T>
class Queue {
public:
Queue()
: _last(nullptr)
{}
void enqueue(T value)
{
// Create a new node, not yet linked to anything
Node* node = new Node{value, nullptr};
if(is_empty()) {
// Only node in the list, link it to itself
node->next = node;
} else {
// Link the new node to the start of the list
node->next = _last->next;
// Add the new node to the end of the list
_last->next = node;
}
_last = node;
}
T dequeue()
{
if(is_empty()) {
throw std::out_of_range("Empty queue");
}
// Get the first node in the list
Node* node = _last->next;
// Unlink the node by pointing last to the next node
_last->next = node->next;
// If we're removing the only node in the list, set last node to nullptr
if(node == _last) {
_last = nullptr;
}
// Retrieve the value before deleting the node
int value = node->value;
delete node;
return value;
}
size_t size() const
{
if(is_empty()) {
return 0;
}
// Start at last node, count iterations until last node is reached again
size_t count = 0;
Node* current = _last;
do {
count++;
current = current->next;
} while(current != _last);
return count;
}
bool is_empty() const
{
return _last == nullptr;
}
private:
struct Node
{
T value;
Node* next;
};
Node* _last;
};
#endif // QUEUE_HH