queue
The queue is a restricted form of a deque—you can only enter elements at one end and pull them off the other end. Functionally, you could use a deque anywhere you need a queue, and you would then also have the additional functionality of the deque. The only reason you need to use a queue rather than a deque, then, is if you want to emphasize that you will only be performing queue-like behavior.
The queue is an adapter class like stack, in that it is built on top of another sequence container. As you might guess, the ideal implementation for a queue is a deque, and that is the default template argument for the queue; you’ll rarely need a different implementation.
Queues are often used when modeling systems in which some elements of the system are waiting to be served by other elements in the system. A classic example of this is the "bank-teller problem": customers arrive at random intervals, get into a line, and then are served by a set of tellers. Since the customers arrive randomly and each takes a random amount of time to be served, there’s no way to deterministically know how long the line will be at any time. However, it’s possible to simulate the situation and see what happens.
In a realistic simulation each customer and teller should be run by a separate thread. What we’d like is a multithreaded environment so that each customer or teller would have their own thread. However, Standard C++ has no model for multithreading, so there is no standard solution to this problem. On the other hand, with a little adjustment to the code, it’s possible to simulate enough multithreading to provide a satisfactory solution.[99]
In multithreading, multiple threads of control run simultaneously, sharing the same address space. Quite often you have fewer CPUs than you do threads (and often only one CPU). To give the illusion that each thread has its own CPU, a time-slicing mechanism says "OK, current thread, you’ve had enough time. I’m going to stop you and give time to some other thread." This automatic stopping and starting of threads is called preemptive, and it means you (the programmer) don’t need to manage the threading process at all.
An alternative approach has each thread voluntarily yield the CPU to the scheduler, which then finds another thread that needs running. Instead, we’ll build the "time-slicing" into the classes in the system. In this case, it will be the tellers that represent the "threads," (the customers will be passive). Each teller will have an infinite-looping run( ) member function that will execute for a certain number of "time units" and then simply return. By using the ordinary return mechanism, we eliminate the need for any swapping. The resulting program, although small, provides a remarkably reasonable simulation:
//: C07:BankTeller.cpp
// Using a queue and simulated multithreading
// To model a bank teller system
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <list>
#include <queue>
using namespace std;
class Customer {
int serviceTime;
public:
Customer() : serviceTime(0) {}
Customer(int tm) : serviceTime(tm) {}
int getTime() { return serviceTime; }
void setTime(int newtime) {
serviceTime = newtime;
}
friend ostream&
operator<<(ostream& os, const Customer& c) {
return os << '[' << c.serviceTime << ']';
}
};
class Teller {
queue<Customer>& customers;
Customer current;
enum { slice = 5 };
int ttime; // Time left in slice
bool busy; // Is teller serving a customer?
public:
Teller(queue<Customer>& cq)
: customers(cq), ttime(0), busy(false) {}
Teller& operator=(const Teller& rv) {
customers = rv.customers;
current = rv.current;
ttime = rv.ttime;
busy = rv.busy;
return *this;
}
bool isBusy() { return busy; }
void run(bool recursion = false) {
if(!recursion)
ttime = slice;
int servtime = current.getTime();
if(servtime > ttime) {
servtime -= ttime;
current.setTime(servtime);
busy = true; // Still working on current
return;
}
if(servtime < ttime) {
ttime -= servtime;
if(!customers.empty()) {
current = customers.front();
customers.pop(); // Remove it
busy = true;
run(true); // Recurse
}
return;
}
if(servtime == ttime) {
// Done with current, set to empty:
current = Customer(0);
busy = false;
return; // No more time in this slice
}
}
};
// Inherit to access protected implementation:
class CustomerQ : public queue<Customer> {
public:
friend ostream&
operator<<(ostream& os, const CustomerQ& cd) {
copy(cd.c.begin(), cd.c.end(),
ostream_iterator<Customer>(os, ""));
return os;
}
};
int main() {
CustomerQ customers;
list<Teller> tellers;
typedef list<Teller>::iterator TellIt;
tellers.push_back(Teller(customers));
srand(time(0)); // Seed random number generator
clock_t ticks = clock();
// Run simulation for at least 5 seconds:
while(clock() < ticks + 5 * CLOCKS_PER_SEC) {
// Add a random number of customers to the
// queue, with random service times:
for(int i = 0; i < rand() % 5; i++)
customers.push(Customer(rand() % 15 + 1));
cout << '{' << tellers.size() << '}'
<< customers << endl;
// Have the tellers service the queue:
for(TellIt i = tellers.begin();
i != tellers.end(); i++)
(*i).run();
cout << '{' << tellers.size() << '}'
<< customers << endl;
// If line is too long, add another teller:
if(customers.size() / tellers.size() > 2)
tellers.push_back(Teller(customers));
// If line is short enough, remove a teller:
if(tellers.size() > 1 &&
customers.size() / tellers.size() < 2)