データ構造(キュー・スタック・配列・連結リスト・木構造)について

## はじめに
この記事とは関係ありませんが、実はこの記事を書く直前まで、会社の人におすすめされた映画 **『シャッターアイランド』** を観ていました。普段は映画に集中し続けることができない私でも、見入ってしまった作品なのでおすすめです！
ただ、ちょっと怖いシーンとかもあったのでちょくちょく目や耳を隠しながら観てました😂

https://www.netflix.com/jp/title/70095139

雑談はここまでにして本題に入ります！
**※途中で出てくるイラストはイメージです**

## 目次
- 記事を書こうと思った理由
- データ構造とは
- スタック
- キュー
- 配列
- 連結リスト
- 木構造
- まとめ
- さいごに

## 記事を書こうと思った理由
エンジニア歴が1年以上になる中で、会社のテストを通じてデータ構造に関する知識が不足していると痛感し、また教わる側から教える側に移行する中で自分の理解の浅さを感じる場面が増えたため、この機会にアウトプットを通じて理解を深め、自分自身の成長にも繋げたいと感じたためです！

## データ構造とは
コンピュータが扱う情報のことを「データ」といい、データはコンピュータ内にある「**主記憶装置**」と呼ばれる記憶装置に保存されます。
コンピュータの処理効率は**データの並べ方**によって大きく変わります。そのため、主記憶装置に保存されるデータは、処理の内容やその時の状況に応じて、さまざまな方式で並べられます。
この、主記憶装置上のデータの並べ方のことを「**データ構造**」と言います。
そして、そのデータ構造には以下の5種類があるみたいです。
1. スタック(Stack)
2. キュー(Queue)
3. 配列
4. 連結リスト
5. 木構造

以下でそれぞれの特徴と使用用途を説明します！

## スタック(Stack)
### 特徴
「LIFO(LastIn,FirstOut)」方式のデータ構造。
最後に追加されたデータが最初に取り出されるという、積み重ねた本のようなイメージです。
スタックにデータを格納することをpushといい、反対に取り出すことをpopという。
### 使用用途
- ブラウザの「戻る」ボタンのような、直前の状態に戻す操作
- 文字列の逆順表示や再帰処理の管理

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3530812/59d007dd-93b8-3314-190a-bc2439b5ba5e.png)

## キュー(Queue)
### 特徴
「FIFO(FirstIn, FirstOut」方式のデータ構造。
名前の通り、最初に入れたデータが最初に出るという、レジ待ちの列のようなイメージです。
キューにデータを入れることをenqueue(エンキュー)といい、反対に取り出すことをdequeue(デキュー)という。
### 使用用途
- プリンターの印刷ジョブ
- CPUのタスクスケジューリング

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3530812/c12a2202-f993-1a21-a3dc-e21764604024.png)

## 配列(Array)
### 特徴
同じ型のデータを連続してメモリに格納する構造。
1つの1つのデータを要素といい、要素の位置を表す数字を添字(インデックス)という。

### 使用用途
- 順番に並んだデータを一括で処理する場合
- ランダムアクセスが求められる場合(インデックス指定で素早くアクセスできるため)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3530812/6b1cd281-8a9e-e179-7d09-4e5c01cc1d36.png)

## 連結リスト(Linked List)
### 特徴
データを数珠繋ぎに並べたデータ構造。
配列と同じように、個々のデータを「要素」と呼ぶ。ただし、連結リストの要素は配列の要素と異なり、データに「ポインタ」が付く。
**ポインタ**とは、次の要素のアドレス(主記憶装置上のデータの位置)を指し示すもの。
コンピュータは、ポインタに格納されているアドレスをたどることで目的のデータにアクセスする
### 使用用途
- 頻繁にデータの挿入・削除が発生する場合、特にリストの中間部分への操作
- サイズの事前確保が難しい場合(チャットアプリのメッセージ履歴管理)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3530812/b53cd06b-722d-3f0f-cdda-07117d42c83d.png)

---
### [余談] 配列と連結リストの違い
配列と連結リストはともに「**データが順番に並んでいる**」という点は同じですが、データにアクセスする方法が異なります。
配列では、添字(インデックス)を使うことで**データに直接アクセス**できます。一方で連結リストの場合は、**連結リストの先頭から順番に要素を辿って**目的のデータにアクセスする必要があります。そのため、連結リストの場合、要素数が多ければ多いほど、データへのアクセスに時間がかかります。
このように聞くと、連結リストよりも配列の方が優れているように感じるかもしれませんが連結リストにもメリットがあります。それは、**データを挿入・または削除する際**です。
配列に要素を挿入・削除する際は、後ろの要素を全て1つずつずらす必要があります。そのため、要素数が多ければ多いほど処理に時間がかかります。一方、連結リストの場合は、**ポインタを変更するだけ**でデータを挿入・削除できるので迅速に処理を行うことができます。

こちらの記事に詳しく書かれていました。

https://zenn.dev/masahiro_toba/books/436c018f5cd4e2/viewer/af0195

---

## 木構造(Tree)
### 特徴
階層構造を表現するデータ構造。
植物の木を逆さにしたような形をしており、ノードと呼ばれる要素が親子関係を持ちます。
一般的には「ルート」から始まり、複数の「枝」と「葉」に分岐していきます。
### 使用用途
- データベースの索引やファイルシステムのディレクトリ構造
- Webページのドキュメントツリー

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3530812/ea5a72a7-f53d-6867-74c8-c6eb355803cc.png)

## まとめ
今回、データ構造が効率的な情報処理において重要な役割を持つことを学びました。
各データ構造の特徴を理解し、適切に使い分けることで、コードのパフォーマンスを向上させることができるため、今後は、さらに多くのデータ構造とアルゴリズムを学び、実際の開発に応用できるスキルを磨いていきたいと感じました！

## さいごに
私の働いている会社で経験の有無を問わず採用を行っています。
興味のある方は是非カジュアル面談から応募してみてください！

https://jambo-support.com/recruit_engineer/

---
参考文献

https://amzn.asia/d/6grqUJg

https://zenn.dev/brainyblog/articles/data-structures-beginners-guide