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。

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