// from pp. 319 ff in Louden's text

// note that access to the link field is not needed by any derived
//   class, so that this field may be "private" rather than "protected"

#include <iostream.h>

class linkableObject							{
private:
  linkableObject *link;
public:
  virtual void display(void)=0;     // this is not in the Louden text
  // void display(void) {}          // Ex: what if this is used instead?
  linkableObject (void) {link=0;}
  linkableObject (linkableObject *p) {link=p;}
  linkableObject *next (void) {return link;}
  void linkto(linkableObject *p) {link=p;}				};


class queue								{
protected:
  linkableObject *rear;
public:
  queue(void) {rear=0;}
  int empty(void) {return rear==0;}
  void enqueue(linkableObject *item);
  void dequeue(void);
  linkableObject* front(void)
    {return rear->next();}
  ~queue(void);								};

void queue::enqueue(linkableObject *item)				{
if (empty())							{
  rear=item;
  rear->linkto(item);						}
else                                                            {
  item->linkto(rear->next());
  rear->linkto(item);
  rear=item;							}	}

void queue::dequeue(void)						{
linkableObject *temp=front();
if (temp==rear)
  rear=0;
else
  rear->linkto(temp->next());						}

queue::~queue(void)							{
linkableObject *temp=rear;
if (temp==0)
  return;
do 								{
  linkableObject *temp2=temp;
  temp=temp->next();
  delete temp2;							}
while (temp!=rear);							}

class linkableInt : public linkableObject				{
private:
  int item;
public:
  int data(void) {return item;}
  void setdata(int x)  {item = x;}
  void display(void) {cout << "int:" << item;}                                    };

class linkableChar : public linkableObject				{
private:
  char item;
public:
  int data(void) {return item;}
  void setdata(int x)  {item = x;}
  void display(void) {cout << "char:" << item;}					};

class traversable_queue:public queue					{
public:
  void traverse(void);							};

void traversable_queue::traverse(void)					{
linkableObject *temp=rear;
if (temp==0)
  return;
do    								{
  temp->display();
  temp=temp->next();
  if (temp==rear)
    cout << " end of traversal" << endl;
  else
    cout << " ";                                                  }
while (temp!=rear);							};

int main()                                                              {
traversable_queue q;
linkableObject *o;
linkableInt *i=new linkableInt;
i->setdata(42);
q.enqueue(i);
linkableChar *c=new linkableChar;
c->setdata('a');
q.enqueue(c);
i=new linkableInt;
i->setdata(43);
o=i;                      // note that i=o would give a compiler error
q.enqueue(o);
c=new linkableChar;
c->setdata('b');
o=c;
q.enqueue(o);
q.traverse();
return 0;								}