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

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

覚えておきたい

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

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

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

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

ア　a、b、c

イ　b、a、c

ウ　c、a、b

エ　c、b、a

正解の理由（令和元年　問62）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

よって、正解は　ウ　です。

PUSH x：品物xを1個積み上げる。 POP：　一番上の品物を1個取り出す。