擬似言語トレースドリル

配列で作るスタック｜擬似言語のトレース解説と練習問題

レベル：基礎　／　タグ：スタック・大域変数・手続・配列

大域の配列 stack と変数 top でスタックを表す。手続 push は値を積み、関数 pop は最後に積んだ値を取り出して返す。関数 test は、取り出した値を順に並べた整数を返す。配列の要素番号は 1 から始まる。

プログラム

1大域: 整数型の配列: stack ← {3 個の 0}
2大域: 整数型: top ← 0
3
4○push(整数型: x)
5 top ← top ＋ 1
6 stack[top] ← x
7
8○整数型: pop()
9 整数型: v ← stack[top]
10 top ← top － 1
11 return v
12
13○整数型: test()
14 整数型: r
15 push(8)
16 push(4)
17 r ← pop()
18 push(6)
19 r ← r × 10 ＋ pop()
20 r ← r × 10 ＋ pop()
21 return r

何をしているか

大域の配列 stack に値を積み、変数 top で「いちばん上の値が入っている要素番号」を覚えておきます。push は top を 1 増やしてからその位置に書き込み、pop は top の位置の値を読んでから top を 1 減らします。

トレースのコツ

  • 表には top と stack 全体を書きます。大域変数なので、どの手続の中でも同じものを指します。
  • pop しても配列の中の値は消えません。top が下がるだけで、次の push で上書きされます。
  • 「読んでから減らす」「増やしてから書く」の順番を、1行ずつ確かめます。

よくある間違い

  • 取り出す順を、入れた順と同じにしてしまう。スタックは後入れ先出しです。
  • pop のあとに配列の値が 0 に戻ると思い込む。
  • top を「次に入れる位置」と読み違える。このプログラムでは「いちばん上の値の位置」です。

例題：test() を最後まで追う

上のプログラムを test() で呼び出したときの、全ステップのトレース表です。太字は、その文で値が変わった変数です。

#行したこと手続stacktoprxv
11宣言(main){0, 0, 0}————
22宣言(main){0, 0, 0}0———
314宣言test{0, 0, 0}0未定義——
45代入　push{0, 0, 0}1—8—
56代入　push{8, 0, 0}1—8—
615呼出しtest{8, 0, 0}1未定義——
75代入　push{8, 0, 0}2—4—
86代入　push{8, 4, 0}2—4—
916呼出しtest{8, 4, 0}2未定義——
109宣言　pop{8, 4, 0}2——4
1110代入　pop{8, 4, 0}1——4
1211戻る（4）　pop{8, 4, 0}1——4
1317代入test{8, 4, 0}14——
145代入　push{8, 4, 0}2—6—
156代入　push{8, 6, 0}2—6—
1618呼出しtest{8, 6, 0}24——
179宣言　pop{8, 6, 0}2——6
1810代入　pop{8, 6, 0}1——6
1911戻る（6）　pop{8, 6, 0}1——6
2019代入test{8, 6, 0}146——
219宣言　pop{8, 6, 0}1——8
2210代入　pop{8, 6, 0}0——8
2311戻る（8）　pop{8, 6, 0}0——8
2420代入test{8, 6, 0}0468——
2521戻る（468）test{8, 6, 0}0468——

この例題で問われること

問　test() を呼び出したときの戻り値はどれか。

答え　468

  • 呼出しは全部で4回行われます。
  • 奥の呼出しから順に 4 → 6 → 8 → 468 を返し、最後に返る 468 が答えです。

問　6行目を3回目に実行した直後の、変数 stack の値はどれか。

答え　{8, 6, 0}

  • 6行目は全部で3回実行されます。
  • 実行した直後の stack は、順に {8, 0, 0} → {8, 4, 0} → {8, 6, 0} です。
  • 3回目の直後なので、答えは {8, 6, 0} です。

問　10行目を3回目に実行した直後の、変数 top の値はどれか。

答え　0

  • 10行目は全部で3回実行されます。
  • 実行した直後の top は、順に 1 → 1 → 0 です。
  • 3回目の直後なので、答えは 0 です。

練習問題 標準（10問）

本試験と同じくらいの量。レベル：基礎

  1. 問題01　test()
  2. 問題02　test()
  3. 問題03　test()
  4. 問題04　test()
  5. 問題05　test()
  6. 問題06　test()
  7. 問題07　test()
  8. 問題08　test()
  9. 問題09　test()
  10. 問題10　test()
もっと解く（追加の20問）
  1. 問題11　test()
  2. 問題12　test()
  3. 問題13　test()
  4. 問題14　test()
  5. 問題15　test()
  6. 問題16　test()
  7. 問題17　test()
  8. 問題18　test()
  9. 問題19　test()
  10. 問題20　test()
  11. 問題21　test()
  12. 問題22　test()
  13. 問題23　test()
  14. 問題24　test()
  15. 問題25　test()
  16. 問題26　test()
  17. 問題27　test()
  18. 問題28　test()
  19. 問題29　test()
  20. 問題30　test()

ほかのアルゴリズム