Answer to Question 35C-5

  //=====================================
  //          shrink
  //=====================================
  // Halve the physical size of the 
  // array for queue q.
  //=====================================

  void shrink(Queue& q)
  {
    int n = q.physicalSize;

    //--------------------------------------------
    // Copy the old array into a new array.  Move
    // the front to index 0 in the new array.
    //--------------------------------------------

    int  newsize = n/2;
    int* newA = new int[newsize];
    for(int i = 0; i < q.load; i++)
    {
      newA[i] = q.contents[(q.front + i) % n];
    }

    //--------------------------------------------
    // Install the new array.
    //--------------------------------------------

    delete [] q.contents;
    q.contents     = newA;
    q.front        = 0;
    q.physicalSize = newsize;
  }

  //=====================================
  //          removeFirst
  //=====================================
  // Remove and return the first item in
  // queue q.  If q is empty, return -1
  // and do not modify q.
  //=====================================

  void removeFirst(Queue& q)
  {
    if(isEmpty(q))
    {
      return -1;
    }
    else 
    {
      int result = q.contents[q.front];
      if(4*q.load <= q.physicalSize)
      {
         shrink(q);
      }
      q.front = (q.front + 1) % q.physicalSize;
      q.load--;
      return result;
    }
  }