ITパスポート試験

問62

ITパスポート過去問 令和1年度（2019年）問62

下から上へ品物を積み上げて，上にある品物から順に取り出す装置がある。この装置に対する操作は，次の二つに限られる。

PUSH x：品物xを1個積み上げる。

POP：一番上の品物を1個取り出す。

最初は何も積まれていない状態から開始して，a，b，cの順で三つの品物が到着する。一つの装置だけを使った場合，POP操作で取り出される品物の順番としてあり得ないものはどれか。

 

選択肢

  • ア：a，b，c
  • イ：b，a，c
  • ウ：c，a，b
  • エ：c，b，a
  • ア
  • イ
  • ウ
  • エ

正解と解き方・学習ポイント（AI解説）

正解：ウ
あなたの回答：未回答

この装置はスタックで、取り出し（POP）は常に一番上の品物に限られます。cを最初に取り出すには、到着順どおりにa、b、cをPUSHしてからPOPする必要があります。するとcを取り出した直後の一番上はbになるので、次にaを取り出すことはできません。よって、c、a、bの順はあり得ません。

ア：不正解

到着した品物をその都度POPすれば実現できます。例として、PUSH a、POP、PUSH b、POP、PUSH c、POPです。

イ：不正解

a、bをPUSHしてからb、aの順にPOPし、その後cをPUSHしてPOPすれば実現できます。例として、PUSH a、PUSH b、POP（b）、POP（a）、PUSH c、POPです。

ウ：正解

cを最初に取り出すにはa、b、cをPUSHしてからPOP（c）します。その時点でスタック上部は[b, a]となり、一番上のbを残したままaを先にPOPできないため実現できません。

エ：不正解

a、b、cをPUSHしてからPOPを3回行えば実現できます。例として、PUSH a、PUSH b、PUSH c、POP（c）、POP（b）、POP（a）です。

Point

スタックのPUSH・POP操作と、到着順（a、b、c）が固定であるという制約を踏まえて、実現できる取り出し順と実現できない取り出し順を手順として説明できるようになることを目的としています。

解くために必要な知識

この問題を解くには、スタック構造とPUSH/POP（LIFO）の性質を理解している必要があります。

用語の整理

用語 意味
スタック データ（品物）を積み上げて管理し、取り出しは一番上から行う構造です。
LIFO（Last In, First Out） 後入れ先出し。最後に追加した要素が最初に取り出される規則です。
PUSH スタックの一番上に品物を1個追加する操作です。
POP スタックの一番上の品物を1個取り出す操作です。

性質（この問題で使うルール）

POPで取り出せるのは一番上だけ

  • 例として、下から a、b、c の順に積まれている状態では、取り出せる順は c → b → a だけです。

到着順はPUSHの制約になる

  • 品物は a → b → c の順に到着するため、cをPUSHする前にaやbが未到着という状況にはできません。

  • ただし、到着した品物をすぐPOPすることは可能です。

問題の解法手順

解く手順

前提の確認

スタックでは、次が成り立ちます。

  • PUSHは一番上に積みます。

  • POPは一番上からしか取り出せません。

  • 品物はa、b、cの順でしか到着しないので、PUSHできる順番もa、b、cの順に限られます。

「ウ（c，a，b）」が可能かをシミュレーションする

最初にcを取り出すには、cが到着するまでPUSHを進める必要があります。

手順 操作 スタックの状態（左が上） 取り出し済み
1 PUSH a [a]  
2 PUSH b [b, a]  
3 PUSH c [c, b, a]  
4 POP（cを取り出す） [b, a] c

次にaを取り出したいが、スタックの一番上はbです。aはbの下にあるため、aを取り出す前にbをPOPする必要があります。

このため、取り出し順「c，a，b」は実現できません。

参考（他の選択肢が実現できる理由）

  • 「ア（a，b，c）」は、到着のたびにPOPすれば実現できます。

  • 「イ（b，a，c）」は、aとbをPUSHしてbを先にPOPし、その後aをPOPすれば実現できます。

  • 「エ（c，b，a）」は、a、b、cをPUSHしてから順にPOPすれば実現できます。

選択肢ごとの解説

ア：不正解

到着した品物をその都度POPすれば実現できます。例として、PUSH a、POP、PUSH b、POP、PUSH c、POPです。

イ：不正解

a、bをPUSHしてからb、aの順にPOPし、その後cをPUSHしてPOPすれば実現できます。例として、PUSH a、PUSH b、POP（b）、POP（a）、PUSH c、POPです。

ウ：正解

cを最初に取り出すにはa、b、cをPUSHしてからPOP（c）します。その時点でスタック上部は[b, a]となり、一番上のbを残したままaを先にPOPできないため実現できません。

エ：不正解

a、b、cをPUSHしてからPOPを3回行えば実現できます。例として、PUSH a、PUSH b、PUSH c、POP（c）、POP（b）、POP（a）です。

まとめ

この装置はスタックで、取り出し（POP）は常に一番上の品物に限られます。cを最初に取り出すには、到着順どおりにa、b、cをPUSHしてからPOPする必要があります。するとcを取り出した直後の一番上はbになるので、次にaを取り出すことはできません。よって、c、a、bの順はあり得ません。

※本解説は生成AIによる学習支援用の参考情報です。内容の正確性や最新性は保証されません。最終的な判断は、試験実施団体の公式資料をご確認ください。

テクノロジ系 > 基礎理論 > アルゴリズムとプログラミング

順次、単語を追加予定です。もうしばらくお待ちください。