2-1-1配列構造

• データ構造

　プログラムを実現する為には、どのようなデータが必要で、そのデータに対してどのような操作をしたらよいか明確にする必要があります。プログラム間でやりとりされるデータ構造は、プログラム全体に影響を及ぼします。特に、配列におけるデータ構造は重要です。

• 配列

　配列とは、同じ属性を持ったデータを集め、そのデータを添え字(インデックス)によって識別する構造を持ったものをいいます。配列は、添え字の数によって1次元配列、2次元配列といった構造体になります。
　配列は、ほとんどのプログラミング言語でサポートされているもっとも基本的なデータ構造です。配列構造の代表的なものにスッタク構造、キュー構造、リスト構造があります。

※POINT

代表的なデータ構造として、配列、スタック構造、キュー構造、リスト構造、ツリー構造がある。

• スタック構造

　1次元配列で格納されたデータにおいて、後から入れたものを先に出す構造をいいます。スタックにデータを格納することをpush(プッシュ)といい、格納したデータを取り出すことをpop(ポップ)といいます。スタックでの格納と取り出しは、ともにリストの先頭に対して行われ、もっとも新しく格納されたデータが最初に取り出されることになります。このようなデータの出し入れをLIFO(Last-In First-Out :後入れ先出し)と呼びます。
　スタック構造は、プログラムの実行中にサブルーチンを呼び出すときなどに使用されます。

※基本用語

スタック

棚という意味があり、データを順番に格納する1次元配列の箱のことをいう。

• キュー構造

　1次元配列で格納されたデータにおいて、一方の端からデータを入れ、他方の端からデータを取り出す構造をいいます。待ち行列ともいいます。
　キューにデータを格納することをenqueue(エンキュー)といい、取り出すことをdequeue(デキュー)といいます。キューではもっとも古いデータから取り出されます。このようなデータの出し入れをFIFO(First-In First-Out:先入れ先出し)と呼びます。
　キュー構造は、ディスクの入出力やオペレーティングシステムでのタスクの実行などで幅広く使用されています。

※基本用語

キュー

列という意味があり、データを順番に格納する1次元配列の箱のことをいう。

FIFO(First-In First-Out)

待ち行列の典型で､多くの社会生活においてもスーパーでのレジや電話の行列などはまさにFIFOである。

• リスト構造

　リスト構造とは、順序づけされたデータの集合体をいいます。リスト構造の各データは、データ部とポインタ部を対として持っているセルによって構成されています。リスト構造のデータ領域は必ずしも連続領域とは限りません。データのつながりは、ポインタ部に示された次のデータのアドレスを参照することでデータの並びを管理しています。
　リスト構造には、ポインタの管理の仕方によって、単方向リスト、双方向リスト、循環リストがあります。

※基本用語

ポインタ

他のデータへの参照を示す値で、そのデータのアドレスが入っている。

　単方向リスト
　ポインタには次のセルの場所が位置づけられていて、一方向にだけたどっていくリスト構造です。単方向リストの特徴は、データの挿入、追加、削除が、ポインタを変更することによって容易に行える点にあります。最後のセルにはポインタはなく、データのみが存在します。

　双方向リスト
　前のセルへのポインタと次のセルへのポインタといった2つのポインタを持たせ、前後に自由にリストをたどることが出来るようにしたリスト構造です。最後のセルへのポインタとデータはありません。

　循環リスト
　双方向リストと同様に、前のセルへのポインタと次のセルへのポインタといった2つのポインタを持ったリスト構造です。双方向リストとの違いは、最後のセルの次ポインタに先頭データがあるセルのアドレスが示されており、各データが環状に連結する構造となっている点です。