アルゴリズムとプログラミング
ITパスポート試験「データ構造」の問題
下から上へ品物を積み上げて，上にある品物から順に取り出す装置がある（次の図のように，PUSHで一番上に積み，POPで一番上から取り出す後入れ先出しの構造）。この装置に対する操作は，次の二つに限られる。
PUSH x：品物xを1個積み上げる（一番上に置く）。
POP：一番上の品物を1個取り出す。
最初は何も積まれていない状態から開始して，a，b，cの順で三つの品物が到着する（到着した順にしかPUSHできない）。一つの装置だけを使った場合，POP操作で取り出される品物の順番としてあり得ないものはどれか。
アa，b，c
イb，a，c
ウc，a，b
エc，b，a
正解
ウ．c，a，b
この装置はスタック(後入れ先出し，LIFO)。ウの"c,a,b"を作るには，cを最初に取り出す必要があるのでa,b,cを順に積んで[a,b,c]とし，POPでcを取り出す。次にaを出したいが，一番上はbなのでPOPするとbが出る。aはbより下にあり先に取り出せない。よってc,a,bの順は実現不可能で，あり得ないものはウである。
?選択肢ごとの解説
ア ×a,b,cは実現可能。PUSH a→POP(a)→PUSH b→POP(b)→PUSH c→POP(c)と1個ずつ積んでは出せば到着順そのままに取り出せる。
イ ×b,a,cは実現可能。PUSH a→PUSH b→POP(b)→POP(a)→PUSH c→POP(c)。aの上にbを積んでからbを先に出せばb,a,cとなる。
ウ ○この装置はスタック(後入れ先出し，LIFO)。ウの"c,a,b"を作るには，cを最初に取り出す必要があるのでa,b,cを順に積んで[a,b,c]とし，POPでcを取り出す。次にaを出したいが，一番上はbなのでPOPするとbが出る。aはbより下にあり先に取り出せない。よってc,a,bの順は実現不可能で，あり得ないものはウである。
エ ×c,b,aは実現可能。PUSH a→PUSH b→PUSH…
アルゴリズムとプログラミングの他の問題
この問題の「深掘り・誤答の完全解説・試験のコツ・覚え方」はアプリで。
無料ではじめる →ITパスポート試験の全問を、一問ごとにAIの8-ways解説つきで。SRS暗記カード・全真模試・弱点診断まで。まずは無料で。
ukamiru 過去問 · ITパスポート試験 · itpass-r1a-q62