はじめに
今回は平成30年秋春期問5の回答、解説です。平成30年秋春期問5はデータ構造のスタックついての問題です。本問を通してデータ構造のスタックについて学んでいきましょう。
問題を解くためのキーワード
- スタック
- PUSH命令、POP命令
- 後入れ先出し(LIFO:Last-in First-out)
問題のカテゴリ
今回の問題カテゴリは以下の通りです。
分野 | 大分類 | 中分類 |
テクノロジ系 | 基礎理論 | アルゴリズムとプログラミング |
問題
次の二つのスタック操作を定義する。
PUSH n:スタックにデータ(整数値n)をプッシュする。
POP:スタックからデータをポップする。
空のスタックに対して,次の順序でスタック操作を行った結果はどれか。
PUSH 1 → PUSH 5 → POP → PUSH 7 → PUSH 6 → PUSH 4 → POP → POP → PUSH 3
![](https://www.herochannel.net/wp-content/uploads/2023/10/スクリーンショット-2023-10-23-14.15.24-1024x275.png)
解説
スタックについて
本問に登場するスタックとはデータ構造のひとつで、最後に格納したデータから順に処理を行う、後入れ先出し(LIFO:Last-in First-out)方式でのデータ構造を指します。後入れ先出し(LIFO:Last-in First-out)方式ではデータを格納することをPUSHといい、データを取り出すことをPOPといいます。
スタックのPUSH(データ格納)のイメージを説明します。ここで、データ1〜データ4をスタックにPUSHする時は後入れなので、以下のようなイメージになります。
![](https://www.herochannel.net/wp-content/uploads/2023/10/スクリーンショット-2023-10-23-21.31.33.png)
次にPOP(データ取り出し)のイメージです。スタックからPOPする時は先出しなので、以下のようなイメージになります。
![](https://www.herochannel.net/wp-content/uploads/2023/10/スクリーンショット-2023-10-23-21.36.02.png)
最後に格納されたデータ4から取り出しされます。
それではこれまでの知識で試験問題を解いてみましょう。
試験問題を解いてみる
改めて本問をみてみましょう。
次の二つのスタック操作を定義する。
PUSH n:スタックにデータ(整数値n)をプッシュする。
POP:スタックからデータをポップする。
空のスタックに対して,次の順序でスタック操作を行った結果はどれか。
PUSH 1 → PUSH 5 → POP → PUSH 7 → PUSH 6 → PUSH 4 → POP → POP → PUSH 3
![](https://www.herochannel.net/wp-content/uploads/2023/10/スクリーンショット-2023-10-23-14.15.24-1-1024x275.png)
それぞれを以下のように分解してイメージしてみましょう。
- PUSH 1 → PUSH 5 → POP
- PUSH 7 → PUSH 6 → PUSH 4 → POP → POP
- PUSH 3
1.PUSH 1 → PUSH 5 → POP
![](https://www.herochannel.net/wp-content/uploads/2023/10/スクリーンショット-2023-10-23-21.46.49.png)
2.PUSH 7 → PUSH 6 → PUSH 4 → POP → POP
![](https://www.herochannel.net/wp-content/uploads/2023/10/スクリーンショット-2023-10-23-21.49.49.png)
3.PUSH 3
![](https://www.herochannel.net/wp-content/uploads/2023/10/スクリーンショット-2023-10-23-21.51.19.png)
よって正解はウとなります。
おわりに
今回は平成30年秋春期問5の回答、解説しました。