0 c++ queue stack pointers data-structures
假设某些应用程序需要使用两个元素属于同一类型的堆栈.这种双栈数据类型的自然存储结构将由两个阵列和两个顶部指针组成.解释为什么这可能不是一个空间有效的实现.
我认为这个问题的关键在于,如果你想同时代表两个堆栈,可以使用单个数组元素来实现.在堆栈的典型阵列实现中,元素存储在阵列中,其中一些"松弛空间"可用于增长.当该空间耗尽时,阵列的大小会增加(通常通过加倍来进行分摊的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]
这里,一个堆栈有六个值,一个堆栈只有一个.请注意,我们通过共享数组非常有效地使用了我们的空间.