データ構造
データ構造（データこうぞう、英: data structure）は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
適切なデータ構造を選ぶことで、アルゴリズムを高速化することができます。
例えば、グラフで最短経路を求める ダイクストラ法 は、オリジナルの計算量は\(O (n^2) \) ですが、優先度付きキュー を用いることで\( O (N \times \log N) \) の計算量になります。
抽象データ型 Abstract Data Type
抽象データ型（ちゅうしょうデータがた、英: abstract data type、ADT）とは、データ構造とそれを直接操作する手続きをまとめてデータ型の定義とすることでデータ抽象[1]を実現する手法またはそのひとまとまりとして定義されたデータ型を言う。通常のデータ型であれば変数宣言で変数に束縛されるものは値であるが、抽象データ型の世界において値に相当するものはデータ構造とその操作[2]のまとまり[3]である。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ADT 抽象データ型とは、具体的なデータ構造のモデルのようなもので、 そのADT が持つ操作の集合とその計算量により定義されています。
例えば、ADTの例として、スタックを挙げることができます。
抽象データ型としてのスタックは、ノード（何らかのデータを持ち、別のノードを指し示すことができる構造）のコンテナ（データを集めて格納する抽象データ型の総称）であり、2つの基本操作プッシュ(push)とポップ(pop)を持つ。Pushは指定されたノードをスタックの先頭（トップ）に追加し、既存のノードはその下にそのまま置いておく。Popはスタックの現在のトップのノードを外してそれを返す。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ADTとしてのスタックは、Push と Pop という操作を持ち、それぞれの計算量は\( O (1)\)です。
「 操作の集合とその計算量」により定義された抽象データ型を、具体的に実装すると、データ構造になります。
「スタック」という言葉の場合は、「ADT」としての意味と、「データ構造」としての意味のどちらも「スタック」という言葉で表されます。
