#include<iostream>
 #include<cassert>
 #include<cmath>
  using namespace std;

   typedef int item_type;

   class queue // circular linked list implementation of queue
    {
     private:
      struct queuenode
       {
        item_type item;
        struct queuenode*next;
       };
      queuenode*dummy;
     public:
      queue();
      bool empty();
      void enqueue(item_type);
      item_type dequeue();
      int size(); // not part of the queue ADT, but useful for debugging
      void traverse(); // not part of the queue ADT, but useful for debugging
    };

  queue::queue()
   {
    dummy = new queuenode;
    dummy->next = dummy;
   }

  bool queue::empty()
   {
    return dummy->next == dummy;
   }

  void queue::enqueue(item_type newitem)
   {
    cout << "enqueue(" << newitem << "):" << endl;
    // missing code here
   }

  int queue::size()
   {
    int result = 0;
    queuenode*runner = dummy->next;
    while(runner != dummy)
     {
      result++;
      runner = runner->next;
     }
    return result;
   }

  void queue::traverse()
   {
    queuenode*runner = dummy->next;
    cout << "traverse: ";
    while(runner != dummy)
     {
      cout << runner->item << " ";
      runner = runner->next;
     }
    cout << endl;
   }

  item_type queue::dequeue()
   {
    // Need to delete unused memory
    assert (!empty());
    queuenode*first = dummy->next;
    int result = first->item;
    dummy->next = first->next;
    return result;
   }

  int main()
   {
    queue Q=queue();
    cout << "Q.size() = " << Q.size() << endl;
    Q.traverse();
    Q.enqueue(4);
    cout << "Q.size() = " << Q.size() << endl;
    Q.traverse();
    Q.enqueue(3);
    cout << "Q.size() = " << Q.size() << endl;
    Q.traverse();
    Q.enqueue(6);
    cout << "Q.size() = " << Q.size() << endl;
    Q.traverse();
    cout << "Q.dequeue() returns " << Q.dequeue() << endl;
    cout << "Q.size() = " << Q.size() << endl;
    Q.traverse();
    Q.enqueue(5);
    cout << "Q.size() = " << Q.size() << endl;
    Q.traverse();
    while(!Q.empty())
     cout << "Q.dequeue() returns " << Q.dequeue() << endl;
    cout << "Q.size() = " << Q.size() << endl;
    Q.traverse();
    return 0;
   }