擬似言語のスタックとキューの違いとは？科目Bで出る出し入れの順番を解説

スタックとキュー、どっちがどっちだったか毎回あやしくなる。

言葉は聞いたことがあるのに、問題になると手が止まりませんか？

科目Bでは、この二つがそのまま問われることも、他の処理の部品として登場することもあります。どちらにしても、押さえる中身は多くありません。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務でも、処理を待たせる順番をどちらの型にするかで、システムの振る舞いがまるごと変わります。

その感覚は、試験に出る擬似言語でもそのまま使えます。この記事では、二つの型を並べながら、コードのどこを見れば見分けられるのかを整理していきます。

スタックとキューは、出し入れの順番が違うだけ¶

まずは大枠から確認しましょう。スタックもキューも、データを一時的にためておく入れ物です。

入れ物としての役割は同じです。違うのは、たまったデータのうち、どれを先に取り出すかという一点だけになります。

スタックは、最後に入れたものから取り出します。キューは、最初に入れたものから取り出します。

この一行が理解できていれば、あとは書き方の問題です。逆に、ここがあいまいなままコードを読むと、必ず途中で迷子になります。

日常のたとえで押さえておく¶

言葉だけだと入りにくいので、身近な場面に置き換えてみましょう。

スタックは、机に積み上げた本と同じです。上に置いた本から順に取っていくので、最初に置いた一番下の本は最後まで残ります。

キューは、レジに並ぶ行列です。先に並んだ人から順に会計を済ませ、後から来た人は最後尾に付きます。

このたとえは試験本番でも役に立ちます。問題文を読みながら、机の上の本か、レジの行列か、どちらの絵が浮かぶかを確かめてみてください。

なお、後入れ先出しをLIFO、先入れ先出しをFIFOと呼ぶこともあります。用語として問われることもあるので、頭の片隅には置いておきましょう。

スタックは後入れ先出しで動く¶

では、スタックから詳しく見ていきます。スタックに対する操作は、基本的に二つだけです。

データを入れる操作をpush、取り出す操作をpopと呼びます。名前は問題によって多少変わりますが、役割は変わりません。

擬似言語では、スタックの中身を配列で表し、今どこまで入っているかを整数の変数で持つ形がよく出ます。実際のコードを見てみましょう。

○大域: 整数型の配列: stack ← {}   /* データを入れる場所 */
○大域: 整数型: top ← 0            /* 今、何個入っているか */

○push(整数型: value)
  top ← top + 1
  stack[top] ← value

○整数型: pop()
  整数型: value

  value ← stack[top]    /* 一番上の値を取り出す */
  top ← top - 1         /* 使った分だけ位置を戻す */
  return value

追うべき変数はtopだけです。この一つが、スタックの状態をすべて表しています。

topが0なら中身は空、3なら3個入っている。それだけの話なので、身構える必要はありません。

push と pop で top がどう動くか¶

実際に動かしてみましょう。空のスタックに5、8を入れて、一度取り出し、3を入れて、また二度取り出す流れです。

その前に、topが指しているのは常に一番上の要素の位置だという点を意識してください。ここを押さえると表が読みやすくなります。

最初に入れた5が、最後に出てきました。これが後入れ先出しの正体です。

もう一つ注目してほしいのは、4行目です。popでtopを1に戻したあと、pushすると同じ位置に3が上書きされます。

配列の中に8が残っているかどうかは、実は問題になりません。topより上は無いものとして扱うからです。

こうした添字の動きに不安があるなら、配列の基本から確認しておくと理解が早くなります。

【関連記事】擬似言語の配列と添字がわからない人へ｜要素数・二次元配列の読み方を解説

空のときに pop すると壊れる¶

スタックの問題で必ず出てくる論点があります。中身が空なのにpopしたらどうなるか、です。

topが0のときにstack[top]を読むと、存在しない0番目を参照することになります。これは異常な状態です。

だから実際の問題では、popの先頭に空かどうかの判定が入ります。次のような形になります。

○整数型: pop()
  整数型: value

  if (top = 0)
    return -1           /* 空なので取り出せない */
  endif

  value ← stack[top]
  top ← top - 1
  return value

空欄補充で、この判定条件そのものを選ばせる問題は実際に出ます。topが0か、それとも1未満か、といった選択肢が並ぶ形です。

判断に迷ったら、実際に空の状態を思い浮かべてください。topが0のとき何が起きるかを確かめれば、答えは自然に決まります。

キューは先入れ先出しで動く¶

続いてキューです。こちらの操作も二つで、入れる操作をenqueue、取り出す操作をdequeueと呼びます。

スタックとの決定的な違いは、入れる場所と出す場所が反対側にあることです。後ろから入れて、前から出ます。

そのため、追う変数が二つに増えます。先頭の位置と、末尾の位置です。

コードにすると、こうなります。

○大域: 整数型の配列: queue ← {}
○大域: 整数型: head ← 1     /* 次に取り出す位置 */
○大域: 整数型: tail ← 0     /* 最後に入れた位置 */

○enqueue(整数型: value)
  tail ← tail + 1
  queue[tail] ← value

○整数型: dequeue()
  整数型: value

  if (head > tail)
    return -1              /* 空なので取り出せない */
  endif

  value ← queue[head]      /* 先頭の値を取り出す */
  head ← head + 1          /* 先頭を一つ進める */
  return value

headとtail、この二つが追えれば読めます。片方だけを見ていると、途中で必ずずれます。

先頭と末尾、二つの位置を追う¶

こちらも動かして確かめましょう。5、8を入れて一度取り出し、3を入れて、また二度取り出す流れです。スタックとまったく同じ操作順にしてあります。

比べながら読むと、違いがはっきりします。

同じ操作をしたのに、取り出される順番がスタックと違いました。最初に入れた5が、最初に出てきています。

もう一つ気づいてほしいのは、最後の行です。headがtailを追い越して、head > tail になりました。

この状態が空を意味します。空の判定にhead > tailを使う理由が、表を見ると腑に落ちるのではないでしょうか。

変数の動きを表に書き出す作業は、キューに限らずどの問題でも効きます。型を持っておくと、本番で慌てません。

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

配列の後ろが尽きる問題¶

キューには、少し厄介な性質があります。dequeueをしてもheadが進むだけなので、配列の前のほうが使われないまま残るのです。

enqueueを繰り返すとtailが配列の端に届き、まだ空きがあるのに入れられなくなります。

この対策として、末尾まで来たら先頭に戻る形が使われます。輪のようにつながっているという意味で、リングバッファや循環キューと呼ばれる考え方です。

科目Bで出るとしたら、剰余を使ってtailを1に戻す処理が絡みます。ややこしく見えますが、端まで来たら先頭に戻るという意図さえ分かっていれば読み解けます。

二つを並べて整理する¶

ここまでの内容を、一度まとめて見比べておきましょう。違いがはっきりすると、問題を見た瞬間にどちらか判断できるようになります。

比べるポイントは、取り出す順番と、追う変数の数です。

表の一行目が、見分けの決め手です。問題文に取り出す順番の説明があれば、そこだけでどちらか決まります。

追う変数の数も手がかりになります。変数が一つならスタック、二つならキューと当たりを付けて読み始められます。

科目Bではどんな形で出るのか¶

そのまま出題される場合は、問題文の冒頭で操作の仕様が定義されます。この関数は末尾に追加する、この関数は先頭を取り出す、といった説明です。

大事なのは、名前ではなく説明文のほうです。pushという名前でも、説明が先頭から取り出すとなっていればキューとして扱います。

思い込みで読むと、そこで一問落とします。定義は必ず読んでください。

部品として出る場合もあります。式の計算や、たどる順番を管理する処理の中で、裏方としてスタックが使われる形です。

このとき、操作は手続や関数の形で与えられます。引数と戻り値の関係があいまいだと読みにくくなるので、そこが不安なら先に確認しておきましょう。

【関連記事】擬似言語の手続と関数の違いとは？引数・戻り値と変数の有効範囲を解説

手を動かして確かめると定着が早い¶

読んで納得しても、自分で追うとまた別のところで詰まります。とくにキューは、headとtailが同時に動く場面で混乱しやすいところです。

Giji Academy の擬似言語シミュレーターでは、一行ずつ実行しながら変数の中身を確認できます。topやheadが増えたり減ったりする様子が、そのまま目で見えます。

自分の予想と実行結果を突き合わせて、ずれた場所を探してみてください。そこが、次に復習すべき一点です。よかったら学習ページから試してみてください。

よくある間違いと直し方¶

私が学習相談を受ける中で、この分野では同じつまずきが繰り返し出てきます。まとめて確認しておきましょう。

一番多いのは、一行目です。型を決めないまま追い始めて、途中でどちらの順番だったか分からなくなる形が目立ちます。

問題を読んだら、まず余白にスタックかキューかを書いてしまいましょう。それだけで防げます。

科目Bは20問を100分で解く試験です。一問あたりに使える時間を考えると、型を即断できるかどうかは大きな差になります。

構造を先に見抜ければ、残りは値を追うだけです。この順番を守ってください。

まとめ¶

スタックは、最後に入れたものから取り出す入れ物でした。追う変数はtopの一つだけで、空の判定はtopが0かどうかで決まります。

キューは、最初に入れたものから取り出す入れ物です。headとtailの二つを追い、headがtailを追い越したら空になります。

見分け方は、問題文にある取り出す順番の説明。この一点で判断できます。

どちらも、実際に数個のデータを入れて出す表を書けば、動きは必ず追えます。頭の中だけで処理しようとしないことが、遠回りに見えて一番の近道です。

擬似言語の記号や書き方そのものに不安が残る場合は、早見表で全体を眺めておくと安心です。

【関連記事】擬似言語の記号・記述形式一覧｜試験前のチェック早見表

スタックとキューが読めるようになると、木構造をたどる問題や、待ち行列を扱う問題も同じ目線で読めるようになります。次に問題を開いたら、まず取り出す順番の定義から探してみてください。