こんにちは、フルスタックエンジニアのryuです。
今回の記事では、基本情報技術者試験の過去問を使いながら、キューの仕組みについて解説します。
キューは、データを一時的にためておくためのデータ構造の一つです。基本情報技術者試験では、スタックとセットで出てくることも多く、
「FIFOとLIFO、どっちがキューだっけ？」 「enqueueとdequeueが出てくると分からなくなる」 「擬似言語になると、どの値から取り出されるのか追えない」
というところでつまずきやすいと思います。
ただ、キューの基本はとてもシンプルです。
先に入れたデータから、先に取り出す。
まずはこれを理解できれば大丈夫です。
現在の基本情報技術者試験では、科目Bでデータ構造やアルゴリズムが扱われ、スタックやキューも出題範囲に含まれています。単に「FIFO＝キュー」と暗記するだけではなく、擬似言語になったときにデータの動きを追えるようにしておきましょう。
キューに関する記述として最も適切なものはどれか¶
今回はこちらの問題です。
キューに関する記述として、最も適切なものはどれか。
ア：最後に格納されたデータが最初に取り出される。 イ：最初に格納されたデータが最初に取り出される。 ウ：添字を用いて特定のデータを参照する。 エ：二つ以上のポインタを用いてデータの階層関係を表現する。 出典：平成27年春期 問5
答えは、イの「最初に格納されたデータが最初に取り出される」です。
これはキューの基本である、先入れ先出し（FIFO）を説明しています。
では、キューがどのようにデータを扱うのか、順番に見ていきましょう。
キューとは？¶
キューとは、先に入れたデータから順番に取り出すデータ構造です。
英語では、
First In First Out
といい、頭文字を取ってFIFOと呼ばれます。
例えば、レジに並んでいる行列をイメージすると分かりやすいです。
入口 → A → B → C → 出口
Aさんが最初に並び、そのあとにBさん、Cさんが並んだとします。
会計するときは、
A → B → C
の順番になります。
後から来たCさんが、いきなりAさんより先に会計することはありません。
この「先に入ったものから先に出る」という仕組みがキューです。
キューではenqueueとdequeueを使う¶
キューでは、データを入れる操作と取り出す操作に名前があります。
データを入れる操作を、
enqueue
データを取り出す操作を、
dequeue
と呼びます。
例えば、空のキューにA、B、Cの順番でデータを入れてみましょう。
最初は何も入っていません。
[ ]
Aをenqueueします。
[A]
次にBをenqueueします。
[A, B]
さらにCをenqueueします。
[A, B, C]
ここでdequeueすると、最初に入れたAが取り出されます。
取り出す → A
[B, C]
もう一度dequeueすると、次はBです。
取り出す → B
[C]
このように、enqueueした順番とdequeueされる順番が同じなのがキューです。
キューとスタックの違い¶
キューを勉強するときに、一緒に覚えておきたいのがスタックです。
キューとスタックは、どちらもデータを一時的に保存するデータ構造ですが、取り出す順番が違います。
キューは、
A → B → C
の順番で入れたら、
A → B → C
の順番で取り出します。
一方、スタックは、
A → B → C
の順番で入れたら、
C → B → A
の順番で取り出します。
違いを表にすると次のようになります。
| 項目 | キュー | スタック |
|---|---|---|
| 取り出す順番 | 先に入れたものから | 最後に入れたものから |
| 呼び方 | FIFO | LIFO |
| 入れる操作 | enqueue | push |
| 取り出す操作 | dequeue | pop |
| イメージ | レジの行列 | 積み重ねた本 |
スタックは、上に積み重ねた本をイメージすると分かりやすいです。
最後に置いた本が一番上にあるので、その本から先に取り出します。
一方、キューは行列です。
キュー＝行列、スタック＝積み重ねた本
とイメージしておくと、試験でも判断しやすくなります。
関連記事：文字を出力するために最小限必要となるスタックは何個か
各選択肢を詳しく確認しよう¶
ここで、最初の問題へ戻って各選択肢を確認してみましょう。
ア：最後に格納されたデータが最初に取り出される¶
これはキューではなく、スタックの説明です。
スタックでは、最後に入れたデータから取り出します。
A → B → C の順に入れる
↓
C → B → A の順に取り出す
この方式を後入れ先出し、LIFOと呼びます。
イ：最初に格納されたデータが最初に取り出される¶
これが正解です。
キューでは、
A → B → C
の順番で入れたら、
A → B → C
の順番で取り出されます。
これを先入れ先出し、FIFOと呼びます。
ウ：添字を用いて特定のデータを参照する¶
これは配列の特徴です。
例えば、
data[3]
のように添字を使って特定の要素を参照します。
配列も科目Bでは非常によく使うため、キューやスタックと一緒に理解しておきたいデータ構造です。
エ：二つ以上のポインタを用いてデータの階層関係を表現する¶
これはキューの説明ではありません。
階層関係を表すデータ構造としては、木構造などがあります。
科目Bでは、キューやスタックだけではなく、リスト、木構造、グラフなどのデータ構造も学習しておく必要があります。
科目Bではキューが擬似言語で出てくる¶
この過去問だけを見ると、
キュー＝FIFO
と覚えれば解けます。
ただ、現在の基本情報技術者試験の科目Bでは、それだけでは十分ではありません。
キューが擬似言語の中に登場し、
「この処理を実行したあと、次に取り出される値は何か」 「headとtailの値はどう変化するか」 「何回dequeueされたか」
といった形で処理を追うことがあります。
そのため、キューは言葉だけでなく、実際の動きまで理解しておくことが大切です。
キューを擬似言語で見てみよう¶
キューの動きを簡単な擬似言語で表すと、例えば次のようになります。
整数型の配列: queue
整数型: head ← 1
整数型: tail ← 0
enqueue(value)
tail ← tail + 1
queue[tail] ← value
dequeue()
value ← queue[head]
head ← head + 1
return value
最初は少し難しく見えるかもしれません。
ただ、キューで見るべき変数は主に、
head
tail
の二つです。
headは、次に取り出す位置を表します。
tailは、最後に追加した位置を表します。
この二つを分けて考えると読みやすくなります。
実際にキューをトレースしてみよう¶
先ほどの擬似言語を使って、次の処理を考えてみます。
enqueue(10)
enqueue(20)
enqueue(30)
dequeue()
dequeue()
まず初期状態は、
head = 1
tail = 0
です。
enqueue(10)¶
最初に、
tail ← tail + 1
を実行します。
tail = 1
そのあと、
queue[1] ← 10
となります。
キューの中身は、
[10]
です。
enqueue(20)¶
次は、
tail = 2
となり、
queue[2] = 20
です。
[10, 20]
enqueue(30)¶
同じように、
tail = 3
となります。
[10, 20, 30]
1回目のdequeue¶
次にdequeueします。
現在、
head = 1
なので、
queue[1]
の10が取り出されます。
そのあと、
head ← head + 1
となるため、
head = 2
になります。
2回目のdequeue¶
次に取り出すのは、
queue[2]
の20です。
この流れを表にすると次のようになります。
| 操作 | head | tail | 取り出した値 |
|---|---|---|---|
| 初期状態 | 1 | 0 | - |
| enqueue(10) | 1 | 1 | - |
| enqueue(20) | 1 | 2 | - |
| enqueue(30) | 1 | 3 | - |
| dequeue() | 2 | 3 | 10 |
| dequeue() | 3 | 3 | 20 |
科目Bでは、このように表へ書きながら追うとかなり分かりやすくなります。
頭の中だけで、
「headはいくつだっけ？」 「tailはどこまで進んだ？」
と考えていると途中で分からなくなるため、最初のうちは値を書き出すのがおすすめです。
キューの擬似言語で見るべきポイント¶
キューが問題に出てきたら、いきなりコードを1行目からすべて理解しようとしなくても大丈夫です。
まずは次の3つを探してください。
1. データを入れている場所¶
例えば、
queue[tail] ← value
のような処理です。
「どこに新しい値を入れているのか」を確認します。
2. データを取り出している場所¶
例えば、
value ← queue[head]
です。
これを見れば、「headが指している位置から取り出している」と分かります。
3. headとtailがどう変化するか¶
例えば、
tail ← tail + 1
head ← head + 1
のような部分です。
どちらが「入れる位置」で、どちらが「取り出す位置」なのかを整理すると、コード全体が読みやすくなります。
キューは実際にどこで使われるの？¶
キューは試験のためだけにあるデータ構造ではありません。
実際のシステムでも、処理を順番に待たせたい場面でよく使われます。
例えば、
- 印刷待ちのデータ
- メッセージ処理
- ジョブの実行待ち
- Webサービスのバックグラウンド処理
- 通信データの処理待ち
などです。
例えばプリンターへ、
資料A
資料B
資料C
の順番で印刷を依頼した場合、基本的には資料Aから順番に処理してほしいですよね。
このような「先に来た処理から順番にさばく」という考え方と、キューは相性がよいです。
基本情報技術者試験の用語を実際のシステムと結びつけて考えると、単なる暗記ではなくなり、覚えやすくなります。
リングバッファを使ったキューもある¶
キューについて少し進んで勉強すると、リングバッファや循環キューという考え方も出てきます。
単純な配列でキューを作り、
head
tail
をひたすら右に進めていくと、配列の後ろまで到達したあとに空いている前半部分を使えなくなってしまいます。
そこで、配列の最後まで到達したら先頭へ戻り、円のように使う方法があります。
イメージとしては、
1 → 2 → 3 → 4 → 5
↑ ↓
└───────────────┘
のような形です。
科目Bの問題では、こうした仕組みが擬似言語として出てくる場合もあります。
ただ、最初からリングバッファまで覚える必要はありません。
まずは、
キューは先入れ先出し
という基本と、head・tailの役割を理解するところから始めましょう。
FIFOとLIFOを丸暗記しない¶
キューとスタックを勉強すると、
FIFO
LIFO
という言葉だけを暗記してしまいがちです。
もちろん試験では用語も必要ですが、それだけだと擬似言語問題で止まってしまいます。
例えば、
A
B
C
を順番に入れたとき、
キューなら、
A → B → C
スタックなら、
C → B → A
と取り出される。
ここまで自分で説明できるようにしておきましょう。
科目Bでは「言葉を知っている」ことよりも、処理を追えることが重要です。
Giji Academyでキューやスタックを実際に学ぶ¶
キューやスタックは、文章を読んでいるだけならそれほど難しくありません。
問題になるのは、擬似言語になったときです。
headやtailなどの変数が増え、enqueueやdequeueを何回も実行すると、
「今どこまで入っているのか」 「次にどの値が取り出されるのか」
が分からなくなることがあります。
Giji Academyでは、基本情報技術者試験の科目Bで必要になるデータ構造について、擬似言語を使いながら段階的に学習できます。
データ構造のカテゴリには、
- スタック
- キュー
- リスト
- 木構造
- グラフ
などの講座があります。
いきなりキューの擬似言語を読むのが難しい場合は、変数、条件分岐、繰返し、配列、トレースなどの基礎から進めることもできます。
「FIFOは覚えているけど、科目Bのコードになると追えない」という方は、実際に処理を動かしながら確認してみてください。
登録不要で無料体験できます。
過去問解説まとめ¶
今回の記事では、次の問題について解説しました。
キューに関する記述として、最も適切なものはどれか。
ア：最後に格納されたデータが最初に取り出される。
イ：最初に格納されたデータが最初に取り出される。
ウ：添字を用いて特定のデータを参照する。
エ：二つ以上のポインタを用いてデータの階層関係を表現する。
答えは、イです。
キューで覚えておきたいポイントは次のとおりです。
- キューは先入れ先出し
- FIFO（First In First Out）とも呼ばれる
- データを入れる操作はenqueue
- データを取り出す操作はdequeue
- スタックは後入れ先出しなので動きが逆
- 擬似言語ではheadとtailの変化を追う
基本情報技術者試験では、キューという言葉だけを覚えるのではなく、実際にデータがどの順番で入って、どの順番で取り出されるのかを理解しておくことが大切です。
特に科目Bでは、キューやスタックが擬似言語の処理の一部として登場することがあります。
問題を見て分からなくなったときは、頭の中だけで考えず、キューの中身やhead、tailの値を表にして追ってみてください。
Giji Academyでは、キューやスタックを含むデータ構造だけではなく、擬似言語の基礎、配列、繰返し、トレース、探索・整列アルゴリズムなどを順番に学べます。
科目Bの擬似言語に苦手意識がある方は、まず無料で実際にコードを動かしてみてください。
Giji Academy｜擬似言語を実行しながら科目Bを学ぶ
基本情報技術者試験の過去問解説はこちらから確認できます。
あわせて読みたい
