To practice around with C++11 smart pointers I was trying to implement a simple Queue to go beyond a simple Linked List. The fact that the _first
and _last
nodes are pointed to twice at runtime made me decide to implement them as shared_ptr
.
I was wondering if this was the correct way to implement the data structure.
#include <iostream>
#include <memory>
template <class T>
class Queue
{
private:
class Node
{
public:
const T _data;
std::shared_ptr<Node> _next;
Node(const T& t) : _data{ t } {}
};
std::shared_ptr<Node> _first;
std::shared_ptr<Node> _last;
unsigned _size;
public:
Queue() : _size{ 0 }, _first { nullptr }, _last{ nullptr } {}
~Queue() {}
void add(const T& item);
const T remove();
const unsigned size();
const T peek();
bool isEmpty();
};
template <class T>
bool Queue<T>::isEmpty()
{
return _first == nullptr;
}
template <class T>
void Queue<T>::add(const T& item)
{
std::shared_ptr<Node> new_end = std::make_shared<Node>(item);
if (_last)
{
_last->_next = new_end;
}
_last = new_end;
if (!_first)
{
_first = _last;
}
++_size;
}
template <class T>
const T Queue<T>::remove()
{
if (_first == nullptr) return NULL;
auto ptr = std::move(_first);
_first = ptr->_next;
if (!_first)
{
_last.reset();
}
T val = ptr->_data;
ptr.reset();
--_size;
return val;
}
template <class T>
const unsigned Queue<T>::size()
{
return _size;
}
template <class T>
const T Queue<T>::peek()
{
if (_first) return _first->_data;
return NULL;
}
peek()
function even compiles when it's used.NULL
is unlikely to be convertible toT
(e.g. whenT
isint
orstd::string
). \$\endgroup\$_first
and_last
node. This was purely an exercise on data structures, without worrying about concurrency. I'll try to think about possible implementations for multiple threads! \$\endgroup\$NULL
exactly because I was doing amain()
withT
asint
. If that is the case,nullptr
cannot be used b/c the compiler cannot convertnullptr
toconst int
\$\endgroup\$T
that cannot be constructed with a0
argument, that function will fail to compile. \$\endgroup\$