IT試験の、混同しやすい用語
スタックとキューの違い
同じ順に入れても、出てくる順が変わる。
自分で操作して、違いを発見する
同じ操作を、両方に試そう。
「入れる」「取り出す」を好きな順番で実行します。取り出す前に、どのデータが出るか予想してみましょう。左が底/先頭、右が上/末尾です。色付きのデータが次に出ます。
スタック
底 ← 入っているデータ → 上・出口
これまでに出た順番
キュー
出口・先頭 ← 入っているデータ → 末尾
これまでに出た順番
操作履歴を表で確認する
| 手 | 操作 | スタックから出た値 | キューから出た値 | スタックに残る値 | キューに残る値 |
|---|
演習では中のデータを8個、操作を32回までに制限しています。仕組みそのものの上限ではありません。入力・結果はこのページ内だけで扱い、再読み込みすると消えます。
途中で取り出すと、どうなる?
例2を、1手ずつ追ってみる。
A、Bを入れる → 1回取り出す → Cを入れる → もう1回取り出す。この順番なら、最後に残るデータも違います。
| 操作 | スタック | キュー |
|---|---|---|
| Aを入れる | 残り:A | 残り:A |
| Bを入れる | 残り:A・B | 残り:A・B |
| 取り出す | Bが出る 残り:A | Aが出る 残り:B |
| Cを入れる | 残り:A・C | 残り:B・C |
| 取り出す | Cが出る 残り:A | Bが出る 残り:C |
スタックは最後に入れたCを先に出します。キューはCより先に並んでいたBを出します。「逆順」「同じ順」とだけ覚えるより、操作のたびに残りを書き直すと迷いにくくなります。
応用:このあとDを入れ、2回取り出すと?
スタックはA・Dとなるので、D → A。キューはC・Dとなるので、C → Dです。どちらも最後は空になります。上の「例2」を選び、Dを入れて2回取り出すと確かめられます。
違いを表で整理
| 比べる点 | スタック | キュー |
|---|---|---|
| 取り出すルール | 後入れ先出し(LIFO) | 先入れ先出し(FIFO) |
| A → B → Cと入れた後の順番 | C → B → A | A → B → C |
| 入れる操作 | push(プッシュ) | enqueue(エンキュー) |
| 取り出す操作 | pop(ポップ) | dequeue(デキュー) |
| イメージ | 積み重ねた皿のいちばん上 | 順番待ちの列の先頭 |
順番を逆に覚えないコツ
「入れた順」だけでなく、「どこから出すか」を見ます。スタックは積み重ねた上から、キューは列の先頭から。同じA・B・Cでも、出口のルールが違います。
順番の表は、A・B・Cを全部入れてから取り出す例です。途中で取り出したり追加したりすると、残るデータも変わります。操作が混ざる問題では、1回ずつ残ったデータを書きましょう。
理解をたしかめる
違いがわかったら、1問。
A → B → Cを入れた後、追加せずに2回取り出します。スタックとキューの組合せは?
関連する内容を、Webで復習する。
取り出す順序と、処理が止まる条件を3問で確認できます。
アプリで学びたい方へ:iPhone・iPad向けアプリ(無料範囲・追加購入あり)
定義の確認:NIST:stack · NIST:queue。解説・例題は独自に作成しています。