【基本情報】キュー・スタックの違いって何？
それぞれの使い方と演習問題

今回は、キューとスタックについてそれぞれの使い方と、それに対する演習問題までご紹介していこうと思います。

インプットもアウトプットも同時に試せてしまうため、本記事を通して『キュー・スタック』に関する知識を確かなものにしてしまいましょう。

また、本記事で扱っている演習問題は、大半が基本情報技術者試験の過去問になるため、試験対策にもなります。
ぜひ最後まで見ていってください。

　用語解説

では、まず初めにキューやスタックについてその意味や違いを解説していこうと思います。

キューとは？

キューとは、先に格納したデータから順番に取り出す、先入先出型のデータ構造のことです。

下の図では、データが追加された順に左から並んでおり、取り出しの際には、一番左のデータが取り出されています。

このように、一番古いデータから取り出すようなデータ構造をキューというので、よく覚えておきましょう。

enqueue(エンキュー)・dequeue(デキュー)とは？

キューにデータを追加することをenqueue(エンキュー)、キューからデータを取り出すことをdequeue(デキュー)と言います。

enqueueやdequeueのルールに関する問題はよく出題されるので、言葉まで覚えておきましょう。

スタックとは？

スタックとは、後に格納したデータから順番に取り出す、後入先出型のデータ構造のことです。

下の図のように、箱にデータを詰めていく様子をイメージすると、わかりやすいと思います。

箱にデータを詰めていくと、一番最後に入れたデータから取り出すことになりますよね。

push(プッシュ)・pop(ポップ)とは？

スタックにデータを追加することをpush(プッシュ)、スタックからデータを取り出すことをpop(ポップ)と言います。

こちらも、試験でよく問われるため覚えておきましょう。

　演習問題

続いては演習問題です。
インプットした知識を演習を通じてアウトプットして、知識の定着を図りましょう。

演習問題①

キューに関する記述として，最も適切なものはどれか。
[基本情報技術者平成27年春期 午前問5]

演習問題②

PUSH命令でスタックにデータを入れ，POP命令でスタックからデータを取り出す。動作中のプログラムにおいて，ある状態から次の順で10個の命令を実行したとき，スタックの中のデータは図のようになった。1番目のPUSH命令でスタックに入れたデータはどれか。

[基本情報技術者平成17年春期 午前問13]

演習問題③

A，C，K，S，Tの順に文字が入力される。スタックを利用して，S，T，A，C，Kという順に文字を出力するために，最小限必要となるスタックは何個か。ここで，どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また，スタック間の文字の移動は行わない。
[基本情報技術者令和元年秋期 午前問8]

演習問題④

四つのデータA，B，C，Dがこの順に入っているキューと空のスタックがある。手続pop_enq，deq_pushを使ってキューの中のデータをD，C，B，Aの順に並べ替えるとき，deq_pushの実行回数は最小で何回か。ここで，pop_enqはスタックから取り出したデータをキューに入れる操作であり，deq_pushはキューから取り出したデータをスタックに入れる操作である。
[基本情報技術者平成24年秋期 午前問5]

演習問題⑤

空の状態のキューとスタックの二つのデータ構造がある。次の手続を順に実行した場合，変数xに代入されるデータはどれか。ここで，手続きに引用している関数は，次のとおりとする。

〔関数の定義〕

• push(y)：データyをスタックに積む。
• pop()：データをスタックから取り出して，その値を返す。
• enq(y)：データyをキューに挿入する。
• deq()：データをキューから取り出して，その値を返す。

〔手続〕

• push(a)
• push(b)
• enq(pop())
• enq(c)
• push(d)
• push(deq())
• x ← pop()

[基本情報技術者平成26年春期 午前問7]

　まとめ

今回は、キューとスタックについての説明や、それらに関する演習問題を紹介してきたのですが、いかがだったでしょうか。

• キューは先入先出型
• スタックは後入先出型

です。

キューとスタックは、データを扱うデータ構造としてよく試験で問われますが、違いを明確に理解しておきましょう。