キューの種類

1. 序章

この記事では、4種類のキューとそのアプリケーションについて学習します。イラストでひとつひとつ理解していきましょう。

単純なキューは最も基本的なキューです。このキューでは、エンキュー操作は後部で実行され、 デキュー操作は前部で実行されます：

そのアプリケーションは、プロセススケジューリング、ディスクスケジューリング、メモリ管理、IOバッファ、パイプ、コールセンター電話システム、および割り込み処理です。

循環キューは、キューのサイズが固定されている場合、単純キューよりも優れたメモリ使用率を可能にします。

このキューでは、最後のノードが最初のノードを指し、循環接続を作成します。したがって、最後のノードがいっぱいで最初のノードが空いているときに、キューの最初のノードにアイテムを挿入できます。

リングバッファとも呼ばれます。

信号機のライトのオンとオフを切り替えるために使用されます。それとは別に、上記のすべてのアプリケーションで単純なキューの代わりに使用することもできます。

優先キューは、各アイテムに事前定義されたサービスの優先度がある特殊な種類のキューです。このキューでは、エンキュー操作はアイテムの到着順に後方で行われ、デキューは行われます。操作は、アイテムの優先度に基づいて前面で行われます。

つまり、優先度の高いアイテムは、優先度の低いアイテムの前にデキューされます。

この場合、2つ以上のアイテムの優先度が同じである場合、それらは到着順にデキューされます。したがって、FIFOルールに厳密に従う場合と従わない場合があります。

dequeも特殊なタイプのキューです。このキューでは、エンキューおよびデキュー操作がフロントとリアの両方で実行されます。つまり、両端にアイテムを挿入したり、両端からアイテムを削除したりできます。したがって、FIFOの順序に準拠している場合と準拠していない場合があります。

これは、閲覧履歴の保存、元に戻す操作の実行、A-Stealジョブスケジューリングアルゴリズムの実装、スタックの実装、または単純なキューの実装に使用されます。

さらに、 input-restricteddequeとoutput-restricteddequeの2つの特殊なケースがあります。

最初のケースでは、エンキュー操作は後部でのみ実行されますが、デキュー操作は後部と前部の両方で実行されます。

入力制限キューは、キューの後ろからアイテムを削除する必要がある場合に役立ちます。

2番目のケースでは、エンキュー操作はリアとフロントの両方で実行されますが、デキュー操作はフロントでのみ実行されます。

出力制限キューは、キューの先頭にアイテムを挿入する必要がある場合に便利です。

この記事では、アプリケーションで4種類のキューを学習しました。