私たちは仕事などで様々なデータを扱うっすが、それらのデータはデータベースにきれいな形で整理・管理されているからこそ効率的に扱うことができるんすよ。
へぇー、今まで意識したことはなかったけどデータってそんな感じで管理されているんだね。
データ構造は次回学習するアルゴリズムを理解するための基礎知識になるっす。
| 目標 | ・データ構造の基本的な考え方を理解する。 |
| 説明 | ・業務データの分析や整理を行うために，データ及びデータ構造の基本的な考え方を理解する。 |
データ構造とは
コンピュータが取り扱うデータは一定の形式に従って格納されていますが、この形式のことをデータ構造といいます。
コンピュータの処理では、どのようにデータを格納して整理するかによってプログラムでのデータの扱いやすさが決まります。そのため、データ構造について理解し、それを適切に選択・使用することが、プログラミングにおいては重要な要素となります。
テーブル
情報を格納する表のことをテーブルといいます。このテーブルにおいて、データを１行に並べたもの（表の行のあたるもの）をレコードと呼び、表の列にあたるものをフィールドと呼びます。
この辺については、データベースのところでもう少し詳しく学習するっす。
フィールド内のデータを1列に並べたものを配列といいます。例えば、学生の平均点を知りたい場合は、各学生の得点だけが分かればいい（ほかの情報は必要ない）ので、「得点」のフィールド内のデータを [65, 93, 71,48]といった形で並べておくとプログラムで処理しやすくなります。
変数
プログラムで扱うデータを一時的に記憶する領域のことを変数と呼びます。変数はいわばデータを入れる箱のようなものです。この箱（変数）にいろいろな数値や文字を代入することによって、プログラムの実行結果を変化させることができます。
例えば、テストの得点が70点以上であれば「合格」、69点以下であれば「不合格」を出力するというようなプログラムを作りたいとします。
もし変数を使わなければ、0点のときは「不合格」、1点のときは「不合格」、2点のときは「不合格」・・・・、70点のときは「合格」、71点のときは「合格」・・・と、0点から100点までの101通りのプログラム文を用意しなければなりません。
しかし、変数を用いることで「変数”得点”に受験者の得点を代入し、変数”得点”が70点以上であれば「合格」、69点以下のときは「不合格」を出力する」というようなプログラム文を用意すれば、短いプログラム文で早く正確に処理することができるようになります。
木構造
ひとつの要素が複数の子要素を持ったデータ構造を木構造（ツリー構造）といいます。階層が深くなるほど枝分かれしていき、木をひっくり返したような構造になっていることから木構造と呼ばれます。
なお、要素が最大で2つの子を持つ木構造のことを2分木（バイナリツリー）といいます。2分探索法というデータの探索アルゴリズムなどで利用されます。
スタックとキュー
データの入力や出力（削除）を行う場合、その順序が問題となることがあります。この基本的な考え方となるものがスタックとキューです。
スタック
コンピュータにおける基本的なデータ構造の1つで、データを後入れ先出し（LIFO: Last In First Out）の構造で保持します。つまり、後から入力したデータ（もっとも新しいデータ）を先に出力するという考え方です。
積み上げた本を上からとっていくようなイメージっすね。
push（プッシュ）で指定したデータを追加し、pop（ポップ）でデータを1個取り出します。
スタックのデータ構造で、push a → push b → pop → push c、の順序で操作を行った場合。
popの操作では、最も新しい直近のデータ「b」を取り出します。
キュー
コンピュータにおける基本的なデータ構造の1つで、データを先入れ先出し（FIFO: First In First Out）の構造で保持します。つまり、先に入力したデータ（もっとも古いデータ）を先に出力するという考え方です。
レジなどの待ち行列のようなイメージっすね。
enq（エンキュー）で指定したデータを追加し、deq（デキュー）でデータを1 個取り出します。
キューのデータ構造で、enq a →enq b → deq →enq c、の順序で操作を行った場合。
deqの操作では、最も古いデータ「a」を取り出します。
確認○×問題
情報を格納する表のことをテーブルと呼び、データを１行に並べたものをフィールド、表の列にあたるものをレコードという。
答え：×
フィールドとレコードの説明が逆になっています。正しくは以下の記述となります。
情報を格納する表のことをテーブルと呼び、データを１行に並べたものをレコード、表の列にあたるものをフィールドという。
二つの変数xとyに対して、次の手続きを1から順に実行する。処理が終了したとき、xの値は”4”になる。
（手続き）
- xに2を代入し、yに3を代入する。
- yの値から1を引いたものをyに代入する。
- xの値とyの値を加えたものをxに代入する。
- y≠1なら手続き2に戻り、y＝1なら終了する。
（出典：平成22年度秋期分 問69一部改変）
答え：×
変数xと変数yの値を表にすると次のようになります。
| 手続き | 変数x | 変数y |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 2 | 2（=3-1） |
| 3 | 4（=2+2） | 2 |
| 4 | 4 | y≠1なので手続き2に戻る |
| 2 | 4 | 1（=2-1） |
| 3 | 5（=4+1） | 1 |
| 4 | 5 | y＝1なので終了 |
以上より、処理が終了したときのxの値は”5”になります。
変数AとBに格納されているデータを入れ替えたい。データを一時的に格納するための変数をTMPとすると、次の手順によってデータを正しく入れ替えることができる。ここで”x←y”は、yのデータでxの内容を置き換えることを表す。
- TMP←A
- A←B
- B←TMP
（出典：平成22年度春期分 問53一部改変）
答え：〇
変数AとBに格納されているデータを入れ替えたい場合、いきなり「A←B」としてしまうと、AのデータがBのデータで上書きされ、Aの内容が消えてしまいます。そこで、いったん変数TMPにAのデータを逃がしてやる必要があります。
変数Aに格納されているデータを「a」、変数Bに格納されているデータを「b」として考えていきます。
| 手順 | 変数A | 変数B | TMP |
|---|---|---|---|
| 1 | a | b | a |
| 2 | b | b | a |
| 3 | b | a | a |
木構造では、ひとつの親要素がもつ子要素は常に２つでなければならない。
答え：×
ひとつの要素が複数の子要素を持ったデータ構造を木構造（ツリー構造）といいます。なお、要素が最大で2つの子を持つ木構造のことを2分木（バイナリツリー）といいます。
下から上へ品物を積み上げて、上にある品物から順に取り出す装置がある。この装置に対する操作は、次の二つに限られる。
PUSH x：品物 xを１個積み上げる。
POP：一番上の品物を１個取り出す。
最初は何も積まれていない状態から開始して、a、b、cの順で三つの品物が到着する。一つの装置だけを使った場合、以下のPOP操作で取り出される品物の順番として不可能なものが２つある。
- a,b,c
- b,a,c
- c,a,b
- c,b,a
（出典：令和元年度秋期分 問62一部改変）
答え：×
スタックは、コンピュータにおける基本的なデータ構造の1つで、データを後入れ先出し（LIFO: Last In First Out）の構造で保持します。push（プッシュ）で指定したデータを追加し、pop（ポップ）でデータを1個取り出します。
1.の順番での取り出し（可能）：a,b,c
①push a：[a]
②pop：[ ]→aを取り出す
③push b：[b]
④pop：[ ]→bを取り出す
⑤push c：[c]
⑥pop：[ ]→cを取り出す
2.の順番での取り出し（可能）：b,a,c
①push a：[a]
②push b：[a,b]
③pop：[a,b]→bを取り出す
④pop：[a]→aを取り出す
⑤push c：[c]
⑥pop：[ ]→cを取り出す
3.の順番での取り出し（不可能）：c,a,b
①push a：[a]
②push b：[a,b]
③push c：[a,b,c]
④pop：[a,b]→cを取り出す
⑤次にpop操作をするとbが取り出されます。したがって、スタックではcの次にaを取り出すことはできません。
4.の順番での取り出し（可能）：c,b,a
①push a：[a]
②push b：[a,b]
③push c：[a,b,c]
④pop：[a,b]→cを取り出す
⑤pop：[a]→bを取り出す
⑥pop：[ ]→aを取り出す
以上より、POP操作で取り出される品物の順番として不可能なものは１つ（3.の順番）です。
先入れ先出し（First-In First-Out, FIFO）処理を行うのに適したキューと呼ばれるデータ構造に対して「8」、「1」、「6」、「3」 の順に値を格納してから、取出しを続けて2回行った。2回目の取出しで得られる値は「1」である。
（出典：平成30年度春期分 問96一部改変）
答え：〇
キューは、コンピュータにおける基本的なデータ構造の1つで、データを先入れ先出し（FIFO: First In First Out）の構造で保持します。enq（エンキュー）で指定したデータを追加し、deq（デキュー）でデータを1 個取り出します。
キューでは古いデータから先に取り出すため「8」、「1」、「6」、「3」の順に値を格納した場合、取り出しの順番も「8」、「1」、「6」、「3」の順になります。したがって、2回目の取出しで得られる値は「1」となります。
スタックとキューの二つのデータ構造がある。次の手続を順に実行した場合、変数xに代入されるデータは「b」である。ここで、
データyをスタックに挿入することを push(y)、
スタックからデータを取り出すことを pop()、
データyをキューに挿入することを enq(y)、
キューからデータを取り出すことを deq()、
とそれぞれ表す。
①push(a)
②push(b)
③enq(pop())
④enq(c)
⑤push(d)
⑥push(deq())
⑦x ← pop()
（出典：応用情報技術者試験 平成16年度春期分 午前問10一部改変）
答え：〇
少しややこしいのですが、図を描きながら考えるとわかりやすいと思います。
①push(a)：スタックに「a」を追加する
②push(b)：スタックに「b」を追加する
③enq(pop())：キューに「スタックから取り出した値(b)」を追加する
④enq(c)：キューに「c」を追加する
⑤push(d)：スタックに「d」を追加する
⑥push(deq())：スタックに「キューから取り出した値(b)」を追加する
⑦x ← pop()：xに「スタックから取り出した値(b)」を代入する
よって、変数xに代入されるデータは「b」となります。
