目次
用語集
- キュー
抽象データ型であり、最初に入った要素が最初に出てくる線形データ構造 - ファーストイン・ファーストアウト（FIFO）
最初に入った要素が最初に出てくるデータ構造 - エンキュー
キューに要素を追加する - デキュー
キューから要素を削除する - 有限キュー
追加できる要素数に上限があるキュー - 無限キュー
追加できる要素数に上限がないキュー
キューをいつ使うのか
- スタックと同様に、キューはデータの追加や削除を効率的に行える
- キューのサイズに関係なく、エンキューとデキューの計算量はともに O(1)
- 逆に、スタックと同じようにキューは個々のデータの参照は非効率。見つけるまでキューの要素を1つずつ辿らなければならないため。 O(n)
- プログラマーは、キューを頻繁に使う
- キューはFIFOに理想的なデータ構造
- たとえばキューは、コールセンターのような自動電話対応のシステムで役立つ
- 話中のときに、電話してきた人をいったん列に並べて、先にかけてきた人から空いた担当者につなぐようなシステムのプログラミングに役立つ
- OSにおいては、HDDへのデータの書き込み、音声やビデオの