If you have not done so already, fork and clone the repo at https://github.com/Grinnell-CSC207/linear-structures.
Driver: A
Write a new class with a main method that creates a priority queue
of strings that is ordered by string length, adds a few strings,
and then removes the strings.
You may use either java.util.PriorityQueue or BuiltinPriorityQueue
for your priority queue.
You should use an anonymous inner class to build the comparator for the
priority queue. If your compare method is presented with two
equal-length strings, it should compare them alphabetically.
Driver: A
As you may recall, the ArrayBasedStack class has two fields, an
array called values and an integer called size.
a. Sketch (that is, make notes on but do not write the Java code for)
an iterator for the ArrayBasedStack class. (You do not need to turn
in your notes._
b. Compare your answer to the iterator presented in ArrayBasedStack.java.
Driver: B
As you may recall, the LinkedQueue class has two fields,
front and back, each of which reference a node.
a. Sketch (that is, make notes on but do not write the Java code for)
an iterator for the LinkedQueue class. (Once again, you do not need
to turn in your notes.)
b. Compare your answer to the iterator presented in LinkedQueue.java.
Driver: B
You may have noted that the ArrayBasedQueue class lacks an iterator.
Write one. Your iterator should present the elements starting and
the front of the queue and ending at the back.
Your code will likely look something like the following.
public ArrayBasedQueue<T> implements ... {
// ...
Iterator<T> iterator() {
return new ArrayBasedQueueIterator<T>(this);
} // iterator()
// ...
} // ArrayBasedQueue<T>
private ArrayBasedQueueIterator<T> implements Iterator<T> {
ArrayBasedQueue<T> abq;
int i;
public ArrayBasedQueueIterator(ArrayBasedQueue<T> abq) {
this.abq = abq;
this.i = 0;
}
// ... this.abq.values[pos] ...
} // ArrayBasedQueueIterator<T>
Upload your answers to exercises 1 and 4. That is, upload the new file you created in exercise 1 and the modified version of ArrayBasedQueue.
If you find that you have extra time, you should attempt the following.
remove in array-based queuesYou may have noted that java.util.Iterator provides a remove method.
Implement that method for your iterator for ArrayBasedQueue.
Convert your iterator for array-based queues to an anonymous inner class. You should now be able to do without the field that refers back to the associated array-based queue.
remove in linked queuesImplement the remove method for the iterator for LinkedQueue.
Note: This is a pain in the neck and may involve special cases.
This lab was newly written in spring 2019. It was revised somewhat in Fall 2023 and Spring 2024.