【ITニュース解説】The Queue: Understanding FIFO Data Structures in TypeScript

プログラミングにおいて、データを効率的に管理するための仕組みを「データ構造」と呼ぶ。その中でも特に基本的で重要なものの一つが「キュー」である。キューは「FIFO（First In, First Out）」、すなわち「先入れ先出し」という原則に基づいている。これは、日常生活における店舗のレジ待ちの行列と同じ考え方である。最初に行列に並んだ人が最初にサービスを受けられるように、キューでは最初に追加されたデータが最初に処理の対象となる。この単純明快な原則により、キューは処理の順序が重要な様々な場面で活用されている。

キューの動作は、データを一列に並べて管理することで実現される。データは列の最後尾に追加され、列の先頭から取り出される。このデータの追加操作を「エンキュー（enqueue）」、取り出し操作を「デキュー（dequeue）」と呼ぶ。この仕組みをプログラムで実装する方法として、連結リストを用いるのが一般的である。連結リストは、個々のデータを格納する「ノード」と呼ばれる単位で構成される。各ノードは、自身のデータ値と、次に連なるノードへの参照情報を持っている。これにより、データがメモリ上で物理的に連続していなくても、鎖のようにつなぎ合わせて一列の構造を形成できる。

具体的な実装を見ていく。まず、連結リストの基本単位であるノードをクラスとして定義する。このNodeクラスは、ジェネリクス<T>を用いて様々な型のデータを扱えるように設計される。Nodeクラスは、データそのものを保持するvalueプロパティと、次のノードを指し示すnextプロパティを持つ。nextは次のノードが存在しない場合、つまり末尾のノードではnullとなる。

次に、キュー全体を管理するQueueクラスを定義する。このクラスは、キューの先頭ノードを指すfirst、末尾ノードを指すlast、そしてキューに含まれる要素の総数を管理するsizeという3つのプロパティを持つ。先頭と末尾の両方を記録しておくことで、エンキュー（末尾への追加）とデキュー（先頭からの削除）を効率的に行うことができる。キューが生成される際には、これらのプロパティを初期値で設定するコンストラクタが用意される。

エンキューは、キューの末尾に新しいデータを追加する操作である。まず、追加したい値を持つ新しいNodeインスタンスを生成する。次に、現在のキューが空でなければ、現在の末尾ノード（this.lastが指すノード）のnextプロパティを、この新しく生成したノードに設定する。これにより、既存のリストの最後に新しいノードが接続される。その後、キューのlastプロパティ自体を、この新しいノードを指すように更新する。もしキューがもともと空だった場合は、firstプロパティもこの新しいノードを指すように設定する必要がある。最後に、キューのsizeを1増やすことで、エンキュー処理は完了する。

デキューは、キューの先頭からデータを取り出して削除する操作である。最初に、キューが空でないことを確認する。もしfirstがnullであれば、取り出すデータがないためnullを返して処理を終了する。キューにデータが存在する場合、現在の先頭ノード（this.firstが指すノード）を一時的な変数に保存しておく。次に、キューのfirstプロパティを、現在の先頭ノードが指していた次のノード（this.first.next）に更新する。これにより、2番目にあったノードが新しい先頭となる。この操作の結果、キューが空になった場合（新しいfirstがnullになった場合）は、lastプロパティもnullに更新し、キューが完全に空であることを示す。最後に、キューのsizeを1減らし、一時的に保存しておいた元の先頭ノードのvalueを返すことで、デキュー処理は完了する。

キューには、他にも便利な基本操作がある。「ピーク（peek）」は、デキューのようにデータを取り出すことなく、先頭のデータが何かを単純に確認する操作である。これはfirstプロパティが指すノードのvalueを返すだけで実現できる。また、「isEmpty」は、キューが空かどうかを判定する操作であり、sizeプロパティが0であるかどうかを調べることで簡単に実装できる。

以上のように、キューはFIFO原則に基づいたデータ構造であり、連結リストを利用することで効率的に実装できる。エンキューでデータを末尾に追加し、デキューで先頭から取り出すという一連の流れは、タスクのスケジューリングやデータの一時的なバッファリングなど、コンピュータサイエンスの多くの分野で応用されている。これらの基本的な操作と内部構造を理解することは、システムエンジニアとしてより複雑な問題を解決するための重要な第一歩となるだろう。