新人SEのための楽しく学ぶアルゴリズム　第2回（5）

データ構造

矢沢久雄

2000.10.20

データ構造はアルゴリズムと表裏一体
同時に考えてプログラムに仕立てる

講師　矢沢　久雄

木構造による効率的なサーチ

図14●単純な配列と木構造の比較
単純な配列を利用した場合，順番にたどっていかなければならない。図の例の場合，6つの経路をたどることになる。木構造を利用すれば，どの値を検索する場合でも経路は2つで済む

　「木構造」は，双方向のリスト構造を応用して配列に格納されたデータを根（ルート）から2つずつ枝分かれする構造にしたものである。木構造では，左側の枝に小さいデータ，右側の枝に大きいデータを格納する。このデータ構造を採用すると，単純な配列に比べて目的のデータをより短い経路でサーチできる（図14[拡大表示]）。

スタックとキュー

　他に，プログラムが次々とデータを受けるような状況でよく利用されるデータ構造として，「スタック」および「キュー」と呼ばれるものがある。スタックもキューもプログラム・コード上では配列として実現されるのだが，配列のインデックスを意識しないで利用できる。データを格納する一種のオブジェクトである。

　スタックはLIFO（Last In First Out）といって，最後に格納されたデータが最初に取り出される仕組みである。スタックとは「干草を積んだ山」という意味である（図15[拡大表示]）。スタックは，データを一時的に保存するためと，簡単な手順でデータの交換を行うために利用する場合が多い。

図15●スタックの構造
スタック，キューの両方とも，データを一時的にためるためのデータ構造。スタックは，最後に入れたものを最初に取り出すデータ構造

　キューはFIFO（Fisrt In First Out）といって，最初に格納されたデータが最初に取り出される。キューは「待ち行列」とも呼ばれ，一度に大量に入力されたデータの処理が間に合わない場合のバッファ＊10の役割をするものである（図16[拡大表示]）。

　例えば，皆さんが利用しているパソコンのキーボード・ドライバ＊11に，キューが利用されている。ワープロ・ソフトで文字入力を行っているときに，キー入力から若干遅れて文字が表示されることがあるだろう。これは，あまりに高速なキー入力によるデータを，一時的にバッファに格納し，皆さんが一呼吸置いたタイミングでキューからワープロ・ソフトにデータが取り込まれているからである。

　誌面の都合でスタックとキューのサンプル・プログラムを省略するが興味のある方は参考文献＊12を参照してほしい。