Chapter 6
Section 6.1
1.
Thome will be the customer that is removed. There are three customers left.
Section 6.2
1.
declare an integer x
declare an integer y
declare an object temp
set x = queue.getSize()
set y = 0
loop while y < x
set temp = queue.remove()
display temp
queue.insert(temp)
increment y by 1
next loop
This algorithm would rotate the entire queue once, but the queue would essentially be the same in the end, with the same size and order of objects.
Section 6.3
1.
3.
While inserting a new item at the rear is easy, to remove an item from the front you need to walk along the linked list until you reach the next to last node, so that you have a reference to the new front, this is an O(n) operation. By having the front at the head of the linked list and the rear at the tail, both insertion and removal are constant time operations.
Section 6.4
1.
The time is 0. Frequent Flyer arrival, new queue size is 1.
The time is 0. Regular Passenger arrival, new queue size is 2.
Time is 0, serving Frequent Flyer with timestamp 2.
The time is 1. Frequent Flyer arrival, new queue size is 2.
The time is 1. Regular Passenger arrival, new queue size is 3.
The time is 2. Regular Passenger arrival, new queue size is 4.
Time is 2 serving Regular Passenger with timestamp 1.
The time is 3. Frequent Flyer arrival, new queue size is 4.
The time is 3. Regular Passenger arrival, new queue size is 5.
Time is 3 serving Frequent Flyer with timestamp 1.
The time is 4. Regular Passenger arrival, new queue size is 5.
Time is 4 serving Regular Passenger with timestamp 1.
The time is 5. Frequent Flyer arrival, new queue size is 5.
Time is 5 serving Frequent Flyer with timestamp 3.
Time is 8, serving Regular Passenger with timestamp 1.
Time is 9, serving Frequent Flyer with timestamp 2.
Time is 11, serving Regular Passenger with timestamp 1.
Time is 12, serving Regular Passenger with timestamp 2.
The number of regular passengers served was 5
with an average waiting time of 5.4
The number of frequent flyers served was 4
with an average waiting time of 2.0
There are 0 passengers left in the frequent flier line
There are 0 passengers left in the regular passenger line
=
3. No, changing the order of these statements would not change the result. The checkNewArrivals are both performed before the startServe() function is called, and all three in the same clock stroke. The result is the same.