【スタックの問題の解き方】ITパスポート令和元年問62解説

【スタックの問題の解き方】ITパスポート令和元年問62解説特集
スポンサーリンク

はじめに確認しておきましょう。

覚えておきたい

データ構造は、データを効率的に管理するための整理方法です。リスト、キュー、スタック、木構造、2分木などの種類があります。

スタックでは、最後に格納されたデータを最初に取り出します。

スタックの説明図(テクノロジ系アルゴリズムとプログラミング36.データ構造)

令和元年 問62

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

PUSH x:品物xを1個積み上げる。
POP:  一番上の品物を1個取り出す。
ITパスポート令和元年秋問62スタック図

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

ア a、b、c
イ b、a、c
ウ c、a、b
エ c、b、a
 

正解の理由

(1) ”求めるもの”と”条件”を確認します。

【求めるもの】
 POP操作で取り出される品物の順番としてあり得ないもの

【条件】
 最初は何も積まれていない状態から開始して、a、 b、cの順で三つの品物が到着する。

(2)問題を解く大筋を確認します。

この問題では、取り出されたものの順番と積まれた商品を比較して、PUSHとPOPの順番を考えるのが大筋です。

ITパスポート令和元年問62問題を解く大筋の説明図

(3) 考えやすいパターンから、選択肢を確認します。

この問題では、a、b、cが順番に並んでいるので、ア から考えるのが易しいでしょう。

(いつも、問題を解く時、選択肢の から考える必要はありません。)

 a、b、cの順番は、図のようなPUSH、POPの操作を行うと実現できます。

ITパスポート令和元年問62選択肢アの説明図

a、b、cが逆に順番に並んでいるので、エ を考えます。

 c、b、aの順番は、図のようなPUSH、POPの操作を行うと実現できます。

ITパスポート令和元年問62選択肢エの説明図

次は、イ でも ウでもいいのですが、とりあえず、イ を考えます。

 b、a、cの順番は、図のようなPUSH、POPの操作を行うと実現できます。

ITパスポート令和元年問62選択肢イの説明図

 c、a、bの順番について考えます。

ITパスポート令和元年問62選択肢ウの説明図

図に示すように、c、a、bの順番で品物が取り出されることはあり得ません。

よって、正解は  です。

コメント

タイトルとURLをコピーしました