堆栈被称为后进先出 (LIFO) 和先进后出 (FILO) 结构。
有没有数据结构是 LIFO 但不是 FILO (或其他方向)?一个反例证明“FILO并不总是意味着LIFO”
最佳答案
也许我有点晚了,但有一个简单的反证证明。
假设有一个不是 FILO 的 LIFO 结构。这意味着首先到达的元素(让我们用字母 A 指定它)可以被处理(“出”)“不最后”,即如果结构中存在一些其他元素(晚于 A 到达)。其中存在最后一个元素B,显然B≠A。但是,根据 LIFO 原则,必须“现在”处理的是 B,而不是 A(因为 B 是最后一个,因此必须首先处理),因此无论如何 B 会在 A 之前“退出”。仅当不存在这样的 B 时,即仅当没有其他元素存在时,才处理元素 A。但它的定义是 FILO。 QED
以几乎相同的方式可以证明任何 FILO 结构都是 LIFO。
附言FIFO==LILO 语句也可以类似地证明。
关于data-structures - FILO 总是 LIFO 吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61775669/