data-structures - FILO 总是 LIFO 吗？

Question

堆栈被称为后进先出 (LIFO) 和先进后出 (FILO) 结构。

有没有数据结构是 LIFO 但不是 FILO (或其他方向)？一个反例证明“FILO并不总是意味着LIFO”

Answer 1

也许我有点晚了，但有一个简单的反证证明。
假设有一个不是 FILO 的 LIFO 结构。这意味着首先到达的元素(让我们用字母 A 指定它)可以被处理(“出”)“不最后”，即如果结构中存在一些其他元素(晚于 A 到达)。其中存在最后一个元素B，显然B≠A。但是，根据 LIFO 原则，必须“现在”处理的是 B，而不是 A(因为 B 是最后一个，因此必须首先处理)，因此无论如何 B 会在 A 之前“退出”。仅当不存在这样的 B 时，即仅当没有其他元素存在时，才处理元素 A。但它的定义是 FILO。 QED
以几乎相同的方式可以证明任何 FILO 结构都是 LIFO。
附言FIFO==LILO 语句也可以类似地证明。