Lab QueueSimu - Queue simulator

This exercise is taken almost verbatim from the book: A Laboratory Course on C++ Data Structures by Robergé, et. al.

In this exercise you will use a queue ADT to simulate the flow of customers through a check-out line in a store. In order to create this simulation, you must model both the passage of time and the flow of customers through the line. You can model time using a loop in which each pass corresponds to a set time interval of 1 minute, for example. You can model the flow of customers using a queue in which each data item corresponds to a customer in the line.

In order to complete the simulation, you need to know the rate at which customers join the line, as well as the rate at which they are served and leave the line. Suppose the check-out line has the following properties:

You can simulate the flow of customers through the line during a time period n minutes long using the following algorithm.

Initialize the queue to empty.
for ( minute = 0 ; minute < n ; minute++ )
{
   If the queue is not empty, then remove the customer at the front of the queue.
   Compute a random number k between 0 and 3.
   If k is 1, then add one customer to the line. If k is 2, then add two customers
   to the line. Otherwise (if k is 0 or 3), do not add any customers to the line.
}

Calling the C++ rand() function is a simple way to generate pseudo-random numbers. It should be available through the <cstdlib> header file. Generating random numbers varies from platform to platform because of compiler and operating system differences. If you are not familiar with random number generation in C++ please read the section "Random Numbers in C++" at the end of this document.

A starter code is provided in http://vpl.ccom.uprrp.edu in the Lab “Queues: Simulate a queue” .

Step 1

Create a client program that uses the Queue abstract data type to implement the model described in the preceding paragraphs. You can use the STL queue class. Your program should update the following information during each simulated minute; that is, during each pass through the loop:

To compute how long a customer waited to be served, you need to store the “minute” that the customer was added to the queue as part of the queue data item corresponding to that customer.

For example, the following figure illustrates the state of the queue under different situations.

https://i.imgur.com/8g9kEDo.png

Step 2

Use your program to simulate the flow of customers through the line and complete the following table. Each entry in the queue represents a customer (the minute when the customer entered the queue). Note that the average wait is the combined waiting time divided by the total number of customers served.

Time(minutes) Total Number of Customers Served Average Wait (w/ two decimal places) Longest Wait Average Queue Length (w/ two decimal places)
30
60
120
480

Deliverables

Appendix: Random numbers in C++

The function for generating random numbers in C++ is called rand() and included in the cmath library (the same one where pow and sqrt are found). rand() generates a random unsigned integer number between 0 and RAND_MAX. RAND_MAX is a constant whose value is library-dependent, but is guaranteed to be at least 32767 on any standard library implementation.

cout << "Here is a random number:\t" << rand() << endl;
cout << "Here is another:\t" << rand() << endl;

The output (as run in ada.uprrp.edu) is:

Here is a random number:    1804289383
Here is another:            846930886

Curiously, if we run the program again we obtain the following:

Here is a random number:    1804289383
Here is another:            846930886

Wait a moment. Are we going to get the same sequence of random numbers every time we run the program? Yes

Why? Because of how rand() generates random numbers. To generate a random number, rand() uses a formula that depends on the previous random number that was generated.

newRandomValue = someWeirdFormula(previousRandomValue)

To produce the first random number in your program, rand() uses what is called a seed value. If we don't write it explicitly in our program, the seed will always be the same, and therefore, the sequence of random numbers will be the same.

What we need is a method to assign a value to the seed such that whenever we run the program the seed is different and so is the sequence of random numbers generated by calls to rnd(). The preferred way to do this is by calling on the srand() function like this:

srand(time(NULL));

The time(NULL) parameter simply reads the operating system's clock and uses the current time/date as a seed. Since every time you execute the program the clock time is different, so will the seed.

The following program prints three different random numbers every time we execute it:

srand(time(NULL));
cout << rand() << ", " << rand() << ", " << rand();

How to limit the range of random numbers

The range of 0 to RAND_MAX might be too much for many of your programs. To limit the range to maximum of 99, you could use the help of your friend the modulus operator:

srand(time(NULL));

cout << "I am a small random num:" << rand()%100 << endl;

cout << "I am another small random num:" << rand()%100 << endl;

For integer random numbers in the range of [min, max], use:

rand()%(max-min+1) + min

For example, to generate integer random numbers in the range of [1,6], use:

rand()%6 + 1