Java Reference
In-Depth Information
4.
Consider the method
splice
that Exercise 3 describes. Implement this method specifically for the class
ArrayQueue
.
Take advantage of your ability to manipulate the array representation of the queue.
5.
Consider the method
splice
that Exercise 3 describes. Implement this method specifically for the class
LinkedQueue
.
Take advantage of your ability to manipulate the chain that represents the queue.
6.
Using Big Oh notation, what is the time complexity of each queue operation in the class
ArrayQueue
? Briefly
explain your answers.
7.
Using Big Oh notation, what is the time complexity of each deque operation in the class
LinkedDeque
? Briefly
explain your answers.
8.
Implement the ADT queue by using an ADT deque to contain its entries.
9.
Implement the ADT stack by using an ADT deque to contain its entries.
10.
Describe an implementation of a queue that uses two stacks, and comment on its efficiency.
11.
Implement the ADT deque by using a vector to contain its entries.
12.
Consider an application that uses a priority queue. You have two implementations available. One implementation
uses an array to maintain the entries in the priority queue, while the other uses a linked chain. Compare the perfor-
mances of these implementations for each of the following sequences of operations on a priority queue.
a.
Insert 100 objects having the priorities 1, 2, 3,..., 99, 100.
b.
Insert 100 objects having priorities 100, 99, 98,...., 2, 1.
c.
Add 100 objects having random priorities within the range 1 to 100.
d.
Starting with 100 objects in the priority queue having priorities 1 through 100, remove them all.
e.
Starting with 100 objects in the priority queue having priorities 1 through 100, repeat the following pair of
operations 1000 times:
•
Add an item having a random priority within the range 1 to 100.
•
Remove an item.
P
ROJECTS
1.
Use a circular array, as described in Segments 11.8 and 11.9, to implement the queue. Count entries to ascertain
whether the queue is empty or full.
2.
The implementation of the ADT queue that was introduced in Segment 11.10 uses a circular array with one
unused location. Revise that implementation so that the unused location is always before the front of the queue,
with
frontIndex
as the index of this unused location. Let
backIndex
be the index of the entry at the back of the
queue. Initially, both
frontIndex
and
backIndex
are set to the maximum size of the queue (the array will be 1
larger than this number). You can distinguish an empty queue from a full queue by examining these indices. What
tests should you perform to do so?
3.
The array-based implementations of the ADT queue in this chapter used a circular array. One implementation
counted the entries in the queue, while the other left one location in the array unused. We used these strategies to
tell when the queue was empty and when it was full.
A third strategy is possible. It does not count and does not have an unused location in the circular array. After ini-
tializing
frontIndex
to 0 and
backIndex
to
-
1, you do not use modulo arithmetic when you increment these fields.
Instead, you use modulo arithmetic when you index the array, but without changing
frontIndex
and
backIndex
. Thus,
if
queue
is the array,
queue[frontIndex % queue.length]
is the front entry, and the entry at the back of the queue is
queue[backIndex % queue.length]
.
Now if
backIndex
is less than
frontIndex
, the queue is empty. The number of entries in the queue is
backIndex
-
frontIndex
+
1
. You can compare this number with the size of the array to see whether the array is full.
