データ構造

1. スタック

後入れ先出しのデータ構造。データを取り出す時には最後のデータが取り出される。
わかりにくく言うと... 焼き鳥の串をイメージしてください！
最後に刺した肉から食べていきますよね。そんなイメージです。
スタックにデータを入れることをpush、取り出すことをpopと言う。
CPUのレジスタや関数呼び出しなどに用いられる。

2. キュー

先入れ先出しのデータ構造。データを取り出す時には最初のデータが取り出される。
これもわかりにくく言うと... ロケット鉛筆をイメージしてください！
最初に入れた芯が外に出て来ますよね。そんなイメージです。
キューにデータを入れることをenqueue、取り出すことをdequeueと言う。
プリンタ出力など処理の順番が重要な場合に用いられる。

3. リスト

順序づけられたデータの並びで、データ部分とデータの並びを格納するポインタ部を合わせて管理する。データの先頭は先頭ポインタが指し示している。最後方のデータに簡単に辿り着ける様に末尾ポインタを用いる場合もある。

また、各データは別のデータへのポインタを持っているが、次のデータへのポインタのみを持つ物を単方向リスト、前後のデータにそれぞれポインタを持つ物を双方向リスト、最後尾のデータから先頭に戻って環状につながる物を環状リストと呼ぶ。

4. 木

樹形図で表せる様な、親ノードと子ノードの関係によるデータ構造。
親ノードに対して子ノードが二つのものを2分木、三つ以上持てるものを多分木と呼ぶ。
特に、一つの段が完全にいっぱいになるまで次の段にいかない木を完全木と呼ぶ。
もっとも子のノードを葉、もっとも親のノードを根という。
木についてはもっと勉強したいな〜

ヒープ
完全二分木の中でも、「子ノード>=親ノード」もしくは「子ノード<=親ノード」が常に成り立つものをヒープと呼ぶ。

ホームへ