Petrol pump queue simulation

Data structure

A queue is the suitable data structure. Vehicles are served in the order they arrive (FIFO): a new vehicle joins at the rear, and the vehicle at the front is served and leaves. A circular array or a linked queue can be used; a linked queue is better because the number of waiting vehicles is not known beforehand.

 arrive -> [ rear ... ... front ] -> pump -> leave

Algorithm

Assume the pump serves one vehicle at a time. Each vehicle has an arrival time and a service time. Clock t runs in minutes.

1. Create an empty queue Q;  pump_free_at = 0;  total_wait = 0
2. Repeat for each vehicle in order of arrival time:
     a. ENQUEUE(Q, vehicle)                    /* vehicle arrives */
3. While Q is not empty:
     a. v = DEQUEUE(Q)                         /* front vehicle goes to the pump */
     b. start  = max(v.arrival, pump_free_at)
     c. wait   = start - v.arrival
     d. finish = start + v.service
     e. pump_free_at = finish
     f. total_wait = total_wait + wait
     g. print v, wait, finish
4. average wait = total_wait / number of vehicles

In a real-time simulation, step 2 is carried out whenever the clock reaches an arrival time (random arrivals), and QUEUE EMPTY is checked before every dequeue. Underflow means the pump is idle.

Example

Arrival times 0, 1, 2, 6, 7; service times 3, 2, 4, 1, 2 minutes.

Total wait = 0 + 2 + 3 + 3 + 3 = 11 minutes; average wait = 11 / 5 = 2.2 minutes.