Answer questions 1 4 on a separate page.

1. Hand trace a stack X through the following operations:

X.push(new Integer(4));

X.push(new Integer(3));

Integer Y = X.pop();

X.push(new Integer(7));

X.push(new Integer(2));

X.push(new Integer(5));

X.push(new Integer(9));

Integer Y = X.pop();

X.push(new Integer(3));

X.push(new Integer(9));

2. Given the resulting stack X from the previous exercise, what would be the result of each of the following?

Y = X.peek();

Y = X.pop();

Z = X.peek();

Y = X.pop();

Z = X.peek();

3. What should be the time complexity of the isEmpty(), size(), and toString() methods?

4. Draw an example using the five integers (12, 23, 1, 45, 9) of how a stack could be used to reverse the order (9, 45, 1, 23, 12) of these elements.