假设某个应用程序需要使用两个元素类型相同的堆栈。这种双栈数据类型的自然存储结构将由两个数组和两个顶部指针组成。解释为什么这可能不是一个空间有效的实现。
最佳答案
我认为这个问题的意思是，如果您想同时表示两个堆栈，则可以使用单个元素数组来实现。在堆栈的典型数组实现中，元素存储在具有一定数量的“松弛空间”可用于增长的数组中。当该空间用完时，数组的大小会增加(通常通过加倍以获得分期 O(1) 插入)，旧元素被复制，并且可以继续增长。
这种方法效果很好，但如果你知道你将有两个堆栈，它可以做得更好一点。特别是，假设您有两个堆栈，每个堆栈都有一些“松弛空间”，其中一个堆栈用完了松弛空间。如果发生这种情况，如果可以使用其他堆栈中的一些未使用的松弛空间来继续增长第一个堆栈，那就太好了。这将为我们节省额外的分配/复制，并使我们能够更有效地利用可用空间。
如果你有两个堆栈，你可以做到这一点的一种方法是让它们中的两个共享一个数组并从相对的两侧向内增长。例如，如果我有一个包含元素的堆栈 1 2 3另一个带有元素 4 5 6 ，那么这可能在内存中具有以下表示:
[1] [2] [3] [ ] [ ] [6] [5] [4]
如果我们将一个值压入第一个堆栈，例如
9 ，我们像这样增长堆栈:[1] [2] [3] [9] [ ] [6] [5] [4]
如果我们将一个值压入第二个堆栈，例如
0 ，我们将其堆栈增长为[1] [2] [3] [9] [0] [6] [5] [4]
如果我们现在需要通过压入一个值来增大任一堆栈，那么我们将使用标准的重新分配技术将其移动到一个更大的数组中。但是，优势在于，如果一个堆栈大部分是空的，而另一个堆栈相当大，那么我们可以从内存中获得非常好的使用率。例如，这是一种可能的堆栈配置:
[1] [2] [3] [4] [5] [6] [ ] [0]
这里，一个堆栈有六个值，一个堆栈只有一个。请注意，我们通过共享数组非常有效地使用了我们的空间。
关于c++ - C++中两个堆栈的有效表示？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4915283/