[プログラミングの基礎] キューとは
キューとは、コンピューターで扱うデータ構造の一種です。ここでは、キューについて説明します。
広 告
目次
前提条件
- 特になし
動作確認環境
- 特になし
1. キューとは
キューは、格納した順序でデータを取り出すことのできるデータ構造です。先に格納したデータから順番に取り出す構造です。このような特徴を「FIFO（First-in First-out）」または「先入れ先出し」といいます。
データをキューに格納することをエンキュー（enqueue）といい、キューから取り出すことをデキュー（dequeue）といいます。
エンキューで加えられたデータは、待ち行列の末尾に加わります。1つデータを加えた場合は、行列の長さが1増えます。デキューで取り出されるデータは、待ち行列の先頭から取り出されます。1つデータが取り出された場合は、行列の長さは1減ります。
2. リングキューとは
デキューによってキューの列は1つだけずれます。キューに割り当てる領域が少ないと、デキューにエンキューが間に合わず、待ち行列があふれてしまいます。しかし、キューに割り当てる領域を無限に大きくすることは非効率です。そこでキューからのあふれを防ぐため、待ち行列の先頭と末尾をつないでリングキューにすることがあります。
物理的にリング型の領域を配置することはできません。配列の添え数を領域サイズで割って剰余を取り、範囲を制限することで論理的に領域の両端を接続して疑似的に環状にしています。キューのサイズをnとすると、配列[n-1]の次の要素は配列[0]です。リングキューにすることで、配列の先頭にできる空き領域を再利用できます。
直線のキューでキュー操作があった場合、実際にデータを1つずつ移動させていると処理に時間がかかります。そこで、待ち行列全体を移動させるのではなく、先頭が1つだけ後ろに下がる動きをします。この場合は、直線キューでは先頭がどんどん後ろに下がっていき、確保した領域の最後にきてしまいます。一方、リングキューならば先頭が移動しても循環するだけなので問題がありません。