FILO是否总是LIFO？

Question

栈是一种先进后出（Last-In-First-Out，LIFO）和后进先出（First-In-Last-Out，FILO）结构。

是否存在既是LIFO又不是FILO（或者其他方向）的数据结构？有反例可以证明“FILO并不总是意味着LIFO”。

- Raymond Chenon

Answer 1

也许我有点晚了，但这里有一个简单的反证法证明。

假设存在一个不是FILO的LIFO结构。这意味着最早到达的元素（我们用字母A来代表）可以被处理（“out”）“不是最后一个”，即如果一些其他元素（比A晚到达）存在于结构中。其中必定存在最后一个元素B，并且很明显B≠A。但是根据LIFO原则，“现在”必须处理的是B而不是A（因为B是最后一个元素，所以它必须首先被处理），因此无论如何B都会在A之前出队列。只有当不存在这样的B时，也就是没有其他元素剩余时，元素A才会被处理，也就是说它符合FILO的定义。QED

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

备注：FIFO == LILO声明也可以类似地证明。

- trolley813

---

谢谢 @trolley813，你能给出这种数据结构的名称吗？我一直在寻找这个反例。 PS：你没有迟到。 - Raymond Chenon

这是证明不存在这样的结构，即任何FILO结构都是LIFO，反之亦然。对于FIFO-LILO也是如此。 - trolley813