分野：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：データ構造

キュー(Queue)は、「先入先出し」の構造を持つデータ構造で、プリンターの印刷待ち、CPUの処理待ちなど何かの処理の"待ち行列"を実現する際によく使われます。
キューへのデータの追加をエンキュー(enqueue)、データの取出しはデキュー(dequeue)と呼びます。

設問のポインタで連結されたリスト構造で実装されたキューで、追加と取り出しを行うには以下のポインタの付け替え操作が発生します。

〔データの追加〕
現在、最後尾の要素が持つ次要素へのポインタに追加要素のアドレスを設定する。〔データの取出し〕
現在、先頭の要素が持つ次要素へのポインタを先頭ポインタに設定する。つまり、データの取出しでは先頭要素、追加では最後尾の要素を参照する必要が生じます。

まずは〔データの追加〕において最後尾の要素へのアクセスするための手間を考えます。最後尾ポインタのある「ウ」「エ」では最後尾の要素へ1回でアクセスできますが、最後尾ポインタがない「ア」「イ」では最後尾の要素を参照するために先頭から順番にリストを辿っていく必要があり、リスト内の要素数に比例して手間が掛かります。したがって「ウ」「エ」に実装に優位性があると判断できます。

「ウ」と「エ」は先頭・最後尾要素へのアクセスの手間は同じですが、「エ」のリストが循環型になっているためポインタ付け替え回数に違いがあります。「ウ」の実装では上記したポインタの付け替えだけで済みますが、「エ」ではそれに加えて以下の処理が発生します。

データの追加時

追加要素の次要素へのポインタに先頭要素のアドレスを設定する

データの取出し

最後尾の要素の次要素へのポインタを先頭ポインタと同じに設定する

したがって最も手間が少なくなるのは「ウ」の実装になります。