How do we include a struct in a c++ implementation file?

Question

So I am trying to create my own implementation file which contains instructions for a Queue. I decided to use a linked list to implement the Queue class, meaning that I need to use my own Node struct. Unfortunately, I am stuck and don't know how to properly include this within the file.

This is what I have so far:

#include <string>

#ifndef NODE
template <class DataType>
struct Node
{
  DataType data;
  Node *next;
};
#endif

template <class DataType>
class Queue
{
  public: 
    Queue();
    bool isEmpty() const;
    void push(const DataType& parameter);
    bool peek(DataType& parameter) const;
    bool pop(DataType& parameter);
    void makeEmpty();

  private:
    Node<DataType>* front;
    Node<DataType>* end;
};

template <class DataType>
Queue<DataType>::Queue()
: front(0), end(0)
{
}

template <class DataType>
bool Queue<DataType>::isEmpty() const {return 0 == front;}

template <class DataType>
void Queue<DataType>::push(const DataType& parameter)
{
  Node<DataType>* node = new Node<DataType>;
  node->data = parameter;
  node->next = 0;
  if (end) end->next = node;
  else front = node;
  end = node;
}

template <class DataType>
bool Queue<DataType>::peek(DataType& parameter) const
{
  if (0 == front) return false; // failed
  parameter = front->data;
  return true; // success
}

template <class DataType>
bool Queue<DataType>::pop(DataType& parameter)
{
  if (0 == front) return false; // failed
  parameter = front->data;
  Node<DataType>* p = front->next;
  delete front;
  front = p;
  if (front == 0) end = 0;
  return true; // success
}

template <class DataType>
void Queue<DataType>::makeEmpty()
{
  end = 0;
  Node<DataType>* p;
  while (front) 
{ 
  p = front->next; 
  delete front; 
  front = p;
} 
}

I'm not sure if I am enclosing the struct by the #ifndef correctly (i'm not even sure if this is the route I should be taking :/), should I be doing something similar to this or should I be doing something else with the code for the struct?

Answer 1

You can just drop the #ifdef/#endif entirely

This is a class template and it may occur many times in several tranlation units, as long as all the occurrences are identical (One Definition Rule)

Alternative

Since Node<> is purely a private concern, I'd make it a nested struct.

Here's a little demo making this more 'modern C++' style.

Edit Thanks to @R.MartinhoFernandes for showing a few more improvements and for reviewing this.

#include <memory>

template <typename T>
struct Queue {
    Queue() : front(), end(/*nullptr*/) {}

    // Copy-And-Swap idiom
    // see http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Copy-and-swap
    // or  http://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom
    void swap(Queue& q) noexcept {
        using std::swap;
        swap(q.front, front);
        swap(q.end, end);
    }
    Queue(Queue const& q) : front(), end() {
        for(auto it=q.front.get(); it; it=it->next.get())
            push(it->data);
    }
    Queue& operator=(Queue q) {
        std::swap(*this, q);
        return *this;
    }
    // end Copy-and-swap

    // prevent stack overflows in ~Node if the list grows large (say >1k elements) 
    ~Queue() { clear(); }

    bool isEmpty() const { 
        return !front; 
    }
    void push(T const& data) {
        Ptr node(new Node(data));
        if (end)
            end->next = std::move(node);
        else
            front = std::move(node);
        end = node.get();
    }
    bool peek(T& data) const {
        if(front) data = front->data;
        return front.get();
    }
    bool pop(T& data) {
        if(!front) return false;

        data           = front->data;
        front          = std::move(front->next);
        if(!front) end = nullptr;

        return true;
    }
    void clear() {
        end = nullptr;
        while(front) front = std::move(front->next);
    }
private:
    struct Node;
    typedef std::unique_ptr<struct Node> Ptr;
    struct Node {
        Node(T data) : data(std::move(data)), next() {}
        T   data;
        Ptr next;
    };
    Ptr front;
    Node* end;
};

#include <iostream>

int main(int argc, const char *argv[]) {
    Queue<int> test;
    test.push(1);
    test.push(2);
    test.push(3);
    test.push(5);
    test.clear();
    test.push(32028);
    test.push(10842);
    test.push(1839);
    test.push(23493);
    test.push(9857);
    int x;
    test.peek(x);
    while(test.pop(x)) {
        std::cout << x << '\n';
    }
}

Note: Perhaps the code in push has been golfed a bit too far, but hey, it shows you how modern C++ requires much less handholding (even without std::make_unique).

Note how I think Clang correctly handles the following version (i.e. with implicit std::move):

void push(const DataType& parameter) {
    end = ((end? end->next : front) = Ptr(new Node(parameter))).get();
}

I'm not quite sure why gcc rejects it.