堆栈数据存储顺序

无论您如何将数据存储在内存中,只要功能 和性能 与预期一致。

通常,栈被实现为一个具有大小和容量的数组,其中大小是当前栈中元素的数量,容量是可以存储的最大数量,而不需要相对昂贵的内存重新分配。

当需要时,容量通常会翻倍,以便为插入提供分摊的O(1)性能。通常在数组的高索引端使用空空间来实现堆栈比较容易,所以这是通常要做的事情。

为了给出一个特定的例子,当前栈顶可以作为索引存储到顶层元素的数组中。如果将这些项向下添加到数组的最高索引中,那么当增加数组以腾出空间容纳更多元素时,数组顶部的索引也会发生变化。从底部填充时,需要调整数组大小时,顶部元素的索引不会更改。

如果您想以不同的方式实现您的堆栈,您可以这样做,只需确保您的实现的功能和性能都有文档记录。

不是真的。但是,由于没有计算优势(通常)将推送的项目移动到任何其他位置,线性结构(可以提供对当前堆栈“顶部”的快速访问)以及其他功能都可以工作。数组在性能和紧凑性方面满足堆栈结构的需要,因此通常是最佳/明显的选择。

作为一个范例,不,不是真的。作为一个低级的实现细节,向下增长的堆栈有一个微小的优势,即可以使用一个正偏移量从当前堆栈指针对堆栈上已经存在的项进行寻址(例如,这可能对某些CPU架构有用)。