Java Reference
In-Depth Information
Since frontIndex and backIndex can continue to grow, they might become too large to represent. To reduce
the chance of this happening, set frontIndex to 0 and backIndex to - 1 whenever the implementation detects an
empty queue. Note that adding to a full queue invokes ensureCapacity , which sets frontIndex to 0 and backIn-
dex to the index of the entry at the back of the queue.
Complete this array-based implementation of the ADT queue.
4.
Implement the ADT queue by using a circular linked chain, as shown in Figure 11-12. Recall that this chain has
only an external reference to its last node.
5.
Consider a new kind of queue that allows only a single copy of an object in the queue. If an object is added to the
queue, but it is already there, leave the queue unchanged. This queue has another operation moveToBack that takes
an object in the queue and moves it to the back. If an object is not in the queue, the operation adds it at the back of
the queue.
Create an interface NoDuplicatesQueueInterface that extends QueueInterface . Then write an array-based
implementation of NoDuplicatesQueueInterface . Finally, write a program that adequately demonstrates your
new class.
6.
Implement the ADT deque by using an array to contain its entries. Expand the array dynamically when necessary.
7.
One difficulty with implementing the doubly linked chain described in Segment 11.35 is the number of special
cases that occur at the beginning and end of the chain. You can eliminate these cases if the chain is never empty.
Thus, you begin each chain with a dummy node that you do not use for data.
Revise the implementation of the deque given in this chapter by using a dummy node.
8.
Use a circular doubly linked chain (see the note at the end of Segment 11.40) to implement the ADT deque.
9.
Repeat the previous project, but add a dummy node to the chain, as Project 7 describes.
10.
In Project 5 you created a queue that does not allow duplicates. In this project you will create a deque that does not
allow duplicates. The function of the deque's operations addToBack and addToFront should be analogous to the
changed enqueue method in Project 5. Add two operations, moveToBack and moveToFront .
Create an interface NoDuplicatesDequeInterface that extends DequeInterface . Then write a linked imple-
mentation of NoDuplicatesDequeInterface . Finally, write a program that adequately demonstrates your new class.
11.
Implement the ADT priority queue by using an array, as pictured in Figure 11-20a.
12.
Implement the ADT priority queue by using a chain of linked nodes, as pictured in Figure 11-20b.
13.
Revise the interface for the ADT priority queue, as given in Segment 10.19 of the previous chapter, by replacing
the method add with the following method:
public void add(T newEntry, Comparable<? super T> priorityValue)
The client provides an entry and its priority value to this method. The priority queue does not use newEntry 's compareTo
method to assess its priority. Implement this version of the priority queue.
14.
In Project 5 you created a queue that does not allow duplicates. In this project you will create a priority queue that
does not allow duplicates. The function of the add operation should be analogous to the changed enqueue method
in Project 5. In this case, the test for equals should not include the priority, so the header of the add method should
be changed to the one given in the previous project. A new operation move will change the priority of a given item,
if it is already in the priority queue. If the item is not in the priority queue, move will add it with the given priority.
Create an interface for a priority queue that does not allow duplicates. Then write a class that implements this
interface. Finally, write a program that adequately demonstrates your new class.
15.
Implement a priority queue of queues, as described in Project 6 of the previous chapter.
 
Search WWH ::




Custom Search