今回は【基礎理論(アルゴリズム)編】スタックとキューについて紹介します。
スタックとキューはどちらもデータ構造の一つですが、両者は異なる特徴を持っています。
実は身の回りにもスタックやキューに似たような概念が存在しているので、イメージを結び付けながら覚えていきましょう！
スタックについて
スタック(stack)とは、LIFO(Last In First Out)形式で格納されたデータ構造のことを指します。
“最後に入ったもの(Last In)”が“最初に出てくる(First Out)”データ構造になっているんですね！
(ちなみにLIFOはリフォやライフォと読まれたりします。)
そもそも“Stack”という英単語には“積み重ね”といった意味合いがあるので、普段私たちが物を積み重ねて置く行為はスタックのデータ構造とよく似ています。
例えば、お皿や本が積み重なって置かれている場合、普通は最後に置いたもの(一番上のもの)を最初に手に取りますよね！
まさにこれがLIFOと同じ構造になっているのです。
このLIFOの特徴を利用して、ITの世界ではデータ退避などにスタックが利用されています。
ある処理の最中に別の処理を行いたい場合には、メモリ内部のデータを一時的にスタックに格納し、空いた分のメモリで別処理を行います。
その後、別処理が全て終わった段階でスタックからデータを取り出せば、容易に元の処理を復旧させる事ができるんですね。
それでは、一度イラストでスタックのイメージを確認してみましょう。
上のイラストを確認すると、入れた順番と出てくる順番が逆になっている事が分かると思います。
これがスタックのLIFO形式の特徴です。
また、このスタックというデータ構造にデータを出し入れする操作には、それぞれ名称がついています。
スタックにデータを格納することをPush,スタックからデータを取り出すことをPopと呼ぶことを覚えておきましょう。
キューについて
キュー(Queue)とは、FIFO(First In First Out)形式で格納されたデータ構造のことを指します。
スタックがLIFOの特徴を持っていたのに対し、キューは“最初に入ったもの(First In)”が“最後に出てくる(First Out)”ような構造となっています。
(FIFOはフィフォやファイフォと読まれたりします。)
“Queue”という単語には“人の行列”といった意味合いがあるので、レジ待ちの人の列などはキューのデータ構造によく似ています。
先に列に並んでいた人から先にレジに案内されるので、FIFO形式と同じですよね！
このFIFO形式のデータ構造を持つキューは、プリンターの印刷ジョブの処理などに利用されています。
それではここまでの話を一度イラストで整理しておきましょう！(ぜひ先ほどのスタックとも見比べてみてください)
キューの場合は入れた順番と出てくる順番が同じでしたね！
これがキューのFIFO形式の特徴です。
さて、スタックへのデータの出し入れにPushやPopという名前がついていたのと同じように、
キューへのデータの出し入れにも次のような名前がついています。
キューにデータを格納する操作はEnqueue,キューからデータを取り出す操作はDequeueと呼ばれています。必ず覚えておきましょう！
以上でスタックとキューの紹介は終わりになります。
どちらがFIFOでどちらがLIFOか、混同しないようにしっかりと覚えておきましょう。
まとめ
- スタックはLIFO(最後に入れたものが最初に出てくる)形式のデータ構造
- スタックにデータを格納→Push、 データの取り出し→Pop
- キューはFIFO(最初に入れたものが最初に出てくる)形式のデータ構造
- キューにデータを格納→Enqueue、データの取り出し→Dequeue
演習問題
1.スタックに関する記述として最も正しいものはどれか？
A.入れた順番でデータを取り出すことができる
B.プリンターの印刷ジョブに利用されている
C.LIFO形式のデータ構造
2.キューに関する記述として最も正しいものはどれか？
A.データを取り出す操作をDequeueと呼ぶ
B.データを格納する操作をPushと呼ぶ
C.最初に入れたデータが最後に取り出される
3.スタックとキューが1つずつ用意されている。
次の操作を行った後に、変数xとyに格納されている値はどれか？
なお、Push(n)とEnqueue(n)は数値nをPush、Enqueueする操作を表し、
Pop()とDequeue()はPopやDequeueの操作を行って得られる数値を表している。
[操作]
Push(1)→Push(6)→Enqueue(4)→Enqueue(9)→Dequeue()→Enqueue(Pop())→Push(Dequeue())→Enqueue(4)→x=Dequeue(), y=Pop()
A.1
B.4
C.6
D.9
答えは次回の記事で確認してください。
