data-structures - FILO总是后进先出吗？

Question

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

是否有任何数据结构是 LIFO 但不是 FILO（或其他方向）？一个反例证明“FILO 并不总是意味着 LIFO”

Answer 1

也许我来晚了，但是有一个简单的矛盾证明。

假设有一个不是 FILO 的 LIFO 结构。这意味着最先到达的元素（我们用字母 A 表示）可以“不是最后”处理（“out”），即如果结构中存在其他一些元素（比 A 晚到达）。其中存在最后一个元素B，显然B≠A。但是，根据 LIFO 原则，必须“现在”处理的是 B，而不是 A（因为 B 是最后一个，所以必须先处理），所以无论如何 B 在 A 之前“出”。仅当不存在此类 B 时，才处理元素 A，即仅当没有其他元素存在时。但它的定义是 FILO。量子点

以几乎相同的方式可以证明任何 FILO 结构都是 LIFO。

PS FIFO==LILO 语句也可以类似地证明。