ソフトウェア開発技術者試験 2003年度 ＝ 平成15年度 午前 問10

　A、B、Cの順序で入力されるデータがある。各データについてスタックヘの挿入と取出しを一回ずつ任意のタイミングで行うことができる場合、データの出力順序は何通りあるか。


ア　3 イ　4 ウ　5 エ　6

解答

ウ

解説

　スタックは、後入れ先出し＝LIFO（last-in first out）によってデータを蓄えるデータ構造です。
　本問では、A、B、Cが順にプッシュ（挿入）されます。ポップ（取出し）は、データが一つ以上蓄えられているときにのみ行えますので、以下に示すように、5通りの出力順序があります。


[１]
　　　　 PUSH A　　 POP A　　PUSH B　　 POP B　　PUSH C　　 POP C　　　
　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃
　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃
　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃
　　┃　┃　　┃Ａ┃　　┃　┃　　┃Ｂ┃　　┃　┃　　┃Ｃ┃　　┃　┃　　　Ａ、Ｂ、Ｃ
　　┗━┛　　┗━┛　　┗━┛　　┗━┛　　┗━┛　　┗━┛　　┗━┛


[２]
　　　　 PUSH A　　 POP A　　PUSH B　　PUSH C　　 POP C　　 POP B　　
　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃
　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃
　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃Ｃ┃　　┃　┃　　┃　┃
　　┃　┃　　┃Ａ┃　　┃　┃　　┃Ｂ┃　　┃Ｂ┃　　┃Ｂ┃　　┃　┃　　　Ａ、Ｃ、Ｂ
　　┗━┛　　┗━┛　　┗━┛　　┗━┛　　┗━┛　　┗━┛　　┗━┛


[３]
　　　　 PUSH A　　PUSH B　　 POP B　　 POP A　　PUSH C　　 POP C　　
　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃
　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃
　　┃　┃　　┃　┃　　┃Ｂ┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃
　　┃　┃　　┃Ａ┃　　┃Ａ┃　　┃Ａ┃　　┃　┃　　┃Ｃ┃　　┃　┃　　　Ｂ、Ａ、Ｃ
　　┗━┛　　┗━┛　　┗━┛　　┗━┛　　┗━┛　　┗━┛　　┗━┛


[４]
　　　　 PUSH A　　PUSH B　　 POP B　　PUSH C　　 POP C　　POP A　　
　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃
　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃
　　┃　┃　　┃　┃　　┃Ｂ┃　　┃　┃　　┃Ｃ┃　　┃　┃　　┃　┃
　　┃　┃　　┃Ａ┃　　┃Ａ┃　　┃Ａ┃　　┃Ａ┃　　┃Ａ┃　　┃　┃　　　Ｂ、Ｃ、Ａ
　　┗━┛　　┗━┛　　┗━┛　　┗━┛　　┗━┛　　┗━┛　　┗━┛


[５]
　　　　 PUSH A　　PUSH B　　PUSH C　　 POP C　　 POP B　　 POP A　　
　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃　　┃　┃
　　┃　┃　　┃　┃　　┃　┃　　┃Ｃ┃　　┃　┃　　┃　┃　　┃　┃
　　┃　┃　　┃　┃　　┃Ｂ┃　　┃Ｂ┃　　┃Ｂ┃　　┃Ｂ┃　　┃　┃
　　┃　┃　　┃Ａ┃　　┃Ａ┃　　┃Ａ┃　　┃Ａ┃　　┃Ａ┃　　┃Ａ┃　　　Ｃ、Ｂ、Ａ
　　┗━┛　　┗━┛　　┗━┛　　┗━┛　　┗━┛　　┗━┛　　┗━┛
BohYoh.comトップページへ