c++ - 判断出栈顺序是否合法。

Question

给定入栈顺序，判断出栈顺序是否合法？

要求：
空间复杂度O(1)
时间复杂度O(n)
 

网上提供的算法都是新建一个栈，空间复杂度为O(N),可不可以通过O(1)解决

Answer 1

スタックが a、b、c、d、e で​​、一番下が e であるとします。次に、[e, d, c, b, a] など、スタックにプッシュする順序を記録する配列があります。これは、e が最初にスタックにプッシュされることを意味します。現時点では、スタック容量を保存するために必要な変数は 1 つだけです。初期値は 5 です。

a がスタックからポップされると、変数に 5 が格納されていることがわかり、配列の 5 番目のビットと比較され、変数 -1 は 4 になります
b がスタックからポップされると、スタックして、変数に4が格納されていることが分かり、データと比較します 4ビット目を比較すると、変数-1は3
...

になります

これはあなたが望むスペース O(1) ですか、それとも私が質問を誤解していますか?

Answer 2

質問は間違っています。

[ポップシーケンスが合法かどうかを判断する]は、[人間が人間であるかどうかを判断する]と同等です。

コンテナがスタックの場合、順番にプッシュおよびポップする必要があります。したがって、スタックをポップする順序が合法であるかどうかには疑問の余地はありません。

---

さらに、質問者が実際にはスタックに出入りする過程であらゆる可能性をテストしたかったことはわかりますが、質問にはその必要性が反映されていません。質問は間違っています。