7.7　队列

queue容器是一个受到限制的deque形式—只可以在队列一端放入元素，而在另一端删除它们。在功能上，可以在需要使用queue的任何地方使用deque，那时也能够使用deque的附加功能。需要使用queue而不是deque的惟一理由就是，当读者希望强调仅仅执行与queue相似的行为的时候。

queue类是一个如同stack的适配器，因为它也建立在另一个序列容器的基础之上。就像读者猜测的那样，对queue的理想的实现是deque，而其对queue来说是默认的模板参数；很少需要不同的实现。

如果想建立这样一个系统模型，即系统中的某些元素正在等待另一些元素的服务时，时常使用队列。“银行出纳员问题”就是一个经典的例子。顾客们在随机的时间间隔到达银行，进入某一行队列排队，然后由一组出纳员服务。因为顾客们到达是随机的，并且每一个顾客得到的服务时间总数也是随机的，所以没有一种方法能决定性地知道在任何时间点某行队列有多长。然而，模拟这种情形并且看看到底会发生什么事情却是可能的。

在对现实的模拟中，每个顾客和每个出纳员都在独立的线程中运行。这多么像是一个多线程的环境，因此每个顾客和出纳员都有他自己的线程。然而，标准C++不支持多线程处理。另一方面，通过对代码做一些小的调整，模拟足够的多线程处理以提供一个满意的解决方案是可能的。^[1]

在多线程处理中，多个受控制的线程同时运行，共享同一个地址空间。通常用户拥有的CPU数量都会比运行的线程数量少（常常只有一个CPU）。为得到虚拟的环境，应使每一个线程都拥有其自己的CPU，一种时间分片（time-slicing）机制说“OK，当前线程你已经占用了足够多的时间，我马上就要让你停止从而给其他线程一些时间了”。这种自动的线程停止和启动被称为抢占（preemptive），它意味着（程序员）不需要去管理线程处理的过程。

另一种方法就是每个线程自动地将CPU让给线程调度器，该线程调度器然后寻找另一个需要运行的线程。另外，建立“时间分片”进入到系统中的各个类。在这里，将那些出纳员表示为“线程”（顾客将是被动的）。每个出纳员都有一个进行无限循环处理的成员函数run（），该成员函数将在执行确定数量的“时间单元”后返回。通过使用平常的返回机制，排除了任何需要进行的交换处理。虽然产生的程序很小，但是它提供了一个不平常的合理的模拟场景：

每个顾客都需要一个确定的服务时间总额，这就是一个出纳员必须在为某个顾客提供其所需服务上花费的时间单元数。为每个顾客提供的服务时间总额都不同，并且这个时间总额肯定是随机的。另外，也不会知道在每个时间间隔内究竟会有多少个顾客到达，因此这也肯定是随机的。

这些顾客Customer对象被保存在一个queue＜Customer＞中，并且每个出纳员Teller对象都持有那个队列的一个引用。在一个Teller对象完成对当前Customer对象的服务以后，这个Teller将会从队列中得到另一个Customer，开始继续为这个新Customer提供服务，系统从该Teller分配到的时间片里面减少Customer的服务时间。所有这些逻辑都包含在成员函数run（）中，它只是一个具有3个分支的if语句，该语句基于以下事件建立，即当前顾客所必需的服务时间总额是小于、大于、或是等于出纳员在当前时间片中剩余的时间总额。注意，如果该出纳员Teller在完成对一个Customer的服务后还有多余的时间，它再获得一个新的Customer，然后实施自身的递归处理。就像使用stack一样，在使用queue时，它只是一个queue，不具有基础序列容器的任何其他功能。这包括获得一个迭代器以遍历stack的能力。然而，在queue内部将底层序列容器（构建queue的基础）作为一个protected成员来保存，在C++标准中该成员被指定以'c'来做标识符，这意味着可以通过派生自queue的类来访问底层实现。在这里类CustomerQ正是这样做的，其惟一目的就是定义一个ostreamoperator＜＜，以便在queue上实施迭代并显示其成员。

这个模拟系统的驱动器就是main（）函数中的while循环，它使用处理器的时钟滴答（定义于＜ctime＞中）来决定该模拟系统是否已经至少运行了5秒钟。在每次经过从头到尾的循环的开始，都要加入随机的顾客数，和随机的服务时间。为了看到系统当前的状态，出纳员的数量和队列的内容都将显示出来。每个出纳员处理完后，重复地显示这些信息。在这一点上，系统通过比较顾客和出纳员的数量来进行调整。如果某行队列太长，就加入其他的出纳员，而如果队列足够短，则删除一个出纳员。在程序中的这个调整区段中，可以用实验的策略得到关于添加和删除出纳员的最佳数据。如果这是惟一想要修改的区段，也许要将策略封装到不同的对象中去。

本教材将在第11章中的多线程练习中再次涉及这个例子。

[1]我们将在第11章再次讨论多线程处理问题。