Learning objectives
The class queue 
At the Saarbrücken Central Station, from which the author often travels far away when he is fed up of writing boring tutorials, the author is often fed up with the long processing times at the ticket offices and wants to be far away.
There are 8 desks there. In the past, a queue formed in front of each of the 8 desks. When a new traveller came into the hall, he lined up in the shortest queue. Of course, he always had the feeling to have lined up in the queue in which the processing of his wishes lasted longest, in full harmony with Murphy's law. Figure 2.22 shows this situation.
“The system is so unfair”, many travellers grumbled. And: “The one who came first also should always be the first one to be served. Who comes first, pays first!” Deutsche Bahn, always being on the side of its customers, recognized this defect and introduced a new queuing system. Instead of 8 single queues there is a central queue now in which every traveller lines up first. When a desk becomes free, then the one who is right ahead in the central queue goes to this desk, which has just become free. The new system is depicted in Figure 2.23.
With this system every traveller has at least the impression that the whole waiting procedure is going on more fairly. It remains the question whether this system really shortens the mean time for processing. Is this really so? Or does the new system rather increase the mean processing times even further? Or does it at least reduce the standard deviation of the processing time, by which the grumbling about individual waiting times differing too much should get softer?
To settle these questions, we want to compare both systems
in a simulation. Of course, the main attention shall lie on the
LEDA class queue
, which models the queues.
Our simulation proceeds discretely in minutes. In every minute between 0 and 4 travellers arrive.^{[27]} As probability distribution we take a binomial distribution with mean value 2. So on the average 2 travellers per minute come into the system. Every traveller takes 2, 3, 5, or 6 minutes personal processing time; 3 minutes of processing time are twice as probable as the other times. This distribution has a mean value of 3.8 minutes. So per one minute of the simulation, we need 2 · 3.8 = 7.2 minutes of work to be done on the average. This is just managed by the 8 desk clerks so that the queues do not get infinitely long and the system does not become chaotic.
We put travellers into the queues. We model these by
means of a class Traveller
.
Every traveller knows his time of arrival and can give information
about it. He knows the number of minutes that he still needs as
personal processing time. He can decrement this number (if he is
processed by the clerk) and give information about the time
remaining. For the distribution of the original
processing time, which is defined in the constructor of a
Traveller
, we still need a (static) random source and a (static) array
of individual processing times.^{[28]}
With that the header file Traveller.h
looks as
follows:
#include <LEDA/random_source.h> using leda::random_source; class Traveller { private: int time_to_serve; int arrival_time; static const int service_times[]; static random_source S; public: Traveller(int); ~Traveller(); int dec_time_to_serve(); int get_arrival_time(); };
The implementation Traveller.C
defines the array of the processing times and the random
source. A Traveller
records his time of
arrival in the constructor; thereby, the time spent in the
system by this traveller can be calculated later by subtraction
from the current system time. In addition, the constructor
creates a random processing time by means of the random
source.
#include "Traveller.h" random_source Traveller::S; const int Traveller::service_times[] = {2,3,3,5,6}; // total of 19 means 3.8 minutes per traveller on the average Traveller::Traveller(int t) { arrival_time = t; time_to_serve = service_times[S(0,4)]; } Traveller::~Traveller() {} int Traveller::dec_time_to_serve() { return time_to_serve;} int Traveller::get_arrival_time() { return arrival_time;}
We now come to the actual simulation, which is based on
the LEDA type queue
. First we
simulate the old queuing system for a whole year of
uninterrupted runtime. In every minute of the simulation the
following happens: At first a random number of travellers freshly
coming into the system is created. Every new traveller
lines up in the currently shortest queue. After this, all 8
clerks carry out 1 minute of work each, that is, they serve the
first traveller standing in the queue right in front of them.
This traveller decrements his remaining processing time. If it
has become 0, he exits the queue and the system. We accumulate
the time that he altogether spent in the system in a sum
variable and store it additionally in a list in order to be able
to calculate statistical indicators, like the standard
deviation, later.
#include <LEDA/queue.h> #include <LEDA/list.h> #include <LEDA/array.h> #include <LEDA/random_variate.h> #include "Traveller.h" using leda::queue; using leda::array; using leda::random_variate; using leda::list; using std::cout; array< queue<Traveller*> > Queues(1,8); int min_queue = 1; // number of a shortest queue list<int> Service_times; // needed for computation of variance const int mins_to_simulate = 60*24*7*52; // 1 full year int total_travellers = 0; int travellers_served = 0; int total_service_time = 0; void compute_shortest_queue(); void output_statistics(); int main() { // random variate of 'travellers per minute' array<int> weight(0,4); weight[0] = 1; weight[1] = 4; weight[2] = 6; weight[3] = 4; weight[4] = 1; // this gives 2 travellers per minute on the average random_variate R(weight); // for every minute of the time interval do the following for(int time = 0; time < mins_to_simulate; time++) { // some new travellers arrive int num_new_travellers = R.generate(); total_travellers += num_new_travellers; // Queing the new travellers for(int i = 0; i < num_new_travellers; i++ ) { Traveller* T = new Traveller(time); // Traveller t goes to the queue with minimal length Queues[min_queue].append(T); compute_shortest_queue(); } // Travellers at the front of the queues get served for(int i = 1; i <= 8; i++) if(!Queues[i].empty()) { Traveller* T = Queues[i].top(); if(T>dec_time_to_serve() == 0) { // T leaves the system Queues[i].pop(); travellers_served++; compute_shortest_queue(); int time_used = time  T>get_arrival_time(); total_service_time += time_used; Service_times.append(time_used); delete T; } } } output_statistics(); } // Update min_queue // Hint: Priority Queues and Sorted Sequences are // better data structures for this task! void compute_shortest_queue() { for(int j = 1; j <= 8; j++) if(Queues[j].size() < Queues[min_queue].size()) min_queue = j; } void output_statistics() { double mean = total_service_time/(double)travellers_served; // compute standard deviation int time; double sum; forall(time,Service_times) sum += (time  mean) * (time  mean); double variance = sum / (Service_times.size()1); double stddev = sqrt(variance); cout << "Total number of travellers arrived = " << total_travellers << "\n"; cout << "Total number of travellers served = " << travellers_served << "\n"; cout << "Total service time = " << total_service_time << "\n"; cout << "Service time per traveller = " << mean << "\n"; cout << "Standard deviation = " << stddev << "\n"; }
The output of a sample run is:
Total number of travellers arrived = 1048773 Total number of travellers served = 1048769 Total service time = 6018465 Service time per traveller = 5.7386 Standard deviation = 3.86143
So almost all travellers were served; the queues did not fill excessively. On the average, every traveller was served within 5.73 minutes. The standard deviation was 3.86 minutes. We will compare these results with those of the second simulation at once.
The method for inserting elements into a
queue
is called
Q.append();
The method
Q.top();
returns a copy of the first element in the queue.
A call
Q.pop();
does the same; however, it additionally removes the first element from the queue.
Q.size();
returns the number of elements in a queue.
Q.empty();
checks whether a queue is empty, and by
Q.clear();
a queue can be emptied completely.
Note  

It is remarkable here that we put pointers to
Since we want to change the internal time information
of the first traveller (by
With regard to their interface, the types

Tip  

The lengths of the individual queues change from
minute to minute. The simulation must, however, know the
currently shortest queue. Here, we calculate this queue by a
complete comparison of all lengths. For exactly this problem
definition, though, LEDA keeps ready especially efficient data
types, which we will come to know yet:

We come to the new system now: There are only one central queue and 8 desks, at which at most one traveller is standing. We implement the desks by an array of pointers to travellers. Again, new travellers are created in every minute of the simulation, according to the same distributions. However, these travellers first line up in the central queue. If a desk is empty, the first traveller of the central queue walks to this desk. After this, all 8 clerks carry out 1 minute of work again, that is, they serve the traveller standing right in front of them (if one stands there at all).
#include <LEDA/queue.h> #include <LEDA/list.h> #include <LEDA/array.h> #include <LEDA/random_variate.h> #include "Traveller.h" using leda::queue; using leda::array; using leda::random_variate; using leda::list; using std::cout; queue<Traveller*> BigQueue; array<Traveller*> TicketOffice(1,8); list<int> Service_times; // needed for computation of variance const int mins_to_simulate = 60*24*7*52; // 1 full year int total_travellers = 0; int travellers_served = 0; int total_service_time = 0; void output_statistics(); int main() { // random variate of travellers per minute array<int> weight(0,4); weight[0] = 1; weight[1] = 4; weight[2] = 6; weight[3] = 4; weight[4] = 1; // this gives 2 travellers per minute on the average random_variate R(weight); // intialize offices for(int i = 1; i <= 8; i++) TicketOffice[i] = nil; // for every minute of the time interval do the following for(int time = 0; time < mins_to_simulate; time++) { // some new travellers arrive int num_new_travellers = R.generate(); total_travellers += num_new_travellers; // Queing the new travellers into the one big queue for(int i = 0; i < num_new_travellers; i++ ) { Traveller* T = new Traveller(time); BigQueue.append(T); } // Empty offices get travellers from the big queue for(int i = 1; i <= 8; i++) if(!TicketOffice[i] && !BigQueue.empty()) TicketOffice[i] = BigQueue.pop(); // Travellers at the 8 offices get served for(int i = 1; i <= 8; i++) if(Traveller* T = TicketOffice[i]) { if(T>dec_time_to_serve() == 0) { // T leaves the system TicketOffice[i] = nil; travellers_served++; int time_used = time  T>get_arrival_time(); total_service_time += time_used; Service_times.append(time_used); delete T; } } } output_statistics(); } void output_statistics() { double mean = total_service_time/(double)travellers_served; // compute standard deviation int time; double sum; forall(time,Service_times) sum += (time  mean) * (time  mean); double variance = sum / (Service_times.size()1); double stddev = sqrt(variance); cout << "Total number of travellers arrived = " << total_travellers << "\n"; cout << "Total number of travellers served = " << travellers_served << "\n"; cout << "Total service time = " << total_service_time << "\n"; cout << "Service time per traveller = " << mean << "\n"; cout << "Standard deviation = " << stddev << "\n"; }
The output of an example run is here:
Total number of travellers arrived = 1047306 Total number of travellers served = 1047303 Total service time = 5491971 Service time per traveller = 5.24392 Standard deviation = 3.26802
There you are! A cheer for Deutsche Bahn! By the new system, we save half a minute at the desks on the average. Moreover, the oscillation around the mean processing time is smaller, making the system appear fairer and therefore our fellow passengers less grumbly. (However, this all is recompensated by sufficient train delay and a very, very strange pricing policy well enough.)
The class queue
is implemented by
linearly linked lists. All operations take time O(1) apart
from clear()
, which takes time O(n) if a
queue
contains n elements.
More about queues can be found on the corresponding manual page.
^{[27] }These distributions are arbitrary. However, they
could be based on a measuring. Here we could, of course,
think up and implement more complex distribution
models also, but this would turn away the main attention from the
class queue
, which it is all about here, actually.
^{[28] }One should expect
after reading Section 2.6 that the individual
processing times, which are not all equally likely, are implemented by
a random variate.
Unfortunately, it is not possible with the present implementation of
random_variate
to make an object of this class a static member that
can be initialized suitably. We therefore manage here with a static
random_source
and a static
array
in which the number 3 occurs
twice.
Another possibility is to use a static
pointer to a
random_variate
that is initialized
to NULL
. If a random processing time is
needed for time_to_serve
in the
constructor, it is checked first whether the pointer is
still NULL
; if it is, a new
random_variate
, to which the pointer
then points, is created with new
. Random processing times
are created via this pointer from then on. With this
handle
technique the problem of not being able to
create any static random_variate
is
bypassed elegantly.