Java Reference
In-Depth Information
Exercise P15.8. Reimplement the
LinkedList
class of
Section 15.2
so that the
Node
and
LinkedListIterator
classes are not inner
classes.
Exercise P15.9. Add a
previous
field to the
Node
class in
Section
15.2
, and supply
previous
and
hasPrevious
methods in the
iterator.
Exercise P15.10. The standard Java library implements a
Stack
class, but
in this exercise you are asked to provide your own implementation. Do not
implement type parameters. Use an
Object[]
array to hold the stack
elements. When the array fills up, allocate an array of twice the size and
copy the values to the larger array.
Exercise P15.11. Implement a
Stack
class by using a linked list to store
the elements. Do not implement type parameters.
Exercise P15.12. Implement a queue as a circular array as follows: Use
two index variables
head
and
tail
that contain the index of the next
element to be removed and the next element to be added. After an element
is removed or added, the index is incremented (see
Figure 14
).
After a while, the
tail
element will reach the top of the array. Then it
Ȓwraps aroundȓ and starts again at 0Ȍsee
Figure 15
. For that reason, the
array is called Ȓcircularȓ.
public class CircularArrayQueue
{
public CircularArrayQueue(int capacity) {.
. .}
public void add(Object x) {. . .}
public Object remove() {. . .}
public int size() {. . .}
private int head;
private int tail;
private int theSize;
private Object[] elements;
}