class StrList {
   public:
      StrList();  
     ~StrList();  
      long getListSize();
      bool insertAtBack(string s);
      bool insertAtFront(string s);
      bool removeFromBack(string &s);
      bool removeFromFront(string &s);
   private:
      // who cares, we can't access it anyway ;-)
};

bool Reverse(StrList &L)
{
   // find out how many strings there are to move
   long size = L.getListSize();

   // move the strings from L to a temporary list,
   //    keeping the same order, but
   // returning false if an operation fails
   long i; string s; StrList tmp;
   for (i = 0; i < size; i++) {
       if (!L.removeFromFront(s)) return false
       else if (!tmp.insertAtBack(s)) return false;
   }

   // now put them back in L, but in reverse order,
   // again returning false if anything fails
   for (i = 0; i < size; i++) {
       if (!tmp.removeFromFront(s)) return false
       else if (!L.insertAtFront(s)) return false;
   }

   // everything appears to have worked
   return true;
} 

class Queue {
   public:
      Queue();
     ~Queue();
      bool enqueue(string s);
      bool dequeue(string &s);
      long getQsize();
   private:
      // who cares, we can't access it anyway ;-)
};

bool Reverse(Queue &Q) // recursive solution
{
   // if Q is empty we're done
   if (Q.getQsize() < 1) return true;

   // otherwise take out the front item,
   //    reverse the rest of the queue,
   // and put the front item at the back of
   //    the reversed queue
   // return false if anything fails
   string s;
   if (!Q.dequeue(s)) return false;
   if (!Reverse(Q)) return false;
   if (!Q.enqueue(s)) return false;

   // everything seems to have succeeded
   return true;
} 

// ALTERNATIVE you could instead do the following:
//    get the size of the queue,
//    allocate an array of that many strings,
//    dequeue everything into the array,
//    enqueue everything from the array in the opposite order
//    delete the array

struct Node {
   string info;
   Node *next, *prev;
};

bool Reverse(Node *front, Node *back)
{
   // if front and back are the same then the list is
   //    empty or a single element, either way the list is
   //    the same forward as backward)
   if (front == back) return true;

   // set up pointers to the two ends, and walk each 
   //    towards the middle, swapping values as you go
   Node *f = front;
   Node *b = back;
   do {
      // if f or b hit a null then something has gone wrong
      if ((f == NULL) || (b == NULL)) return false;

      // swap the values in f and b
      string s = f->info;
      f->info = b->info;
      b->info = s;

      // if f->next is b then we've reached the middle
      //    of an even-length list, so we can quit
      if (f->next == b) return true;
   } while (f != b);
   // drops out of the loop when f and b meet in the middle
   //   of an odd-length list
   return true;
} 

class Queue {
   public:
      Queue();
     ~Queue();
      bool enqueue(string s);
      bool dequeue(string &s);
      long getQsize();
   private:
      // who cares, we can't access it anyway ;-)
};

bool Remove(Queue &Q, string s) 
{
   // find out how many items are in the queue
   long size = Q.getSize();

   // keep track of whether or not you found the
   //    target string and whether or not all the
   //    dequeueing and enqueueing was successful
   bool found = false;
   bool success = true;

   // go through the entire queue once,
   //    dequeueing and then re-enqueueing 
   //    each item EXCEPT the target string
   for (long i = 0; i < size; i++) {
       string qs;
       if (Q.dequeue(qs)) {
          if (qs == s) {
             found = true;
          } else if (!Q.enqueue(qs)) {
                // an enqueue didn't work
                success = false;
             }
          }
       } else {
          // a dequeue didn't work
          success = false;
       }
   }
   // return true iff you found the target and
   //    everything else went smoothly
   if (success && found) return true;
   else return false;
}