Templated queue implementation

Question

I wrote an implementation for a simple queue in C++ (for practice, since there's an stl queue). I've been trying to focus on memory management and the rule of three. Any suggestions/improvements?

(Personally, I feel like there has to be a better way to overload the copy assignment operator).

#ifndef QUEUE_H
#define QUEUE_H

#include "assert.h"

#define NULL 0


template <typename T>
class Queue
{
 public:
  Queue();
  Queue(const Queue& other);
  ~Queue();

  void enqueue(T data);
  T    dequeue();

  bool isEmpty() { return (front_ == back_); }

  Queue& operator=(const Queue& other);

 private:
  struct node
  {
    T     data;
    node* next;
  };

  node* front_;
  node* back_;
};


template <typename T>
Queue<T>::Queue()
{
  front_ = new node();
  back_  = front_;
}


template <typename T>
Queue<T>::Queue(const Queue<T>& other)
{
  front_     = new node();
  back_      = front_;
  node* temp = other.front_;

  while (temp != other.back_)
  {
    enqueue(temp->data);
    temp = temp->next;
  }
}


template <typename T>
Queue<T>::~Queue()
{
  while (!isEmpty()) { dequeue(); }
}


template <typename T>
void Queue<T>::enqueue(T data)
{
  back_->data = data;
  back_->next = new node();
  back_       = back_->next;
}


template <typename T>
T Queue<T>::dequeue()
{ 
  assert(!isEmpty());

  node* temp = front_;
  T     data = front_->data;  
  front_     = front_->next;

  delete temp;
  return data;
}


template <typename T>
Queue<T>& Queue<T>::operator=(const Queue<T>& other)
{
  if (this != &other)
  {
    node* temp = other.front_;

    while (!isEmpty()) { dequeue(); }
    while (temp != other.back_)
    {
      enqueue(temp->data);
      temp  = temp->next;
    }
  }
  return *this;
}

#endif

Answer 1

Use the correct headers

#include "assert.h"

should be

#include <cassert>

since you're writing C++. C++ provides special headers for all C headers, they generally start with a 'c' and have the '.h' removed at the end. Prefer these.

Also system headers, should always use <> rather than "".

Your definition of NULL is unsafe

NULL is typically reserved to use in the context of pointers. Defining NULL as you do means that NULL is not of a pointer type and you can pass NULL as an integer for example this is not desirable.

If you must define NULL you should do it like this:

#ifndef NULL
#define NULL (reinterpret_cast<void*>(0))
#endif

but really most likely it is already included by one of your other headers (<cstddef>, <clocale>, <cstdio>, <cstdlib>, <cstring>, <ctime> and anything that includes those, so pretty much everything).

If you are using C++11 or newer you should use nullptr instead of NULL.

Style

I personally would name node with the same convention as your other classes, Node. I'm also not a big fan of using _ as a suffix for class members but that is personal taste.

Pass template arguments by constant reference

As T can be just about anything, you should pass all Ts by const reference (const T&) to avoid possibly expensive copies.

Const correctness

Methods that do not modify the state of the queue should be declared const.

bool isEmpty()

should be

bool isEmpty() const

being const correct allows you to get compile time errors if you unintentionally modify something you didn't intend to. It's a good habit.

Construct objects as close as possible to their final state

Your node class should have a constructor that initialises the data member. This will reduce some code for you.

Put the sentinel in the class.

Allocating the sentinel node on the heap in your constructor is unnecessary. Prefer to have it be a member variable. It is a good practice to not allocate on the heap when it suffices to use a local or member variable.

Avoid code duplication

The copy constructor and copy assignment operator are typical places where one usually gets code duplication.

I would suggest using the Copy and Swap Idiom for implementing the assignment operator.

And welcome to the site!

Answer 2

Most implementations of Queues I've seen offer a public top() or front() method to return the first element without dequeuing it.

This can be somewhat useful in multiple use-cases