Queues, Deques, and Priority Queues - Data Structures and Abstractions with Java - page 249

FIGURE 10-6

A simulated waiting line

Transaction time left: 5

Customer 1 enters line with a 5-minute transaction.
Customer 1 begins service after waiting 0 minutes.

1

Time: 0 Wait: 0

Transaction time left: 4

Customer 1 continues to be served.

1

Time: 1

Transaction time left: 3 3

Customer 1 continues to be served.
Customer 2 enters line with a 3-minute transaction.

1 2

Time: 2

Transaction time left: 2 3

Customer 1 continues to be served.

1 2

Time: 3

Transaction time left: 1 3 1

Customer 1 continues to be served.
Customer 3 enters line with a 1-minute transaction.

2

1 3

Time: 4

Transaction time left: 3 1 2

Customer 1 finishes and departs.
Customer 2 begins service after waiting 3 minutes.
Customer 4 enters line with a 2-minute transaction.

3

2
Wait: 3

4

Time: 5

Transaction time left: 2 1 2

Customer 2 continues to be served.

2 3 4

Time: 6

Transaction time left: 1 1 2 4

Customer 2 continues to be served.
Customer 5 enters line with a 4-minute transaction.

2 3 4 5

Time: 7

Transaction time left: 1 2 4

Customer 2 finishes and departs.
Customer 3 begins service after waiting 4 minutes.

5

3 4

Time: 8 Wait: 4

Transaction time left: 2 4

Customer 3 finishes and departs.
Customer 4 begins service after waiting 4 minutes.

4 5

Time: 9 Wait: 4