はじめに確認しておきましょう。
データ構造は、データを効率的に管理するための整理方法です。リスト、キュー、スタック、木構造、2分木などの種類があります。
スタックでは、最後に格納されたデータを最初に取り出します。
令和元年 問62
下から上へ品物を積み上げて、上にある品物から順に取り出す装置がある。この装置に対する操作は、次の二つに限られる。
| PUSH x：品物xを1個積み上げる。 POP： 一番上の品物を1個取り出す。 |  |
最初は何も積まれていない状態から開始して、a、 b、cの順で三つの品物が到着する。一つの装置だけを使った場合、POP操作で取り出される品物の順番としてあり得ないものはどれか。
正解の理由
(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 の順番で品物が取り出されることはあり得ません。
よって、正解は ウ です。
コメント