#include<iostream.h>
#include<fstream.h>
#include<strings.h>
#include<stdlib.h>

// QueueADT.C
// burton rosenberg, 15 April 1997

// Introduces Object Oriented Programming,
// and illustrates the Queue ADT.

struct Node {
   char * content ;
   Node * next ;
} ;

class Queue {
private:
   Node * head ;
   Node * tail ;
   int queueSize_ ;

public:
   // Methods (a.k.a. messages or functions)

   // Constructor
   Queue() ;

   // Predicates
   int queueSize() ;

   // Data Mutators
   void insert( char * ) ;
   char * remove() ;

} ;


// Implementation of ADT

Queue::Queue() {
   head = tail = NULL ;
   queueSize_ = 0 ;
}

Queue::queueSize() {
    return queueSize_ ;
}

void Queue::insert( char * w ) {

   // prepare node for insertion
   Node * n = new Node ;
   char * s = new char[strlen(w)+1] ;
   n->content = strcpy( s, w ) ;
   n->next = NULL ;

   // insert after current tail
   if ( queueSize_ == 0 ) {
      // special case: adding to an empty queue
      head = tail = n ;
   }
   else {
      // general case: queue not empty
      tail->next = n ;
      tail = n ;
   }
   queueSize_ ++ ;

   return ;
}

char * Queue::remove() {

   if ( queueSize_ == 0 ) return NULL ;

   // assume non-empty 
   char * s = head->content ;
   Node * h = head ;
   head = head->next ;
   delete h ; // return Node to free-store

   queueSize_ -- ;
   if ( queueSize_ == 0 ) // adjust tail pointer for empty queue
      tail = NULL ;

   return s ;
}

const int BUFFER_N = 500 ;

int main (int argc, char * argv[] ) {
   char buffer[BUFFER_N] ;
   Queue * myQueue = new Queue ; // constructor is called

   cout << "Welcome to " << argv[0] << endl ;
   cout << "^D to exit." << endl ;

   char * cmd, * arg ;
   cin.getline(buffer, BUFFER_N) ;

   while ( cin ) {

      if ( (cmd = strtok( buffer, " \t\n")) != NULL ) {
      
         switch (cmd[0] ) {

            case 'I':
            case 'i':
               // insert command
               if ( (arg = strtok( NULL, " \t\n")) == NULL ) {
                  cout << "Insert error: No item to insert." << endl ;
               }
               else {
                  myQueue->insert(arg) ;
                  cout << "Insert: " << arg << endl ;
               }
               break ;

            case 'R':
            case 'r':
               // remove command
               if ( myQueue->queueSize() == 0 ) {
                  cout << "Remove error: Queue is empty." << endl ;
               }
               else {
                 arg = myQueue->remove() ;
                 cout << "Remove: " << arg << endl ;
                 delete [] arg ; // array delete
               }
               break ;

            default :
                cout << "Unknown command. Commands are:\n" ;
                cout << "   I xxx   to insert word xxx\n" ;
                cout << "   R       to remove and printed removed word\n" ;
                cout << "  ^D       (control-D) to exit\n" ;
         }
      }
      cin.getline(buffer, BUFFER_N) ;
    }

    if ( myQueue->queueSize() > 0 ) {
       cout << "Unloading queue..." << endl ;
       do {
          cout << "Remove: " << myQueue->remove() << endl ;
       } while ( myQueue->queueSize() > 0 ) ;
    }

}