// -*- C++ -*-

#ifndef __QUEUE_H
#define __QUEUE_H

#include <assert.h>


template <class T>
class queue
{
public:
    queue();
    ~queue();

    void enqueue(const T& in);

    bool empty() const { return !head; }
    
    // Copy into the parameter
    void dequeue(T& out);
    void front(T& out);
    
private:
    // Don't copy me or pass me by value!
    queue(const queue& that);
    queue& operator=(const queue& that);

    struct node
    {
        node(const T& in) : data(in), next(0) { }
        T data;
        node* next;
    };

    node* head;
    node* tail;
};


template <class T>
queue<T>::queue() : head(0), tail(0)
{
}


template <class T>
queue<T>::~queue()
{
    while (head)
    {
        tail = head->next;
        delete head;
        head = tail;
    }
}


template <class T>
void queue<T>::enqueue(const T& data)
{
    node* n = new node(data);
    if (head)
    {
        tail->next = n;
        tail = n;
    }
    else
        head = tail = n;
}


template <class T>
void queue<T>::front(T& data)
{
    assert(!empty());
    data = head->data;
}


template <class T>
void queue<T>::dequeue(T& data)
{
    assert(!empty());
    data = head->data;
    node* victim = head;
    head = head->next;
    delete victim;
}


#endif