memory - 順次割り当てを使用する場合、2 つのスタックがメモリの 1 つのセグメントを共有する方法

Question

このトピックは私の CS データ構造クラスで言及されましたが、私はそれに従うことをやめませんでした。誰かが少し時間をかけて、メモリ内の順次割り当てでどのように機能するかを説明してくれるかどうか疑問に思っています。

それを理解するのに役立つグラフやイラストがあると非常に役立ちます。
また、これが 2 つのキューで発生する可能性があるかどうかも疑問です。

ありがとうございました

Answer 1

ハードウェア コール スタックは常に同じ方向に増加しますが、割り当ての両端から 2 つのソフトウェア スタックが増加する可能性があります。これは些細でかわいいように見えるので、あなたが話していることではないかもしれません.

Answer 2

ここで使用されるシーケンシャル割り当ては、ギャップのないメモリ ブロックを意味すると想定しています。

1 つの可能性は、これが両端スタックになることを除いて、deque (両端キュー) のようなものである可能性があります。したがって、たとえば、N 要素に十分なメモリを持つシーケンシャル メモリのブロックを割り当てると、最初の要素から始まり、右に成長する最初のスタックの「トップ」へのポインタが得られます。また、2 番目のスタックの「トップ」へのポインターもあり、最後の要素から始まり、左に伸びます。2 つの「頂点」が交差する場合は、記憶を「成長」させる時です。一方または両方のスタックを新しい場所に再割り当てしてコピーします。したがって、各スタックは、両方のサイズを合わせて N を超えるまで成長できます。

イラスト (ここから、アロケーターなどのデータ構造の使用について説明しているページ):

キューに関しては、はい、このブロックから 2 つのキューを作成しますが、キューの下部が (端から離れて) 上に移動する可能性があるため、余分な穴/ギャップが生じる可能性があります。これに対する考えられる解決策は、前面をポップする代わりに、実際の前面と背面へのポインターを保持しながら、前面要素を空にして背面と交換することです。