//LinkQueue by Jason Winnebeck (gillius@webzone.net, 
// http://www.rit.edu/~jpw9607/).  You are free to use this code
// in your programs and modify it freely.
// 5/15/2000

//I realize the code is pretty hackish.  I made it really fast simply
//for the simple functionality.

template <class T>
class LinkQueueLink {
public:
  LinkQueueLink(LinkQueueLink<T>* next2, T* data2) : next(next2), data(data2) {}

  LinkQueueLink<T>* next;
  T* data;
private:
};

template <class T>
class LinkQueue {
public:
  LinkQueue() {
    first = last = NULL;
    len = 0;
  }
  ~LinkQueue() {
    while (!isEmpty())
      delete pop();
  }

  bool isEmpty() { return (len == 0); }
  int length() { return len; }

  T* peek() {
    //Returns a pointer to the front data.  Do not delete this pointer,
    //although it IS possible to modify the data behind the pointer.
    //NULL is returned of the list is empty
    if (!isEmpty())
      return first->data;
    else
      return NULL;
  }

  T* pop() {
    //Returns a pointer to the front data.  LinkQueue hands responsiblity
    //for deleting data to caller.  Front element is removed from list.
    //NULL is returned if the list is empty.
    if (!isEmpty()) {
      T* ret = first->data;
      LinkQueueLink<T>* temp = first;
      first = first->next;
      delete temp;
      len--;
      return ret;
    } else
      return NULL;
  }

  void add(T* newData) {
    //give this function a pointer to an allocated portion of memory.
    //LinkQueue is responsible for its destruction with the delete command.
    //No data is copied.
    if (isEmpty())
      first = last = new LinkQueueLink<T>(NULL, newData);
    else {
      last->next = new LinkQueueLink<T>(NULL, newData);
      last = last->next;
    }

    len++;
  }

private:
  //LinkQueue may NOT be copied
  operator = (const LinkQueue& o);
  LinkQueue(const LinkQueue& o);

  LinkQueueLink<T>* first;
  LinkQueueLink<T>* last;

  int len;
};