priority queue (優先順位待ち行列) は、値のコレクションから最も大きな要素を、すばやく何度も検索して削除する必要がある場合に有益なデータ構造です。優先順位待ち行列の日常での例は、自己管理のためにほとんどの人が持っている、実行しなくてはならない作業の to do リストです。机の上の整頓などの作業は、それほど重要ではなく、いつでも延期することができます。「月曜日までにレポートを仕上げる」、「記念日に花束を買う」などの作業には期限があり、早急に対処しなければなりません。このように、重要度に従って、完了しなくてはならない作業をソートします。おそらく、期限が迫った重要事項、長期にわたる利益、作業に伴う楽しみなどを合わせて考慮して、順位を決め、最も差し迫ったものから片付けることになります。
よりコンピュータに関連した優先順位待ち行列の例には、オペレーティングシステムで維持される処理の保留リストがあります。この例では、各要素に関連付けられた値がジョブの優先順位です。たとえば、次のキーが押されてデータが消える前に、端末で押されたキーにすばやく反応する必要があります。一方、プリンタで処理される出力の待ち行列にリストをコピーする処理は、最終的に処理される限り、短時間ならば延期することができます。優先順位待ち行列の処理を維持することによって、優先順位の高いジョブが優先順位の低いジョブより先に実行されます。
シミュレーションプログラムでは、将来のイベントの優先順位待ち行列を使用します。シミュレーションは仮想クロックを維持し、各イベントの行われる時間がイベントに関連付けられています。このようなコレクションでは、時間の値が最も小さい要素が次にシミュレートされるイベントです。これらは、priority queue が有益なツールであることを示すいくつかの事例にしかすぎません。おそらく、既に他の事例に直面したことがあるでしょうし、いずれ出会うことになるでしょう。
優先順位待ち行列という用語に違和感を感じる開発者もいるでしょう。データ構造は、厳密な先入れ先出し順序で要素を返すわけではないため、第 10 章で使用した queue という用語の意味ではありません。しかしながら、現在ではこの名前が強固にこのデータ型に関連付けられています。
優先順位待ち行列のデータの抽象化を使用するプログラムには、queue ファイルをインクルードする必要があります。
# include <queue>