CPSC 225, Spring 2002
Quiz #4, April 22

This is the fourth and final quiz in CPSC 225: Intermediate Programming.

Question 1: Explain the fundamental difference between a stack and a queue.

Answer: Either a queue or a stack contains a sequence of items, and items can only be inserted at one end of the sequence. The difference is how items are removed. For a stack, items are removed from the same end where they are added, so that the item that is removed is the one that was added most recently. This makes a stack a "first in last out" data structure. For a queue, items are removed from the opposite end, so that items are removed in the same order in which they were added. This makes a queue a "first in first out" data structure.

Question 2: Suppose that pile is a stack of ints, with the usual operations push, pop, and isEmpty. Explain the purpose of the following code segment:

      while (true) {
         int N;
         cin >> N;
         if (N == 0)
           break;
         pile.push(N);
      }
      while (pile.isEmpty() == false) {
           cout << pile.pop() << endl;
      }

Answer: This reads a sequence of non-zero integers from the user, stopping when the user enters a zero, and then prints the same integers in the reverse of the order in which they were entered.

Question 3: Postfix expressions can be evaluated using stacks. Show the sequence of stack operations that is used in the evaluation of  15 3 - 2 7 2 + * +.  (Draw the stack at each step.)

Answer: 


         |    |          |    |          |    |             |    |          |    |
   Start |    |          |    |          |    |             |    |          |    |
   with  |    | -------> |    | -------> |    | ----------> |    | -------> |    |
   an    |    |  push 15 |    |  push 3  |  3 |  pop 3      |    |  push 2  |  2 |
   empty |    |          | 15 |          | 15 |  pop 15     | 12 |          | 12 |
   stack +----+          +----+          +----+  push 15-3  +----+          +----+
   
   
                 |    |          |    |           |    |           |    |           
                 |    |          |  2 |           |    |           |    |
        -------> |  7 | -------> |  7 | --------> |  9 | --------> |    |
         push 7  |  2 |  push 2  |  2 |  pop 2    |  2 |  pop 9    | 18 |
                 | 12 |          | 12 |  pop 7    | 12 |  pop 2    | 12 |
                 +----+          +----+  push 7+2 +----+  push 2*9 +----+
                 
                 
                     |    |            |    |
                     |    |            |    |
        -----------> |    | ---------> |    |   The value of the 
         pop 18      |    |   pop 30   |    |     expression is 30.
         pop 12      | 30 |            |    |
         push 12+18  +----+            +----+

Question 4: Suppose that a template class Stack<T> is used to define stacks of items of type T.

     (a) How would you define pile as a variable that represents a stack of items of type int ?

     (b) Write the beginning (the first two lines) of the template class declaration.

     (c) What is the advantage of declaring a template class, rather than an ordinary class, to represent stacks?

Answer: 

     (a)  Stack<int> pile;

     (b)  template<class T>      // ("T" can be any identifier.)
          class Stack {          // ("Stack" could be "Stack<T>.)

     (c)  A single stack template can be used to make stacks of any type
          of item.  If ordinary classes were used, a different class would be
          necessary for each item type, even though these classes would be
          very similar.










David Eck, eck@hws.edu