そもそもデータ構造とは？

パソコンで扱われる数値データを扱いやすいようにまとめた塊のことです。

種類

変数
配列
リスト
キュー
スタック
木(ツリー)構造

変数

値を格納する箱のようなものです。

配列

沢山ののデータを一箇所にまとめて入れておくタンスのようなものです。

配列のメリット

添字を指定して値にアクセスすることが出来る

配列のデメリット

データの追加や削除が苦手

配列とリストの違いがピンと来ない人へ

Javaの場合はList型とArray型という明確な区別があります。
Listは可変であり、Arrayは固定なので後からカジュアルに値を追加することが難しいです。
Rubyの場合はArrayであっても値を後から追加可能なのでJavaのListとArrayをいい感じに融合したものであるというイメージで良いのかもしれません。

$ array = [0,1]
=> [0, 1]
$ array << 2
=> [0, 1, 2]

eng-entrance.com

キュー：First In First Out

コンピューターは高速に処理を行えるものの、中には時間が掛かってしまう重たい処理があります。そんな時間がかかる処理が沢山ある場合に使われるのがキューです。イメージとしてはレジに並ぶ人を順番に処理するそれと同じで、一番初めに来た人が初めに処理されます。パソコンの処理ではプリントアウトの時などがわかりやすい例かもしれません。
RailsにおいてはSidekiqの処理がこのキューを使った処理にあたります。

スタック：Last In First Out

処理するものを一旦待避させておきたい時にスタックを使います。
スタックとはお皿をお皿の上に積み上げていくような状態で、後から入れたデータが常に先に出てくるデータ構造です。
ブラウザの戻るボタンでこの仕組みが使われています。

木(ツリー)構造

沢山のデータを階層構造として扱うのが必要な場合に使われます。
木に例えて、頂点をルート(頂点)、枝分かれするところをノード(節)、枝部分をブランチ(枝)、先端部分をリーフ(葉)と呼びます。ハードディスクのファイルシステムで主に使われています。

まとめ

複雑なロジックやアルゴリズムもこれらの組み合わせで出来ているみたいなので、まずデータ構造から学び直してみようと思い、雑にまとめてみました。この後はRubyを使って有名なアルゴリズムの数々を勉強していこうと思います。

参考文献

楽しく学ぶアルゴリズムとプログラミングの図鑑(p56~59)

https://www.amazon.co.jp/%E6%A5%BD%E3%81%97%E3%81%8F%E5%AD%A6%E3%81%B6-%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%AE%E5%9B%B3%E9%91%91-%E6%A3%AE-%E5%B7%A7%E5%B0%9A/dp/4839960216/ref=sr_1_1?__mk_ja_JP=%E3%82%AB%E3%82%BF%E3%82%AB%E3%83%8A&keywords=%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E5%9B%B3%E9%91%91&qid=1556848091&s=gateway&sr=8-1www.amazon.co.jp

カクカクしかじか

技術的なアレコレ

データ構造を雑にまとめる