堆栈还是不堆栈？

Question

假设我有一个类似于Stack的数据结构，但除了通常的Push/Pop之外，它还具有PushAt/PopAt等函数，这两个函数都接受一个整数作为输入，并在数据结构中的该特定位置添加/返回该项。

现在Stack应该是后进先出的。这个数据结构是否符合"Stack“的要求？

Answer 1

在HP RPN计算器和Postscript/PDF中，存在push和pop以外的其他运算符：

用于排列栈顶和下一个元素的

• swap或exch，作为swap

的扩展的

• roll

它们的主要数据结构仍然被认为是一个堆栈。

pushAt和popAt只能使用pop/push和roll编写。因此您的数据结构仍然可以命名为stack。

Answer 2

从技术上讲不是。后进先出的意思是(如你所知)后进先出。如果最后一个进入的元素不是第一个出来的，那么它就不满足堆栈的“语义接口”(或契约)。

但是，由于您似乎只是添加了额外的方法，而不是修改现有的方法，如果您的数据结构像堆栈一样使用，那么您的数据结构可以与堆栈互换使用，即pushAt()和popAt()永远不会被调用(例如，因为它们是通过将其作为Stack传递给函数来“隐藏”的)。

因此，从这个意义上讲，您的版本是一个堆栈，就像Java中的list是一个堆栈一样。它可以作为一个使用，但它也可以做其他事情。

Answer 3

它不是一个堆栈，因为它不是后进先出的，你可以完全控制项目的get/set位置，它只是一个普通的列表imho。