10.3 queue データの抽象化

データの抽象化として、queue は、伝統的に、表 16 に示す演算を実装する任意のオブジェクトとして定義されています。

表 16 -- queue 演算

先頭の要素へのアクセスと削除は、それぞれ別の演算であることに注意してください。

queue データの抽象化を使用するプログラムには、queue ファイルをインクルードする必要があります。

# include <queue>

queue の宣言は、要素型を指定する必要があります。また、値を保持するコンテナを指定することもできます。queue のデフォルトコンテナは deque ですが、list を使用することもできます。list では一般的により小さく、deque ではわずかに速くなる場合があります。以下に、queue の宣言例を示します。

queue< int, list<int> > queueOne;
queue< double> > queueTwo;                      // deque を使用する
queue< Part *, list<Part * > > queueThree;
queue< Customer, list<Customer> > queueFour;

最後の例では、Customer という名前のユーザー定義の型から queue が作成されます。stack コンテナと同様に、queue に格納されるすべてのオブジェクトが演算子 < と == を認識する必要があります。

queue は反復子を実装しないため、第 IV 部で説明する汎用アルゴリズムは queue に適用することができません。

---

注: 銀行の出納係のシミュレーションプログラムの完全版は teller.cpp にあります。

---

待ち行列は、スーパーマーケットや銀行などでよく見かけます。あなたが銀行の支店長であると仮定して、ある時間に何人の出納係を置くかを決める必要があるとします。特定の観察結果に基づくコンピュータシミュレーションを行うとして、たとえば、ピーク時に毎分顧客が来店する確率が 90 % であるとします。

最初に顧客と出納係の両方を表すオブジェクトを定義して、シミュレーションを行います。顧客の場合、必要な情報は列で待っている平均時間です。このように、顧客オブジェクトは単純に列に到着した時間と、窓口にいた時間の 2 つの整数データフィールドを維持します。後者は 2 から 8 の間でランダムに選択される値です(randomInteger() 関数については、2.2.5 節を参照してください)。

class Customer {
public:
   Customer (int at = 0) : arrival_Time(at), 
         processTime(2 + randomInteger(6)) {}
   int arrival_Time;
   int processTime;
   
   bool done()      // 取扱いを終了したか
      { return --processTime < 0; }
      
   operator < (const Customer & c)   // 到着時間で順序付ける
      { return arrival_Time < c.arrival_Time; }
      
   operator == (const Customer & c)   // 顧客は一意とする
      { return false; }
};

オブジェクトは標準 C++ ライブラリのコンテナに格納されるので、等値や順序を知るために比較する場合は、顧客に対して、演算子 < および == を定義する必要があります。また、顧客の取扱いがいつ終了したかが通知されます。

出納係は忙しいことも、暇なこともあります。このため、各出納係の値は、顧客とブール型のフラグの 2 つのデータフィールドを保持します。出納係は、顧客に対するサービスを開始したときに呼び出されるメンバー関数とともに、手が空いているかどうかを回答するためのメンバー関数を定義します。

class Teller {
public:
   Teller() { free = true; }
   
   bool isFree()   // 手が空いていて、新しい顧客に応対できるか
      { if (free) return true;
        if (customer.done())
           free = true;
        return free;
       }

   void addCustomer(Customer c)   // 新しい顧客への応対開始
      {   customer = c;
         free = false;
      }

private:
   bool free;
   Customer customer;
};

メインプログラムは、毎分シミュレーションが行われるたびに循環する大きなループです。毎分新しい顧客が待ち行列に加わる確率は 0.9 です。各出納係がポーリングされ、手が空いている出納係がいれば、待ち行列の次の顧客の応対をします。応対を受けた顧客の数と、待ち行列で費やした合計時間がカウントされます。この 2 つの値から、次に示すシミュレーションによって、顧客が待ち行列で費やした平均時間を割り出すことができます。

void main() {
   int numberOfTellers = 5;
   int numberOfMinutes = 60;
   double totalWait = 0;
   int numberOfCustomers = 0;
   vector<Teller> teller(numberOfTellers);
   queue< Customer > line;
   
   for (int time = 0; time < numberOfMinutes; time++) {
      if (randomInteger(10) < 9)
         line.push(Customer(time));
      for (int i = 0; i < numberOfTellers; i++) {
         if (teller[i].isFree() & ! line.empty()) {
            Customer & frontCustomer = line.front();
            numberOfCustomers++;
            totalWait += (time - frontCustomer.arrival_Time);
            teller[i].addCustomer(frontCustomer);
            line.pop();
            }
         }
      }
   cout << "average wait:" <<
          (totalWait / numberOfCustomers) << endl;
}

出納係の数にさまざまな値を与えてプログラムを何度か実行すると、平均待ち時間を許容範囲にとどめながら顧客に応対するには、最低何人の出納係が必要かを割り出すことができます。