## Exercises - Review Q2

1. Explain the advantage of using generic type parameters when constructing classes for stacks and queues.

With generic type parameters, one does not need to create a separate class for every type of item one might want to put into a stack or queue -- one can write a single stack or queue class instead that can be used with any collection of objects of a specified type.

2. What methods does a class guarantee exist if it implements the Iterator interface?

hasNext() and next()

3. What is the advantage of implementing the Iterable interface for a class that represents a collection of objects of the same type (e.g., stacks, queues, etc.)?

One advantage is that one can use a "for-each" loop with objects of the resulting collection class. More generally, the Iterable interface allows one to iterate through the items in the collection in question.

4. A class seeks to implement the Iterable interface by providing the iterator() method seen below. The method is intended to use an anonymous inner class to create the value to be returned. What should one type in the blank to complete the code?

public Iterator<Item> iterator() {

return ____________________________
private int pos = 0;

public boolean hasNext() {
return nextPos < size;
}

public Item next() {
return items[nextPos++];
}
};
}

new Iterator<Item>() {

5. A class maintains an instance variable widgets of type Widget[] as shown below. The constructor must initialize this instance variable to be an array of length 10. What should one type in the blank to this end?

public class TenThings<Widget> {

Widget[] widgets;

public TenThings() {
widgets = _____________________;

⋮
}

⋮
}

(Widget[] ) (new Object[10]);
6. What's the cost function $C(n)$ associated with the array accesses (i.e., getting or assigning a value) resulting from the array resizing in pushing $n$ items onto a stack implemented with an array (initially of size 1) that triples in size every time it gets full? For ease of analysis, you may assume that $n = 3^k$ for some positive integer $k$.

Note array resizes occur after pushing the 1st, 3rd, 9th, 27th, etc. item. So the last array resize done in pushing $n=3^k$ items involves copying $3^{k-1}$ values. As copying any single value from the old array to the new resized array involves 2 array accesses (i.e., one to get the value from the old array, one to assign it to one of the cells of the new array), the number of array access is then given by

$C(n) = 2(1 + 3 + 3^2 + 3^3 + \cdots + 3^{k-1})$

This is a geometric series with sum $C(N) = 3^{k} - 1 = N-1 \sim N$

.
7. Suppose an intermixed sequence of stack push and pop operations are performed. The pushes push the integers 0 through 9 in order; the pops print out the returned value. Can the sequence 4 3 2 1 0 5 6 7 8 9 be printed as a result? If the answer is yes, indicate the sequence of pushes and pops needed. If the answer is no, explain why.

Yes. Consider the following sequences of pushed values and pops (indicated by a "-"): 0 1 2 3 4 - - - - - 5 - 6 - 7 - 8 - 9 -

8. Suppose an intermixed sequence of queue enqueue and dequeue operations are performed. The enqueues enqueue the integers 0 through 9 in order; the dequeues print out the returned value. Can the sequence 4 3 2 1 0 5 6 7 8 9 be printed as a result? If the answer is yes, indicate the sequence of enqueues and dequeues needed. If the answer is no, explain why.

No. Given that queues are first-in-first-out (FIFO) structures, the order of the returned values will always be identical to the order values were enqueued. In other words, since the enqueues enqueued the integers 0 through 9 in order, the printing will always result in 1 2 3 4 5 6 7 8 9 (assuming everything is eventually dequeued).

9. Assuming $q$ below is an initially empty queue of integers, show the state of the queue after this code fragment executes. (Make sure to indicate the head and tail of the queue.)

q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
for (int i = 0; i < 4; i++) {
int a = q.dequeue();
int b = q.dequeue();
q.enqueue(a+b);
q.enqueue(a-b);
}

(head) -7 5 -5 (tail)

10. The following letters, in the order they appear, are enqueued into a newly constructed queue implemented using an array. Dashes will cause a dequeue. The underlying array doubles in size when the enqueued character would fill the array and halves its size when a dequeue would leave it one-quarter full. Trace the state of the internal array that results. (Indicate null entries in the array with a period.)

A B C D - E - F G H I

A .
A B . .
A B C .
A B C D . . . .
. B C D . . . .
. B C D E . . .
. . C D E . . .
. . C D E F . .
. . C D E F G .
. . C D E F G H
I . C D E F G H

11. Write a minimal private inner class called Node that can be used to build a linked list of strings.

private class Node {
String string;
Node next;
}


12. Describe two errors in the following code, whose insertSecond() method is intended to insert a new item as the second item of the linked list in question.

public class LinkedListH<Item> {

private class Element {
Item item;
Element next;
}

private Element first;
private int size = 0;

public void insertSecond(Item item) {
Element second = new Element();
second.item = item;

first.next = second;
second.next = first.next.next;
size++;
}

⋮
}


After the statement first.next = second; the local variable second has a null reference for its next instance variable. This breaks the list, "dropping" (and thus permanently losing) any existing 3rd, 4th, 5th, etc. elements.