列表的哪一端是顶部？

Question

不可否认,这似乎是一个愚蠢的问题,但请耐心等待.

在我给出的一个与Stack相关的问题中,我们要定义一个函数,它返回堆栈"顶部"的项目.对我来说,我不知道哪一方是"顶级",因为真的,任何一方都可以.

另外,我给出了一个与Queue有关的问题,它要求我们定义一个返回队列"正面"项的函数.同样,任何一方都可以被解释为"前线"

如果问题被重写为要求"返回列表中的最后一项"或"列表中的第一项",那么这是完全合理的,但不幸的是情况并非如此.

所以我想知道:在堆栈/队列方面是否有"前"和"上"的定义基本上只是列表,或者这些术语是否含糊不清？

Answer 1

我认为,严格来说,列表的末尾都不具有成为一个队列的堆叠/正面的顶部.数据结构的实现与数据结构的预期行为是分开的.

例如,堆栈表现出后进先出(LIFO)行为.换句话说,存储在堆栈中的最后一个元素是"顶部"元素.如果您决定将堆栈实现为列表,其中每个新元素都在索引0处添加,并且所有现有元素都被移位1,那么索引0将是您的顶部.另一方面,如果您将堆栈实现为列表,其中每个新元素都附加到列表的末尾,那么索引-1将是您的顶部.

话虽如此,前一个实现效率非常低,因为每次在堆栈上/下移动/弹出值时,都必须移动整个列表,而后一个实现更有效,因为您可以简单地追加/删除元素列表的结尾.

另外,为了指出我没有明确说明的其他答案/评论中提到的内容,您的实现也不必是列表.当我说实现和行为是分开的时,这也适用于底层数据结构.

Answer 2

在堆栈/队列方面是否有"前"和"上"的定义基本上只是列表或这些术语是模糊的

这个问题建立在一个错误的前提上,即堆栈/队列"基本上只是列表".

看一下这张图片,它显示了python列表如何存储在内存中(CPython)

(图片来源:这里)

实现实际上并不像堆栈或队列,实际的列表对象可以遍布内存中.

栈:

这个非常明确:如果有人谈论堆栈的"顶部",他们会指的是最近添加到堆栈中的项目.如果你从堆栈中"弹出",这就是你得到的项目.

队列:

这个人有点通风.如果有人引用队列的前面,它们可能意味着最早添加的项目,因为队列通常实现为"FIFO"(先进先出).但是,它确实依赖于实现,例如在python中也有一个LIFO队列,它更像堆栈.更糟糕的是,还有deques(双端队列),所以你真的需要有更多的上下文来理解这一点CS术语.