## 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.)

```
|    |          |    |          |    |             |    |          |    |
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?

```     (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

```