/* Code of Figure 10.12, pages 439-440 from
   Kenneth C. Louden, Programming Languages
   Principles and Practice 2nd Edition
   Copyright (C) Brooks-Cole/ITP, 2003
   Test code from page 438 also added
*/

#include <iostream>
using std::cout;
using std::endl;

template<typename T> class Queue
{
public:
  Queue() : rear(0) { }

  int empty()
  { return rear == 0; }

  void enqueue (T item);

  void dequeue ();

  T front()
  { return rear->next->data; }

  ~Queue();

protected:
  class Linkable
  {
  public:
    T data;
    Linkable* next;
  };

  Linkable* rear;
};

template <typename T>
void Queue<T>::enqueue(T item)
{ Linkable* temp = new Linkable;
  temp->data = item;
  if (empty()) 
  { rear = temp;
    rear->next = temp;
  }
  else
  { temp->next = rear->next;
    rear->next = temp;
    rear = temp;
  }
}

template <typename T>
void Queue<T>::dequeue()
{ Linkable* temp = rear->next;
  if (temp == rear) rear = 0;
  else rear->next = rear->next->next;
  delete temp;
}

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

int main()
{ Queue<int> q;
  q.enqueue(42);
  int x = q.front();
  q.dequeue();
  cout << x << endl;
  if (q.empty()) cout << "ok!" << endl;
  else cout << "oops!" << endl;
  return 0;
}