A queue is a waiting line, as in a line of people waiting for checkout at a supermarket, or a line of people waiting for service at an automatic teller machine.
Note that new data is put into the queue by placing it at the end of the line. Note also that the oldest data in the queue, the data at the beginning of the line, will be the first data to come out of the queue.
A queue is a list structure (like an array or linked list), together with supporting functions, that looks and acts like a waiting line.
Here is the class definition (in file queue.h) and the functions (in file queue.cpp) for an int queue: a line of integers.
#ifndef QUEUE_H
#define QUEUE_H
#include <iostream>
using namespace std;
const int MAXSIZE = 100; //Maximum size of the queue.
class Queue
{
friend ostream& operator<< (ostream&, Queue&);
public:
Queue ();
void push (int n); //Add person to the queue
void pop (); //Remove person from beginning of queue
int getFirstInLine (); //Get a copy of the first person in line
bool isEmpty ();
private:
int size; //Queue length
int line [MAXSIZE];
};
#endif
#include <iomanip>
#include "Queue.h"
const int WIDTH = 5; //Print field size
Queue::Queue ()
{
size = 0;
}
void Queue::push (int n)
{
if (size < MAXSIZE)
{
line [size] = n;
size++;
}
}
void Queue::pop ()
{
if (size > 0)
{
//Remove the person at the beginning by moving
// everyone else forward one place.
for (int n = 0; n < size - 1; n++)
line [n] = line [n + 1];
size--;
}
}
int Queue::getFirstInLine ()
{
//Return a copy of the first person in line.
int temp = 0;
if (size > 0)
temp = line [0];
return temp;
}
bool Queue::isEmpty ()
{
return size == 0;
}
ostream& operator<< (ostream& out, Queue& Q)
{
for (int n = 0; n < Q.size; n++)
out << setw (WIDTH) << Q.line [n];
return out;
}
It would be helpful to also have a server object (like a supermarket checker's counter) that holds a customer for a set service time and then clears him/her out when that time is up. The following will do it.
#ifndef SERVER_H
#define SERVER_H
#include <iostream>
using namespace std;
//class invariantfor the service class:
//A server object represents a station where a person receives
// a service (banking, haircut, etc., etc.).
//A server object contains:
// 1) a person number, that represents the person getting the service.
// 2) a timer, that records how long the person has been getting the servic.
// 3) a service time, that is the limit of the time a person gets service.
// When the timer reaches the service time, then the person is removed.
class server
{
friend ostream& operator<< (ostream&, server&);
public:
server (int); //The n is the time to service a person.
bool isAvailable (); //True if noone is present, otherwise false
void StartService (int n); //n is the person to service
void Update (); //Ups the timer, kicks the person
// out when the time is up.
private:
int person;
int timer;
int serviceTime;
};
#endif
#include <iomanip>
#include "server.h"
const int WIDTH = 5; //Width of print fields
const int NOBODY = 0;
server::server (int time)
{
//Initialize the person to empty, the time to 0, and set the length of
// the service time.
person = NOBODY;
timer = 0;
serviceTime = time;
}
bool server::isAvailable ()
{
bool returnVal = false;
if (person == NOBODY)
returnVal = true;
return returnVal;
}
void server::StartService (int n)
{
//n is the number of the person to be serviced. Since service is
// starting, set the timer to 0.
person = n;
timer = 0;
}
void server::Update ()
{
//Add a minute to the timer. If the service time is reached, then
// the person being serviced is done, so remove him/her, and reset
// the time to 0.
timer++;
if (timer == serviceTime)
{
person = NOBODY;
timer = 0;
}
}
ostream& operator<< (ostream& out, server& service)
{
if (!service.isAvailable ())
out << setw (WIDTH) << service.person;
else
cout << setw (WIDTH) << " ";
return out;
}
Everything that happens in a computer is deterministic. That is, if you know the inputs and the process, then you can perfectly predict exactly what will happen (at least in theory.) This is also true with random numbers produced by C++.
What does random mean? It means that you can't predict what will happen next, but over time the results form a definite pattern.
C++ will not generate truly random numbers, but it will generate numbers that ``look random'' (but are deterministic).
In the cstdlib library are the two functions srand (int n) and rand ().
The srand function takes an int number as a seed. It uses the seed to generate a long sequence of (pseudo) random numbers between 0 and a large maximum called MAX_RAND. Since srand sets up a whole sequence of numbers, the program should not call srand more than once.
The rand() function actually returns the next number in the random sequence. Use rand () wherever you need a random number.
It is a good object oriented idea to encapsulate the generation of random customer arrivals in a class. This class will need to be initialized by
The class will tell if an arrival has occurred, and it will give the number of the arrival when asked (which means it keeps a count of the arrivals).
The class definition looks like this, in arrivalGen.h:
#ifndef ARRIVALGEN_H
#define ARRIVALGEN_H
//class invariant for the arrivalGenerator class:
//An arrivalGenerator object generates the number of the next person arriving
// for service, if there is one. Whether or not a person arrives is
// determined at random according to a set probability.
//The arrivalGenerator object contains:
// 1) The probability that is used to determine if an arrival occurs.
// 2) The number of the next arrival, as an identifier for that person.
class arrivalGenerator
{
public:
arrivalGenerator (int, double); //The int is a seed for the random
// number generation.
//The double is the probability to
// be usedfor generating random
// numbers.
bool isArrival (); //True if an arrival occurs.
int getArrival (); //The number of the last person arriving.
private:
double probability;
int nextCustomer;
};
#endif
The code is in arrivalGen.cpp.
#include <cstdlib> //For srand and rand
arrivalGenerator::arrivalGenerator (int s, //srand seed
double P) //Probability of arrival
{
srand (s); //seed the random sequence
probability = P;
nextCustomer = -1;
}
bool arrivalGenerator::isArrival ()
{
bool returnVal = false;
double event = rand () % 100 + 1; //Get a random number betw
// 1 and 100
if (event / 100.0 <= probability) //Determine if an arrival
// occurred
{
returnVal = true;
nextCustomer++;
}
return returnVal;
}
int arrivalGenerator::getArrival ()
{
return nextCustomer;
}
Now that we have a queue class, a server class, and an arrivalGenerator class, we can put together a simulation of the line at a bank teller.
Customers are serviced in 3 minutes.
Customers arrive at a rate of one per three minutes (probability of 1/3).
#include <iostream>
#include <iomanip>
#include "Queue.h"
#include "server.h"
#include "arrivalGen.h"
const int SERVICETIME = 3;
const int SEED = 6;
const float PROBABILITY = .333;
const int WIDTH = 6;
const int MAXTIME = 50;
int main ()
{
server teller (SERVICETIME); //Set up the teller with the
// given service time.
Queue line;
arrivalGenerator arrivalMachine (SEED, PROBABILITY);
cout << "Minute " << "Serving " //Table headings
<< "Queue" << endl;
//Run throught the minutes of the simulation
for (int minute = 0; minute <= MAXTIME; minute++)
{
//Teller advances its timer, removes customer if
// service is finished.
teller.Update ();
//Generate an arrival (or not). If there is an arrival put the
// person in line.
if (arrivalMachine.isArrival ())
line.push (arrivalMachine.getArrival ());
//If the teller is open, give first person in line to the
// teller for service, and remove the person from the line.
if (teller.isAvailable ())
{
teller.StartService (line.getFirstInLine ());
line.pop ();
}
//Display the current state of the teller and the line.
cout << setw (WIDTH) << minute << " > "
<< teller << " " << line << endl;
}
return 0;
}
Minute Serving Queue
0 >
1 > 1
2 > 1
3 > 1
4 >
5 >
6 >
7 >
8 >
9 >
10 > 2
11 > 2
12 > 2 3
13 > 3
14 > 3
15 > 3
16 >
17 > 4
18 > 4 5
19 > 4 5 6
20 > 5 6
21 > 5 6
22 > 5 6
23 > 6
24 > 6 7
25 > 6 7 8
26 > 7 8 9
27 > 7 8 9
28 > 7 8 9
29 > 8 9 10
30 > 8 9 10 11
31 > 8 9 10 11
32 > 9 10 11
33 > 9 10 11
34 > 9 10 11
35 > 10 11
36 > 10 11
37 > 10 11 12
38 > 11 12
39 > 11 12
40 > 11 12 13
41 > 12 13 14
42 > 12 13 14
43 > 12 13 14 15
44 > 13 14 15
45 > 13 14 15 16
46 > 13 14 15 16 17
47 > 14 15 16 17 18
48 > 14 15 16 17 18
49 > 14 15 16 17 18
50 > 15 16 17 18