比べてわかるキューとスタックの仕組み｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
2023-11-14 更新
基本情報技術者試験は、2023年4月から新制度で実施されています。
この連載では、新制度の擬似言語（旧制度の擬似言語とは、表記方法に違いがあります）を使って、試験のシラバス（情報処理技術者試験における知識・技能の細目）に示されている代表的なアルゴリズムとデータ構造を、プログラミング入門者向けにやさしく解説します。受験対策としてだけでなく、アルゴリズムとプログラミングの基礎知識を習得するために、ぜひお読みください。
今回は、「 キュー 」と「 スタック 」のデータ構造を取り上げます。
キューとスタックの特徴
プログラムでは、すぐに処理しないデータを一時的に格納しておく配列が必要になる場合があります。このような配列をバッファ（buffer＝緩衝器）と呼びます。
今回のテーマであるキューとスタックは、どちらもバッファですが、配列へのデータの格納と取り出しの順序に違いがあります。キューとスタックを比べてみましょう。
キュー は、ごく普通のバッファであり、最初に格納したデータを最初に取り出します。これをFIFO（First In First Out＝先入れ先出し）形式と呼びます。
たとえば、”A”、”B”（ここでは、文字列データを格納するとします）の順にキューに格納したら、”A”、”B”の順に取り出します。
キュー（queue）は、「待ち行列」という意味です。日常生活において、何かの切符を買う窓口では、最初に列に並んだ人（First In）が、最初に列から出て（First Out）切符を買います。プログラムのキューも、これと同様です。
キューにデータを格納することをエンキュー（enqueue）、キューからデータを取り出すことをデキュー（dequeue）と呼びます（図1）。
スタック は、ちょっと変わったバッファであり、最後に格納したデータを最初に取り出します。これをLIFO（Last In First Out＝後入れ先出し）形式と呼びます。
たとえば、”A”、”B”の順にスタックに格納したら、”B”、”A”の順に取り出します。
スタック（stack）は、「干し草を積んだ山」という意味です。日常生活において、牧場で家畜に食べさせる草を積んだ山では、最後に積んだ草（Last In）を、最初に取り出します（First Out）。プログラムのスタックも、これと同様です。
スタックにデータを格納することをプッシュ（push）、スタックからデータを取り出すことをポップ（pop）と呼びます（図2）。
キューとスタックの大きな違いは、順序が入れ替わるかどうかです。
キュー では、”A”、”B”の順に格納すれば、”A”、”B”の順に取り出されるので、順序が入れ替わりません。
スタック では、”A”、”B”の順に格納すれば、”B”、”A”の順に取り出されるので、順序が入れ替わります。
キューとスタックをオブジェクトで実現する
プログラムでキューとスタックを実現するには、データを格納する配列と、その配列にデータの格納および取り出しを行う処理を用意することになります。
現時点で公開されている基本情報技術者試験の問題を見ると、これらの仕組みをオブジェクトとして実現しています。オブジェクトとは、内部にいくつかのデータと処理を持つモジュール（プログラムの構成要素）です。
基本情報技術者試験の擬似言語では、オブジェクトが持つデータをメンバ変数と呼び、オブジェクトが持つ処理をメソッドと呼びます。
キューやスタックを実現するオブジェクトは、メンバ変数として配列を持ち、その配列にデータを格納するメソッド、およびデータを読み出すメソッドを持つことになります。他にも、必要なメソッドがあれば用意します。
プログラムでは、オブジェクトをクラスとして定義します。
プログラムの実行時に、クラス一式（データと処理の一式）をメモリにロードしたものが、オブジェクト（クラスのインスタンスとも呼びます）です。
オブジェクトが持つメンバ変数やメソッドは、「オブジェクト名.メンバ変数名」や「オブジェクト名.メソッド名」という構文で使います。多くの場合に、オブジェクトを使う側は、オブジェクトが持つデータを直接操作せずに、オブジェクトが持つメソッドを使って間接的に操作します。
キューを実現するQueueクラスを作成したとしましょう。
このQueueクラスには、キューの実体となる配列、コンストラクタQueue、キューにデータを格納するenqueueメソッド、キューから取り出したデータを返すdequeueメソッド、およびキューに格納されているデータ数を返すsizeメソッドがあるとします。
これらは、後で示す試験問題のプログラムに似せたものです。
コンストラクタとは、クラス一式をメモリにロードする（オブジェクトを生成する）機能を持った特殊なメソッドです。多くのプログラミング言語で、コンストラクタの名前はクラスと同じにします。Queueクラスのコンストラクタの名前は、Queueです。
リスト1は、Queueクラスを使ったプログラムの例です。
ここでは、queueという名前のキューを生成し、キューに”A”と”B”というデータを格納して、キューからすべてのデータを取り出して表示しています。
キューは、FIFO形式なので、”A”、”B”の順に表示されます。
ここでは、「クラス名：オブジェクト名 ← コンストラクタ()」という構文で、オブジェクトを生成しています。これは、後で示す試験問題のプログラムに合わせたものです。
多くのプログラミング言語では、オブジェクトの生成にnewという命令を使いますが、擬似言語では使いません。
リスト1 Queueクラスを使ったプログラムの例code
// キューを生成する
Queue:queue ← Queue()
// キューにデータを格納する
queue.enqueue("A")
queue.enqueue("B")
// キューからすべてのデータを取り出す
while (queue.size() ＞ 0)
queue.dequeue()の戻り値を表示する
endwhile
スタックを実現するStackクラスを作成したとしましょう。
このStackクラスには、スタックの実体となる配列、コンストラクタStack、スタックにデータを格納するpushメソッド、スタックから取り出したデータを返すpopメソッド、およびスタックに格納されているデータ数を返すsizeメソッドがあるとします。
リスト2は、Stackクラスを使ったプログラムの例です。
ここでは、stackという名前のスタックを生成し、スタックに”A”と”B”というデータを格納して、スタックからすべてのデータを取り出して表示しています。スタックは、LIFO形式なので、”B”、”A”の順に表示されます。
リスト2 Stackクラスを使ったプログラムの例code
// スタックを生成する
Stack:stack ← Stack()
// スタックにデータを格納する
stack.push("A")
stack.push("B")
// スタックからすべてのデータを取り出す
while (stack.size() ＞ 0)
stack.pop()の戻り値を表示する
endwhile
基本情報技術者試験の問題にチャレンジ
試験対策として、2022年12月に公開された科目Bサンプル問題セットの問8にチャレンジしてみましょう。
これは、オブジェクトで実現したキューをテーマにした問題です。
このキューは、FIFO形式ですが、優先度付きであることに注意してください。
以下に問題を示します。
次の記述中のに入れる正しい答えを、解答群の中から選べ。
優先度付きキューを操作するプログラムである。優先度付きキューとは扱う要素に優先度を付けたキューであり，要素を取り出す際には優先度の高いものから順番に取り出される。クラス PrioQueue は優先度付きキューを表すクラスである。クラス PrioQueue の説明を図に示す。ここで，優先度は整数型の値1，2，3のいずれかであり，小さい値ほど優先度が高いものとする。
手続 prioSched を呼び出したとき，出力はの順となる。
プログラムcode
○prioSched()
PrioQueue: prioQueue ← PrioQueue()
prioQueue.enqueue("A", 1)
prioQueue.enqueue("B", 2)
prioQueue.enqueue("C", 2)
prioQueue.enqueue("D", 3)
prioQueue.dequeue() /* 戻り値は使用しない */
prioQueue.dequeue() /* 戻り値は使用しない */
prioQueue.enqueue("D", 3)
prioQueue.enqueue("B", 2)
prioQueue.dequeue() /* 戻り値は使用しない */
prioQueue.dequeue() /* 戻り値は使用しない */
prioQueue.enqueue("C", 2)
prioQueue.enqueue("A", 1)
while (prioQueue.size() が 0 と等しくない)
prioQueue.dequeue() の戻り値を出力
endwhile
解答群
ア “A”，“B”，“C”，“D”
イ “A”，“B”，“D”，“D”
ウ “A”，“C”，“C”，“D”
エ “A”，“C”，“D”，“D”
dequeueメソッドで、キューから要素を取り出すときは、キュー内で最も優先度の高い要素が取り出されます。最も優先度の高い要素が複数ある場合は、それらのうち最初に格納された要素が取り出されます。
手続prioSchedで行われているキューへの格納と取り出しによって、キューの内容は以下のように変化します。ここでは、キューの1つの要素を[文字列データ, 優先度]で示しています。優先度は、値が小さいほど高いとされます。
prioQueue.enqueue("A", 1) [A, 1]
prioQueue.enqueue("B", 2) [A, 1][B, 2]
prioQueue.enqueue("C", 2) [A, 1][B, 2][C, 2]
prioQueue.enqueue("D", 3) [A, 1][B, 2][C, 2][D, 3]
prioQueue.dequeue() [B, 2][C, 2][D, 3]
prioQueue.dequeue() [C, 2][D, 3]
prioQueue.enqueue("D", 3) [C, 2][D, 3][D, 3]
prioQueue.enqueue("B", 2) [C, 2][D, 3][D, 3][B, 2]
prioQueue.dequeue() [D, 3][D, 3][B, 2]
prioQueue.dequeue() [D, 3][D, 3]
prioQueue.enqueue("C", 2) [D, 3][D, 3][C, 2]
prioQueue.enqueue("A", 1) [D, 3][D, 3][C, 2][A, 1]
キューの内容が[D, 3][D, 3][C, 2][A, 1]となった後で、while文を使ってキューの要素数が0になるまで、キューからデータの取り出しと出力（何に出力するかは示されていませんが、画面に出力すれば表示されます）を繰り返しています。[D, 3][D, 3][C, 2][A, 1]からは、[A, 1]、[C, 2]、前側の[D, 3]、後側の[D, 3]の順に取り出されるので、出力はA、C、D、Dの順になります。
したがって、選択肢エが正解です。
今回は、キューとスタックを取り上げました。
次回も、シラバスに示されたアルゴリズムとデータ構造を解説します。
それでは、またお会いしましょう！
label 関連タグ免除試験を受けた 74.9% の方が、科目A免除資格を得ています。
マージソート｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
二分木の深さ優先探索と幅優先探索｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
比べてわかるキューとスタックの仕組み｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
「リスト」というデータ構造｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
サーチのアルゴリズム (3) ハッシュ表探索法のアルゴリズム｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
クイックソートのアルゴリズム｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
再帰呼び出しのアルゴリズム｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
サーチのアルゴリズム (2) 二分探索法｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
サーチのアルゴリズム (1) 線形探索法｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
多重ループを使うバブルソート｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update『プログラムはなぜ動くのか』（日経BP）が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”
大手電気メーカーでＰＣの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識０ベースのＩＴエンジニアや一般書店フェアなどの一般的なＰＣユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。
主な著作物
- 「プログラムはなぜ動くのか」（日経BP）
- 「コンピュータはなぜ動くのか」（日経BP）
- 「出るとこだけ! 基本情報技術者」 (翔泳社)
- 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」（翔泳社）
- 「ｉｆとｅｌｓｅの思考術」（ソフトバンククリエイティブ） など多数
