memory - 使用顺序分配时两个堆栈如何共享一段内存

Question

这个话题在我的CS数据结构课中提到过，但我没有退出。所以想知道是否有人可以花一点时间向我解释这将如何与内存中的顺序分配一起工作。

图表或一些可以帮助我理解它的插图将非常有帮助。
另外我想知道这是否会发生在两个队列中。

谢谢

Answer 1

硬件调用堆栈总是以相同的方向增长，但您可以有两个软件堆栈从分配的两端增长。这看起来微不足道和可爱，所以它可能不是你在说的。

Answer 2

我假设这里使用的顺序分配意味着一块内存，没有间隙。

一种可能性是这可能类似于双端队列（双端队列），除了这将是一个双端堆栈。因此，例如，您分配了一块具有足够内存用于 N 个元素的顺序内存块，您将有一个指向第一个堆栈的“顶部”的指针，该指针将从第一个元素开始并向右增长。您还将有一个指向第二个堆栈的“顶部”的指针，该指针将从最后一个元素开始并向左增长。如果两个“顶”相互交叉，是时候“增长”记忆了；重新分配并将一个或两个堆栈复制到新位置。因此，每个堆栈都可以增长，直到它们的大小加起来超过 N。

插图（来自这里，一个讨论使用分配器等数据结构的页面）：

关于队列，是的，您在此块之外创建了两个队列，但它可能会有一个额外的孔/间隙，因为队列的底部可以向上移动（远离末端）。一个可能的解决方案是，与其从前面弹出，不如清空前面的元素，并与后面交换，同时保持指向实际前面和后面的指针。