1. I am going to execute this code:
   Stack<int> s;
   s.push(1);
   s.push(2);
   s.push(3);
   cout << s.pop( );
   
   A. Suppose that s is represented by a partially filled array. Draw the
      state of the private member variables of s after the above code:
           _______            __________________________________
      used|       |      data|      |      |      |      |      |
          |_______|          |______|______|______|______|______|
                               [0]    [1]    [2]    [3]    [4]

   B. Suppose that s is represented by a linked list. Draw the linked list
      after the above code:
               _______      
      head_ptr|       |  
              |_______|     


2. I am going to execute this code:
   Queue<int> q;
   q.insert(1);
   q.insert(2);
   q.insert(3);
   q.insert(4);
   q.insert(5);
   cout << q.get_front( );
   cout << q.get_front( );
   q.insert(6);
   
   A. Suppose that q is represented by a partially filled array with a
      CAPACITY of 5. Draw the state of the private member variables of q
      after the above code:
            _______            __________________________________
      front|       |      data|      |      |      |      |      |
           |_______|          |______|______|______|______|______|
                                [0]    [1]    [2]    [3]    [4]
            _______
      rear |       |
           |_______|

   B. Suppose that q is represented by a linked list. Draw the linked list
      after the above code:
               _______                                       _______      
      head_ptr|       |                                     |       |rear_ptr
              |_______|                                     |_______|


3. Implement the following function. You may use the Stack template class and
   the Stack operations of push, pop, peek, is_empty, and size. 
   You may also use cin.peek( ) and use "cin >> i" to read an integer.

   int evaluate_postfix_from_cin( )
   // NORMAL BEHAVIOR OF THE FUNCTION:
   // Normally, the next input line of cin is a properly formed postfix
   // expression containing positive integers, the binary operations
   // + and *, and spaces. In this case, the function reads the line 
   // (including '\n') and returns the value of the postfix expression.
   // ERROR CONDITIONS:
   // If the postfix expression is improperly formed, or if there are
   // illegal characters on the input line, then the function immediately
   // returns zero. In this case, some of the input line might be unread.
   {
      int i;
      Stack<int> s;












































4. Suppose that you want to implement the PriorityQueue so that insertions
   occur in constant time, but get_front requires linear time. You will use
   these class definitions:

   class PriorityQueue
   {
      typedef double Item;
      ...
   private:
      Node *head_ptr;
   };

   struct Node
   {
       PriorityQueue::Item data;
       unsigned int priority;
       Node *link;
   };

   A. Write the PriorityQueue's insert member function:
   void PriorityQueue::insert(const Item& entry)
   {






































4. (Continued)
   B. This question continues from the previous page. Write a description
      of the linear time get_front member function. Use drawings to
      show a typical example of how get_front will work when the 
      PriorityQueue has five items with priorities 1, 10, 3, 10, and 6.























































5. Write a recursive function that has one parameter which is a size_t value
   called x. The function prints x asterisks, followed by x exclamation points.
   Do NOT use any loops. Do NOT use any variables other than x.

























































6. Implement the following function. Do not use any local variables or loops.

void pattern(unsigned int n)
// Precondition: n > 0;
// Postcondition: The output consists of lines of integers. The first line
// is the number n. The next line is the number 2n. The next line is
// the number 4n, and so on until you reach a number that is larger than
// 4242. This list of numbers is then repeated backward until you get back
// to n.

Example output with n = 840:
840
1680
3360
6720
6720
3360
1680
840

{
    assert(n > 0);







































7. This question will help identify the A+ students. If you don't solve this
problem, then don't worry, but do think about the problem after class.

This question involves a game with teddy bears. The game starts when I give you
some bears. You can then give back some bears, but each time that you give back
some bears you must give back half of all your bears. (If you have n bears, and
n is even, then you will give back n/2. If n is odd, then you may round down to
give back (n-1)/2 bears, or you may round up to give back (n+1)/2 bears.) The
goal of the game is to end up with EXACTLY 42 bears.

For example, suppose that you start with 337 bears. Then you could make
these moves:
    Start with 337 bears.
    Give back 168 (which is half of 337, rounding down) to leave 169 bears.
    You now have 169 bears.
    Give back 85  (which is half of 169, rounding up) to leave 84 bears.
    You now have 84 bears.
    Give back 42 (which is half of 42), to leave 42 bears.
    You have reached the goal!

Write a recursive function to meet this specification:
bool bears(int n)
// Postcondition: A true return value means that it is possible to win
// the bear game by starting with n bears. A false return value means that
// it is not possible to win the bear game by starting with n bears.
// Examples:
//   bear(337) is true (as shown above)
//   bear(42) is true
//   bear(83), bear(84) and bear(85) are all true
//   bear(52) is false
//   bear(41) is false
{
    // Hint: To test whether n is even, use the expression ((n % 2) == 0).