【データ構造】スタックとキュー、リスト、配列、木構造、2分木

IPA試験対策

2019.01.25

スタックとキュー、リスト、配列、木構造、2分木についてまとめました。

【スタックとキュー】

種別	概要
キュー	先に入ったもを先に出します（キュー）。FIFO(First In First Out) とも呼ばれる。先入れ先出し以外のアクセスが遅いのが欠点。
スタック	後に入ったものを先に出します（スタック）。LIFO(Last In First Out) とも呼ばれる。後入れ先出し以外のアクセスが遅いのが欠点。

データ構造に対する各種操作は以下のとおりです。

操作	概要
探索	データを取り出すために指定したキーの値をもつデータの位置をみつける操作です。
削除	指定したキーの値をもつデータを削除する操作です。
挿入	新しいデータを追加する操作です。

用語	概要
配列	データを並べたデータ形式で、ほとんどのプログラミング言語に存在する基本的な形式のひとつ。配列に含まれるそれぞれのデータを要素といい、キーによって識別される。【利点】・挿入が高速・インデックスがわかればアクセスは高速【欠点】・探索・削除が遅い・サイズが固定
順序配列	並び順に要素が並んでいる（ソートされている）配列。【利点】・単純な配列より高速【欠点】・挿入・削除が遅い・サイズが固定