當使用連續分配時，兩個堆棧如何共享一段內存

Question

在我的CS數據結構類中提到了這個主題，但我沒有退出。所以想知道是否有人可以花一點時間向我解釋這將如何在內存中順序分配。

這將是非常有用的圖表或一些例證，可以幫助我理解它。
另外我想知道這是否會發生在兩個隊列中。

謝謝

Answer 1

我假設順序分配這裏使用的是指沒有間隙的內存塊。

一種可能性是，這可能是一個像deque（雙端隊列），除了這將是一個雙端堆棧。因此，舉個例子，你分配一個連續內存塊，它有足夠的內存用於N個元素，你將會有一個指向第一個堆棧的「頂部」的指針，這個指針會從第一個元素開始，然後向右擴展。你也可以有一個指向第二個堆棧的「頂部」的指針，它將從最後一個元素開始並向左增長。如果兩個「上衣」互相交叉，則需要「增長」記憶的時間;重新分配並將一個或兩個堆棧複製到新的位置。因此，每個堆疊的可以增長，直到兩個其大小一起超過N.

插圖（從here，頁使用這樣的數據結構作爲分配器討論）：

對於隊列，是的，你創建了兩個隊列，但它可能會有一個額外的洞/間隙，因爲隊列的底部可以向上移動（遠離兩端）。一個可能的解決方案是，不是從前面彈出，而是可以清空前面的元素，並與後面交換，同時保留指向實際前面和後面的指針。

Answer 2

硬件調用棧總是在相同的方向生長，但你可以有兩個軟件棧從分配的兩端發展。這看起來微不足道，很可愛，所以它可能不是你所說的。