スタックとキューについて〜スタック編〜(JavaScript)

今回は2回に分けてスタックとキューについて解説します。
初回であるこの記事では、主にスタックの以下の内容について解説します。

+ そもそもスタックやキューとは何なのか
+ スタックの保存(push)の仕方
+ スタックの取り出し方（pop）
+ スタックはLast In, First Out(LIFO)
+ JavaScriptでスタックを実装
 
#そもそもスタックやキューとは何なのか
スタックやキューとは、データの保存や取り出し方の方法を指します。
スタックやキューと呼ばれる箱の中にいくつかのデータを保存し、必要な時にその箱から取り出すといったイメージです。

![dataStructure.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/355738/0d2a3579-a3e9-874a-b418-16184d2645f7.png)
図１　スタックやキューのイメージ

この2つはデータを保存する、取り出すという点では同じですが、データの保存の仕方や取り出し方に違いがあります。

##スタックの保存(push)の仕方
スタックはデータを保存された場合、スタックはデータを上に積み重ねていくように保存します。この事をpushといいます。
以下の画像の右側にあるコップのような箱がスタックです。
![stack1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/355738/49003cd4-f633-59c7-8917-7acaeeb8b9cb.png)
図２　スタック 保存のイメージ

スタックの中に青色のデータを保存してみると、図３のようになります。
![stack2-2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/355738/3276841b-5b44-0004-8419-05527844c5c8.png)
図３　青色のデータを保存

次に緑色のデータを保存すると、図４のようになります。
![stack3-2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/355738/def9c2bc-3a20-c746-efc1-eba0d8d89d54.png)
図4　緑色のデータを保存

最後にピンク色のデータを保存すると、図５のようになります。
![stack4-2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/355738/46a1ebe2-2166-9232-6624-534e1e1a9ec5.png)
図5　ピンク色のデータを保存

スタックの中身を見ますと、保存されたデータが上に積み重なっていることが分かると思います。

##スタックの取り出し方（pop）
データを取り出すとき、スタックは積み重なったデータを上から順番に取り出します。この事をpopといいます。
![pop1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/355738/a08ca704-77c2-f0fd-969d-f33485438530.png)
図6 スタック　取り出し方のイメージ

先ほどの図５の状態のスタックからデータを取り出すと、図7のようになります。
![pop2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/355738/9301ee4b-a705-5896-4745-0ea241399985.png)
図7 1回目の取り出しのイメージ

図7の状態で取り出すと、図8に、図8の状態で取り出すと図9のようになります。
![pop3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/355738/2b687b09-b881-1187-2232-56fd5a52912b.png)
図8　2回目の取り出しのイメージ
![pop4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/355738/0ac3549f-230b-2b12-e309-907ee379ba09.png)
図9 3回目の取り出しのイメージ


このようにスタックは積み重ねたデータを上から順番に取り出します。

##スタックはLast In, First Out(LIFO)
上記の例から、スタックはデータを取り出すとき、一番新しく保存したピンク色のデータから取り出しました。そして、一番初めに保存した青色のデータは一番最後に取り出されました。
このようなデータの取り出し方をLast In, First Out(LIFO)といいます。
文字通り、一番新しく保存したデータ（Last In)を一番最初に取り出す（First Out)という意味です。

##JavaScriptでスタックを実装
ここまでスタックの考え方について解説しました。ここからは実際にスタックを使ってみます。
今回は配列を使って、スタックを実装していきます。以下、実装例です。

```javascript
console.log('------スタックの実装------');
console.log('スタックのプッシュを実装');

// スタック用の配列を用意
const stack = [];
console.log('最初のstackの中身', stack);

// データを保存
stack.push('青色のデータ');
console.log('1回pushされたstackの中身', stack);

stack.push('緑色のデータ');
console.log('2回目pushされたstackの中身', stack);

stack.push('ピンク色のデータ');
console.log('3回目pushされたstackの中身', stack);

console.log('------------------------------------');
console.log('スタックのポップを実装');

// データを取り出す
stack.pop();
console.log('1回目popされたstackの中身', stack);

stack.pop();
console.log('2回目popされたstackの中身', stack);

stack.pop();
console.log('3回目popされたstackの中身', stack);
```
上記のコードを実行結果は以下の画像のようになります。
この実行結果からも、スタックがLIFOであることが分かりますね。
![coded-stack.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/355738/5ded7d28-7136-bb32-4baa-701a301e40e0.png)

#まとめ
今回は以下の内容について解説しました。

+ スタックやキューとはデータ構造のこと
+ スタックの保存の仕方について
+ スタックの取り出し方について
+ スタックはLIFO
+ JavaScriptでスタックを実装

次回は、キューについて解説します。