スタックとキュー
スタックとキューは、データの入れ物（データ構造）のことです。
データの入れ物（データ構造）には、複数データを格納しておくことと、必要な時に必要な内容を効率よく引き出すことが求められます。。
どちらも筒状の入れ物（スタック・キュー）に球（データ）を順番に入れていくようなイメージです。
スタックとは
スタックとは、データを出し入れするための「片側に蓋をされた（底のある）」筒のことです。
データを格納するときも取り出すときも、1つの入り口（蓋がない方）からしか出し入れ出来ないことが特徴です。
データをA,B,C,Dの順番にスタックに格納したとしましょう。
この場合、データは底（蓋）側からA,B,C,Dの順に入っています。
取り出すときはどのような順番になるでしょうか？
当然、蓋がある方から取り出すことは出来ないので、
D⇒C⇒B⇒Aの順番に取り出すことになります。
このような出し入れの順番をLIFO（Last in First Out）、または、後入れ先出しといいます。
最後に格納したデータが一番最初に取り出されるためです。
特に、スタックにデータを格納することをPUSH、スタックからデータを取り出すことをPOPといいます。
キューとは
キューとは、データを出し入れするための「両側に蓋がない（底のない）」筒のことです。
データを格納する入り口とデータを取り出す出口が別であることが特徴です。
データをキューにA,B,C,Dの順番に格納したとしましょう。
データは出口に近い方からA,B,C,Dの順に入っています。
（↑入り口側からカウントすると、D,C,B,Aの順）
取り出すときはどのような順番になるでしょうか？
出口に近い方から取り出すので、A⇒B⇒C⇒Dの順に取り出すことになります。
このような出し入れの順番をFIFO（First in First Out）、または、先入れ先出しといいます。
最初に格納したデータが一番最初に取り出されるためです。
特に、キューにデータを格納することをエンキュー、キューからデータを取り出すことをデキューといいます。
スタックとキューの出し入れ順を考えよう
データを実際に格納したり、取り出したりして利用する際、必ずしも全てのデータを一度格納してから、取り出すとは限りません。
データの出し入れは必要に応じて、格納・取り出しが入り組みながら行われています。
具体例をもとに、スタックとキューでどのような違いが表れるのかイメージしていきましょう。
A,B,C,Dというデータを以下のような順で操作したときを想定します。
①A,Bを格納
②1つ取り出し
③Cを格納
④2つ取り出し
⑤D,Eを格納
⑥残りすべてを格納
＜スタックの場合＞
①A,Bを格納
②Bを取り出し
③Cを格納
④C⇒Aの順に取り出し
⑤D,Eを格納
⑥E⇒Dの順に取り出し
全体の取り出し順をまとめると、B⇒C⇒A⇒E⇒Dの順に取り出すことになります。
＜キューの場合＞
①A,Bを格納
②Aを取り出し
③Cを格納
④B⇒Cの順に取り出し
⑤D,Eを格納
⑥D⇒Eの順に取り出し
全体の取り出し順をまとめると、Ａ⇒Ｂ⇒Ｃ⇒Ｄ⇒Ｅの順に取り出すことになります。
スタックとキューで取り出す順番に大きく違いがあることが分かります。
特にスタックは格納・取り出しが入り組むと順番が変わるので注意しましょう。
