科目Bのスタック・キュー問題の解き方｜出し入れの順番を表で追う

スタックとキュー、本番でどっちがどっちか分からなくなる。

後入れ先出しという言葉は覚えたのに、コードを前にすると迷っていませんか？

科目Bのスタック・キュー問題は、用語を覚えただけでは解けません。問われているのは、値が出ていく順番を最後まで追えるかどうかだからです。

逆に言えば、追い方さえ決まっていれば確実に取れる分野です。ここは得点源にしやすい場所だと考えてください。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務でも、処理を順番待ちさせる仕組みや、直前の状態に戻す機能でこの2つを使います。

現場で混同すると、処理の順序が逆になって不具合になります。だから私も、頭の中だけで判断せず、必ず紙に書いて確かめます。

この記事では、科目Bの設問に沿って、出し入れの順番を表で追う手順をお伝えします。科目B全体の姿を先に確かめたい人は、親記事から読むと位置づけがつかめます。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

この設問は何を聞いているのか¶

最初に、出題の意図を押さえておきましょう。ここがずれていると、覚える方向を間違えます。

スタックやキューが出てくる問題で問われるのは、データ構造の定義ではありません。与えられたコードを動かしたときに、何がどの順番で出てくるかです。

つまり、暗記ではなく作業です。手を動かせば必ず答えが出る種類の問題だと考えてください。

覚えるのは1行で足りる¶

定義そのものは短く済みます。表にすると、この程度の分量です。

覚えるのはこの4行だけです。あとは、問題文のコードがどちらを使っているかを見るだけになります。

文法としての書き方や操作の名前に不安が残る人は、先にこちらで固めておくと読みやすくなります。

【関連記事】擬似言語のスタックとキューとは？基本情報の科目Bで出る操作を解説

迷ったら身近な例に戻す¶

本番で分からなくなったら、机の上に積んだ本を思い出してください。上に置いた本から取るしかない、それがスタックです。

キューはレジの行列です。先に並んだ人から順に進みます。

この2つの絵を頭に置いておけば、用語を思い出せなくても判断できます。私も新人に説明するときは、必ずこの例から入ります。

まず目を付ける3か所¶

問題用紙を開いたら、1行目から読み始めないでください。先に見る場所を決めておくと、読む時間が半分になります。

見るのは次の3か所です。順番も大事なので、この並びで確認してください。

この3つが分かれば、途中の細かい処理は後回しにできます。全部を理解しようとしないのが、時間を守るコツです。

操作の名前で種類を見分ける¶

宣言部分に型が書かれていれば一番早いのですが、書かれていないこともあります。そのときは操作の名前で判断します。

push と pop が出てきたらスタックです。enqueue と dequeue が出てきたらキューだと考えて構いません。

問題文に操作の説明が添えられていることも多いので、そこも必ず読んでください。定義が書いてあるなら、覚えていなくても解けます。

入れる順番と出す順番を分けて見る¶

コードはたいてい、入れる処理と出す処理の2段構えになっています。ここを混ぜて読むと迷子になります。

まず入れるループだけを追って、中身がどう積まれたかを確かめる。それから出すループに進みます。

段を分けて読むだけで、間違いはぐっと減ります。読む順番を決めておくことの効果は、ほかの設問でも同じです。

【関連記事】基本情報 科目Bの問題はどう解く？問題文から答えを出すまでの手順

表で中身を追ってみる¶

ここからは実際に手を動かします。試験の書き方に合わせた自作のコードを用意しました。

配列の文字を順にスタックへ入れて、あとから取り出してつなげる処理です。

○文字列型: 並べ替え(文字列型の配列: moji)
  整数型: i
  スタック: st
  文字列型: kekka ← ""
  for (i を 1 から moji の要素数 まで 1 ずつ増やす)
    push(st, moji[i])
  endfor
  for (i を 1 から moji の要素数 まで 1 ずつ増やす)
    kekka ← kekka + pop(st)
  endfor
  return kekka

moji が {"A", "B", "C"} のときを追ってみましょう。まずは入れるループだけです。

表の右の列に注目してください。あとから入れた値が左、つまり上に積まれています。

次は出すループです。スタックなので、上から順に取り出されます。

答えは CBA です。入れた順と逆になりました。

もしこれがキューだったら、答えは ABC になります。同じコードの形でも、使うデータ構造が違えば結果が逆になるわけです。

キューの場合も同じ手順で追える¶

念のため、キューの側も確かめておきましょう。先ほどのコードの操作だけを置き換えた形です。

  for (i を 1 から moji の要素数 まで 1 ずつ増やす)
    enqueue(qu, moji[i])
  endfor
  for (i を 1 から moji の要素数 まで 1 ずつ増やす)
    kekka ← kekka + dequeue(qu)
  endfor

同じ {"A", "B", "C"} を入れて、出す様子を表にします。

答えは ABC で、入れた順のままです。表の作り方はスタックのときとまったく同じでした。

つまり、覚え直すことは何もありません。出口が先頭か末尾か、その1点だけが違います。

スタックは縦、キューは横に書く¶

表の書き方にも、ちょっとしたコツがあります。私が勧めているのは、スタックを縦に、キューを横に書く方法です。

スタックは積み重ねなので、上下の向きで書くと直感に合います。キューは行列なので、左から右へ並べると先頭が分かりやすくなります。

書き方を毎回そろえておくと、本番で迷う時間がなくなります。表の作り方そのものに不安がある人は、基本の型をこちらで確認しておいてください。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

途中で入れ直す問題に注意する¶

科目Bでよく出るのが、取り出した値をもう一度入れ直す形です。ここで表を省略すると、まず間違えます。

入れ直しがある問題は、行を増やして1操作ずつ書いてください。頭の中で追える量を超えているから、そういう出題になっているのです。

面倒に見えますが、書くほうが結局速く終わります。消しゴムを使わずに済むからです。

時間がないときは途中まで書く¶

本番で時間が足りないとき、表を全部書く余裕はないかもしれません。そのときは最初の2操作だけ書いてください。

2行書けば、順番がどちら向きかは分かります。あとは選択肢を見て、向きの合うものに絞れます。

何も書かずに勘で選ぶのと、2行書いて絞るのとでは、正答率がまるで違います。書く量は減らしてよいので、書くこと自体はやめないでください。

間違いやすい選択肢の見分け方¶

正しく追えていても、選択肢の読み違いで落とすことがあります。よくある引っかけを知っておきましょう。

出題者が仕掛けてくる場所は、だいたい決まっています。

一番上の行が最多です。自分の答えの逆順が選択肢に並んでいたら、いったん手を止めてください。

空のときの扱いを先に確認する¶

取り出す側のループが、入れた回数より多く回る問題があります。このとき、空のスタックから取り出そうとする場面が生まれます。

問題文には、空のときにどうなるかが書かれているはずです。そこを読み飛ばすと、選択肢のどれにも当てはまらなくなります。

実務でも、この状態を考えずに書くとエラーで止まります。空のときの扱いは、試験でも現場でも最初に決めるべき場所です。

似た構造の問題と混ぜない¶

連結リストの問題と、スタック・キューの問題は見た目が似ています。どちらも要素をたどる形になるからです。

違いは、取り出す位置が決まっているかどうかです。スタックとキューは出口が固定されていますが、連結リストは途中を書き換えます。

連結リストの追い方は別の記事で扱っているので、混同しやすい人はあわせて読んでみてください。

【関連記事】科目Bの連結リスト問題の解き方｜nextを図にして追う

実務ではどこで使われているか¶

試験のためだけの構造ではない、という話もしておきます。この2つは、現場のシステムで毎日動いています。

キューは、注文やメール送信のように順番どおり処理したい場面で使います。先に届いた依頼から片づけるので、行列の考え方そのものです。

スタックは、直前の操作を取り消す機能や、処理の呼び出し履歴を管理する場面で出てきます。最後にやったことから戻す、という動きが必要だからです。

使われている場面を知っておくと、どちらを使うべきかで迷わなくなります。順番を守りたいならキュー、直前に戻りたいならスタックです。

シミュレーターで動かして確かめる¶

紙の表だけで終わらせると、合っているかどうかの確認ができません。答え合わせの手段を持っておきましょう。

Giji Academy の擬似言語シミュレーターなら、コードを1行ずつ実行して変数の値が変わる様子を画面で見られます。自分で書いた表と画面を並べれば、ずれた行がその場で分かります。

擬似言語シミュレーターで出し入れの順番を見てみる

無料で使えるので、先ほどのコードをそのまま試してみてください。push を enqueue に置き換えると、結果が逆になることも確かめられます。

自分で条件を変えて解き直す¶

一度解いた問題は、条件を変えるともう一度使えます。要素を4つに増やす、取り出す回数を1回減らす、といった変更で十分です。

同じコードでも、回数が変わると答えが変わります。その感覚が身につくと、本番でループ回数を数え間違えなくなります。

私も新しい処理を書いたときは、極端な値を入れて動かしてみます。空のとき、1個だけのとき、この2つで確かめるのが習慣です。

まとめ¶

科目Bのスタック・キュー問題は、覚える量がとても少ない分野です。出ていく順番を表で追えれば、それだけで正解にたどり着けます。

今日お伝えした手順を振り返っておきましょう。

この5段階は、ほかの科目Bの問題にもそのまま使えます。読む場所を決めて、表で追って、選択肢を疑う。やることは毎回同じです。

最初は表を書くのが面倒に感じるかもしれません。それでも3問も書けば、手が勝手に動くようになります。

まずは今日、さきほどのコードを自分の手で追ってみてください。CBA と書けたなら、この分野はもう取れる分野です。