language-agnostic - 再帰を繰り返しシミュレートできる構造は何ですか

Question

スタックになると思いますが、スキップリスト、bst、またはキューでしょうか?

押したりはねたりし続けることができるので、スタックであることは理にかなっています。しかし、入ってくる順に追加するので、キューの方が良いでしょうか?

Answer 1

あなたは基本的に自分で質問に半分答えました：再帰を使用した場合、コンパイラが行うのと同じ順序でスタックにプッシュおよびスタックからポップできるため、スタックを使用することは理にかなっています。人々が期待する方法で物事を行うことは良いことです（たとえあなたがそれらを異なって行うことができたとしても）。

スタックは、問題の最も簡単な解決策であり、オーバーヘッドが最小のコンテナーであり、要素は、特別なことをすることなく、再帰を実行するときに通常必要な順序で出力されます。

それに比べて、キューには先頭と末尾があるため、はるかに複雑であり、メモリ管理はより複雑です（スタックは基本的にメモリのチャンクとインクリメント/デクリメントされるポインタです）。

また、キューを使用する場合、要素はプッシュした順序で出力されます。これは、一部の問題では問題にならない場合があります（たとえば、すべての要素を1回だけ繰り返し、順序を気にしない場合）。バックトラックするのは不必要に複雑です。たとえば、データのブロックを再帰的に細分割したり、ツリーを再帰的に歩いたりする場合、最初に左半分に再帰し、次に左半分に再帰します。
最大深度に達したら、1つのレベルをバックトラックして、右半分に戻ります（さらに、別のレベルをバックトラックします）。スタックを使用すると、これは単純なポップで簡単に実行できます。キューがある場合は、どこに行くかを明示的に覚えておく必要があります。もちろんそれは不可能ではありませんが、それは正確に些細なことではありません。

スキップリストについても言及されました。スキップリストは実際には「リスト」のような単純なものではなく、検索ツリーにはるかに匹敵するかなり複雑な構造であることに注意してください。また、これは問題の「自然な選択」ではなく、その複雑さのために、再帰のようなものに使用したいものではありません（ただし、十分に頑固であれば、おそらく機能させることができます）。