今回は2回に分けてスタックとキューについて解説します。
初回であるこの記事では、主にスタックの以下の内容について解説します。
- そもそもスタックやキューとは何なのか
- スタックの保存(push)の仕方
- スタックの取り出し方（pop）
- スタックはLast In, First Out(LIFO)
- JavaScriptでスタックを実装
そもそもスタックやキューとは何なのか
スタックやキューとは、データの保存や取り出し方の方法を指します。
スタックやキューと呼ばれる箱の中にいくつかのデータを保存し、必要な時にその箱から取り出すといったイメージです。
図１ スタックやキューのイメージ
この2つはデータを保存する、取り出すという点では同じですが、データの保存の仕方や取り出し方に違いがあります。
スタックの保存(push)の仕方
スタックはデータを保存された場合、スタックはデータを上に積み重ねていくように保存します。この事をpushといいます。
以下の画像の右側にあるコップのような箱がスタックです。
図２ スタック 保存のイメージ
スタックの中に青色のデータを保存してみると、図３のようになります。
図３ 青色のデータを保存
次に緑色のデータを保存すると、図４のようになります。
図4 緑色のデータを保存
最後にピンク色のデータを保存すると、図５のようになります。
図5 ピンク色のデータを保存
スタックの中身を見ますと、保存されたデータが上に積み重なっていることが分かると思います。
スタックの取り出し方（pop）
データを取り出すとき、スタックは積み重なったデータを上から順番に取り出します。この事をpopといいます。
図6 スタック 取り出し方のイメージ
先ほどの図５の状態のスタックからデータを取り出すと、図7のようになります。
図7 1回目の取り出しのイメージ
図7の状態で取り出すと、図8に、図8の状態で取り出すと図9のようになります。
図8 2回目の取り出しのイメージ
図9 3回目の取り出しのイメージ
このようにスタックは積み重ねたデータを上から順番に取り出します。
スタックはLast In, First Out(LIFO)
上記の例から、スタックはデータを取り出すとき、一番新しく保存したピンク色のデータから取り出しました。そして、一番初めに保存した青色のデータは一番最後に取り出されました。
このようなデータの取り出し方をLast In, First Out(LIFO)といいます。
文字通り、一番新しく保存したデータ（Last In)を一番最初に取り出す（First Out)という意味です。
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であることが分かりますね。
まとめ
今回は以下の内容について解説しました。
- スタックやキューとはデータ構造のこと
- スタックの保存の仕方について
- スタックの取り出し方について
- スタックはLIFO
- JavaScriptでスタックを実装
次回は、キューについて解説します。