Quiz 1: 2 questions, 30 minutes

Question 1: array-based stacks
One easy way to implement a stack is as an array, filling the array from positions 0..N-1 as new elements are pushed. A 'topOfStack' index tracks which position in the array currently contains the top element, e.g.

// default size of stack array
const int DefaultSize = 100;

// a stack of ints
class stack {
   protected:
      int *stk;         // array of stack elements
      int size;         // number of elements stack can hold
      int topOfStack;   // current position of top element

   public:
      // dynamically allocate the array 
      //    and initialize topOfStack, size
      Stack(int size = DefaultSize);
     ~Stack();          // deallocate the array
      bool push(int i); // push item i onto top of stack
      bool pop(int &i); // pop top item off into i
      bool isfull();    // returns true iff the stack is full
                        // (no space left in array for elements)
};   

Question 2: biggest value in a tree
Suppose we have a binary tree that is not a binary search tree - i.e. any value can appear anywhere in the tree.

The definition of a tree node is given below, along with the specification for a recursive find function that searches a subtree to find a specific value.
Task: implement the find function.

// the definition of a tree node is as follows:
// struct tnode {
//    int value;
//    tnode *left, *right;
//};

// find searches the subtree rooted at t for the 
//    indicated value, returning true if the subtree
//    contains the value and false otherwise
bool find(tnode *t, int val)