Java Software Structures, 4th Edition Exercise Solutions, Ch. 5
Chapter 5 Exercise Solutions
EX 5.1 Hand trace a queue X through the following operations:
X.enqueue(new Integer(4));
X.enqueue(new Integer(1));
Object Y = X.dequeue();
X.enqueue(new Integer(8));
X.enqueue(new Integer(2));
X.enqueue(new Integer(5));
X.enqueue(new Integer(3));
Object Y = X.dequeue();
X.enqueue(new Integer(4));
X.enqueue(new Integer(9));
The queue, after each operation (rear of queue at the left):
4
1 4
1
EX 5.2 Given the resulting queue X from Exercise 5.1, what would be the result of each
of the following?
a.) X.front();
X.front() is not a valid method call. We should have called X.first(), which would return
b.) Y = X.dequeue();
c.) X.front();
As in part (a), we should have called X.first() instead of X.front(), and we need to store
d.) Y = X.dequeue();
EX 5.3 What would be the time complexity of the size operation for each of the
implementations if there were not a count variable?
With the count variable, the size operation is O(1) for all implementations. Without the
count variable, the regular array solution and the linked solution would require the
EX 5.4 Under what circumstances could the head and tail references for the linked
implementation or the front and rear references of the array implementation be
equal?
With a linked implementation, head and tail are equal when the queue is empty and
they are both null. They are also equal when there is only one element in the queue.
EX 5.5 Hand trace the ticket counter problem for 22 customers and 4 cashiers. Graph
the total process time for each person. What can you surmise from these
results?
Cutomer Number Arrival time Cashier 1 Cashier 2 Cashier 3 Cashier 4 Wait Time Total Time
1 0 0 0 120
215 15 0120
330 30 0120
445 45 0120
10 135 255 120 240
11 150 270 120 240
12 165 285 120 240
13 180 360 180 300
14 195 375 180 300
19 270 510 240 360
20 285 525 240 360
21 300 600 300 420
EX 5.6 Compare and contrast the enqueue method of the LinkedQueue class to the
push method of the LinkedStack class from Chapter 4.
EX 5.7 Describe two different ways the isEmpty method of the LinkedQueue class
could be implemented.
In addition to checking the value of count, a queue will be empty only if the reference
EX 5.8 Name five everyday examples of a queue other than those discussed in this
chapter.
(1) Standing in line at the grocery store check out, (2) cars waiting in line at an
EX 5.9 Explain why the array implementation of a stack does not require elements to
be shifted but the noncircular array implementation of a queue does.
All operations on a stack occur on one end of the stack (the top). Therefore, the bottom
of the stack can remain at location 0 of the array at all times. Operations on a queue,
EX 5.10 Suppose the count variable was not used in the CircularArrayQueue class.
Explain how you could use the values of front and rear to compute the number
of elements in the list.
The difference between the front and rear indexes indicates the number of elements in
the list, but the circular nature of the array must be taken into account. The following
code could be used: