データ構造ぴょぴょぴょ〜〜〜ん^-^-^-^-^-^

配列

配列 = [ 1, 8, 3, 10, 4]
みたいな感じで同一の型のデータをメモリ上に一列に並べたもの。

10	1	2
3	4	5
6	9	0

２次元の配列

このような２次元の配列は、メモリ上では通常

10, 1, 2, 3, 4, 5, 6, 9, 0

のように格納される。（行優先格納）

スタック

本を上から積み重ねるのと同じ方式でデータを保存する。

データを格納（Push）する時は、今あるデータの積み重ねの上にデータを追加する。

データを取り出す(Pop)時も、今あるデータの積み重ねの一番上にあるデータを取り出すしかない。

ある処理の途中で別の処理に移る場合があるので、とりあえずスタックに中断する処理を放り込んで（Push）、割り込んだ処理が終わったら、スタックから中断した処理を取り出して（Pop）、処理を再開する。

キュー

レジの行列みたいな感じ。

先頭のデータから処理していき、新しくデータ格納する時は最後尾に格納する。

メッセージの送受信はキューを利用する。

しかしここで、スタックやキューのようなストレージシステムの問題がある。それは、要素の挿入や削除をすると、スタックやキューの位置がメモリ中をさまようことだ。
なので、何らかの方法で確保したメモリブロック中にキューを閉じ込めたい。（動かないように固定したい）
簡単な解決法はキューをブロックの中で循環させることだ。

循環キュー

ブロックの最後まで行けば、次はブロックの最初に戻るようにする。

ず

木

グラフと一緒にざっくり解説します

２分木の格納方法

大きく分けて２つの方法があります

連結リストみたいな感じでメモリに格納する方法

２分木は３つの要素からなる。
①データ
②第一子へのポインタ（左の子へのポインタ）
③第二子へのポインタ（右の子へのポインタ）

最初にルートポインタと呼ばれる特別なメモリ場所を確保し、その場所に根のアドレスを格納する。
木へアクセスするときは、まずここに来る。

図

木全体を１つの連続したメモリセルに格納する方法

ず

このように長く細い枝があると、メモリの使用効率が悪いが、
長く細い枝がない（根の下の部分木が大体同じ長さ）なら、効率がいい。

ユーザ定義のデータ型

プログラミング言語が既に提供（用意）してくれているデータ型でなく、基本のデータ型を使ってユーザが新しくデータ型を定義できるようになっている。
個別のデータ型を定義は大抵はアルゴリズムの記述が容易にするために行う。

例えば、すべて同じ構造体で、多くの変数を持つプログラムを開発したいとする。
その構造体は、名前、年齢、技能評価からなる。

一応、各変数（人間）を個別に構造体として定義しても、そりぁまぁエラーは起きないが、大変。
より良いアプローチは、構造体を（ユーザ定義の）新しいデータ型として定義してから、その構造体を使い回す（その新しい型を基本型と同じように使用する）方がはるかに楽だ。

抽象データ型

ユーザ定義のデータ型は便利だが、完全に新しい概念のデータ型を生成はできない。

完全なデータ型は
・前もって定義された格納システム（整数型なら2の補数体系。実数なら不動小数点体系。みたいな）
・前もって定義された演算の集合（可算。減算。みたいな）
が備わっている。

どう違う？

演算の定義　＋　ユーザ定義のデータ型　＝　抽象データ型

そもそも、プログラミング言語の基本データ型(intとか)には、基本演算が関連付けられていて、プログラマが変数を基本型として宣言したら、（プログラマが演算を遅疑しなくても）変数に基本演算を適用できる。

しかし、格納システムだけのユーザ定義のデータ型（１つ目に紹介したやつ）では、そのデータ上で実行できる演算は提供されない。

例えば、スタックを２０個の整数値をもつ配列で実現してみよう。

// コード１
define type StackType to be
{int StackEntries[20];
 int StackPointer = 0;
}

これでユーザ定義の型を生成できた。
これのおかげで

StackType StackOne, StackTwo, StackThree;

と書けば、もうスタックが３つできた。
しかし、

push(25, StackOne)

のような操作はpushと名付けられた手続きを定義しないと使用できない。
なので、「コード１」をもうちょいしっかり定義する。（↓では簡易的に書いているので、実際のコードとしては不十分）

define type StackType to be
{int StackEntries[20];
 int StackPointer = 0;
 produce push(value)
  {StackEntries[StackPointer] ← value;
   StackPointers ← StackPointers + 1;
  }
 produce pop　・・・・・・・
}

のように型StackTypeにStackEntriesとStackPointerという変数と共に、pushやpopという手続きを結びつけている。
こうした上で、

StackType StackOne, StackTwo, StackThree;

と定義して、

StackOne.push(25);

のようにして、要素をプッシュする。

ちなみに、オブジェクト指向言語は、この抽象データ型をさらに拡張したクラスというものを備えている。

オブジェクト指向言語って？？

プログラミング言語の歴史上何個かパラダイム（歴史的な発展）があり、オブジェクト指向パラダイムはその１つです。このオブジェクト指向パラダイムはソフトウェア開発で最もすごいパラダイムと言われています。とにかく画期的ってことですね。
では見ていきましょう。

オブジェクト（ソフトを構成する単位）

ソフトウェアシステムはオブジェクトと呼ばれる単位の集合として見られる。

直訳は「対象となる物」

各オブジェクトは、それ自身や他のオブジェクトからの要求によって、何らかの動作を実行できる。そのようなオブジェクトの相互作用によって、問題を解決できる。

例として、GUI（グラフィティカル　ユーザ　インタフェース）の開発を考えよう。
オブジェクト指向の環境では、スクリーン上に現れるアイコンはオブジェクトとして実装される。
そのようなオブジェクトはクリックされたりドラッグされる訳だが、こうしたイベントにオブジェクトがどのように反応するかを記述した手続き（メソッドと呼ぶ）の集合を含んでいる。
つまり、システム全体は、関連するイベントにどう反応すればいいかを分かっているオブジェクトの集合となっている。

クラス（オブジェクトの性質いちいち書かなくて済むやつ。設計図。）

例えば、リストをオブジェクト指向のプログラミング言語で記述する場合、リストとリストを扱うメソッドの集まりからなるオブジェクトを作る。
このようなオブジェクトの性質の記述を、クラスと呼ぶ。

クラスが構成されると、その記述された性質を持つオブジェクトが必要なときに、いつでも適用できる。
つまり、複数のオブジェクトが１つのクラスに基づいている。

俗に”型”と言ったりもする。
クラスというテンプレートを使って、その”型”のオブジェクトを構成する。みたいな。

クラスとデータ型って似てる？どう違う？

似てる点

データ（整数型なら1,3,8みたいな整数。クラスならインスタンス変数（※後述））を格納するシステムもあり、データに対する演算（整数型なら足し算とか。クラスならメソッド）がある。

言い換えると、1, 5, 21のような数に共通の性質（足し算や引き算ができる、とか）を整数型という基本データ型が包含するように、
複数のオブジェクトに共通する性質をクラスは記述している。

どう違うか

実は、クラスは抽象データ型を拡張したもの。

クラスは他のクラスから性質を継承でき、個々のオブジェクトを生成するときにカスタマイズできる特別なメソッドもある（コントラクタと呼ぶ）。
さらに、クラスは、関連する手続きをグループ化する手段としても使用されることがあるので、手続きだけからでもクラスとして成立する。
この点から、抽象データ型よりも一般的といえる。

インスタンス

特定のクラスに基づいたオブジェクトを、そのクラスのインスタンスと呼ぶこともある。

オブジェクトの中にある変数をインスタンス変数と呼び、オブジェクトの中にある手続きをメソッドと呼ぶ。

オブジェクトとインスタンスって何が違うん？？？？

これはよくある疑問です。いくつか記事を読みましたが正直「多分これで合ってるはず」って感じです。

ざっくりいうと、インスタンスはオブジェクトの一種です。

オブジェクト　ー　インスタンス　＝　概念としてだけのオブジェクト
みたいな。

クッキー作りに例えると、
クラス：星とかハートとかの金型
インスタンス：金型でくり抜いて目の前にあるクッキー
オブジェクト：概念としてのクッキーor金型でくり抜いて目の前にあるクッキー（インスタンスと呼ぶことが多い）

適当に金型（クラス）を１つ選んでクッキー（オブジェクト）を作ろう。
その金型で実際にくり抜いたクッキー（インスタンス）

ちなみにメソッドは調理にあたるでしょう。「焼く」というメソッドなら
クッキー.焼く();
って感じです。

少し真面目っぽく書くとこうです。

オブジェクト
実世界のオブジェクト（人やもの）も状態と振る舞いの大きく２つの要素に分けて問えることができる。
例えば人間なら、状態は年齢、名前。振る舞いは走る、眠る。
車なら状態は、重さ、ギアは何速か。振る舞いはブレーキを効かせる、ギアを変える。
ソフトウェアの「オブジェクト」も概念としては大体同じ。
何か状態があり、振る舞いも携えている。

インスタンス
クラスからできた具体的なコピー