私は最終試験に向けて勉強していますが、この問題がわかりません:
クライアントがスタックのプッシュ操作とポップ操作の混合シーケンスを実行するとします。プッシュ操作は、0 から 9 までの整数を順番にスタックにプッシュします。pop 操作は戻り値を出力します。次のシーケンスのうち、起こり得ないものはどれ?
(a) 4 3 2 1 0 9 8 7 6 5
(b) 2 1 4 3 6 5 8 7 9 0
(c) 0 4 6 5 3 8 1 7 2 9
(d) 4 6 8 7 5 3 2 9 1 0
(e) これらのシーケンスはすべて可能です
答えはCですが、その結論に至る方法がわかりません
わかりました。プログラムは常に 0 から 9 をこの順序でプッシュします。各行を見て、プッシュとポップが発生する順序を特定します。
**The first line.** - Stack is
Pushes 0, 1, 2, 3, 4 - [0, 1, 2, 3, 4]
Pops 4, 3, 2, 1, 0 - []
Pushes 5, 6, 7, 8, 9 - [5, 6, 7, 8, 9]
Pops 9, 8, 7, 6, 5 - []
**Second line** - Stack is
Pushes 0, 1, 2 - [0, 1, 2]
Pops 2, 1 - [0]
Pushes 3, 4 - [0, 3, 4]
Pops 4, 3 - [0]
Pushes 5, 6 - [0, 5, 6]
Pops 6, 5 - [0]
Pushes 7, 8 - [0, 7, 8]
Pops 8, 7 - [0]
Pushes 9 - [0, 9]
Pops 9, 0 - []
**Third line** - Stack is
Pushes 0 - [0]
Pops 0 - []
Pushes 1, 2, 3, 4 - [1, 2, 3, 4]
Pops 4, - [1, 2, 3]
Pushes 5, 6 - [1, 2, 3, 5, 6]
Pops 6, 5, 3 - [1, 2]
Pushes 7, 8 - [1, 2, 7, 8]
Pops 8 - [1, 2, 7]
Pops ?
次の popは 7 でなければなりません。これは 8 の前にプッシュされたため、 1 になることはできません。
これを解決するのは難しくありません。最初にポップされた番号が見つかるまで、シーケンスを書き始めます。それを取り消して続行します。これで、3 番目のシーケンスが発生しない理由がわかります。
0 // Pop 0
-
1 2 3 4 // Pop 4
1 2 3
1 2 3 5 6 // Pop 6
1 2 3 5 // Pop 5
1 2 3 // Pop 3
1 2
1 2 7 8 // Pop 8
1 2 7 // And here it fails; you cannot possibly pop a 1 from the stack
出力シーケンス内の減少するサブシーケンスの場合、出力内でandが前に来ず、サブシーケンスの一部ではないk[a1, ..., an]が存在することはできません。ak > a1ak < anakak[a1, ..., an]
ここで [8, 1] はそのようなサブシーケンスの 1 つであり、7 は前に来ておらず、まだサブシーケンスの一部ではありません。
1 の前に 8 が印刷されているため、1 がポップされたとき、8 までの数字はすでにプッシュされています。しかし、その場合は 2 もプッシュされているため、1 の前にポップする必要があります。
編集：より詳細に - シーケンスに値 x と値 y があり、x > y があり、x がシーケンスの y の前にある場合、間隔 [y, x] の値は満たされませんy の後のシーケンス。