13

A stack is referred to as a Last-In-First-Out (LIFO) and First-In-Last-Out (FILO) structure.

Is there any data structure that is LIFO but not FILO (or other direction) ? A counter example that proves "FILO doesn't always mean LIFO"

Raymond Chenon
  • 11,482
  • 15
  • 77
  • 110

1 Answers1

17

Maybe I'm a bit late, but there's a simple proof by contradiction.

Assume that there is a LIFO structure which is not FILO. That means that the element (let's designate it with letter A) which arrived first can be processed ("out") "not last", i.e. if some other elements (which arrived later than A) are present in the structure. There exists the last element B among those, and it's obvious that B≠A. But, according to the LIFO principle, it's B, not A, which must be processed "now" (as B is the last, so it must be processed first), so B gets "out" before A anyway. Element A gets processed only if no such B exists, i.e. only if no other elements remain. But it's FILO by definition. QED

In nearly the same way it can be shown that any FILO structure is LIFO.

P.S. The FIFO==LILO statement can also be proved analogously.

trolley813
  • 874
  • 9
  • 15
  • Thanks @trolley813 , can you give the name of such data structure . I was looking for this counter example. PS: you are not late. – Raymond Chenon Jan 28 '21 at 09:45
  • 5
    @RaymondChenon This was a proof that no such structure exists, i.e. any FILO structure is LIFO and vice versa. The same holds for FIFO-LILO. – trolley813 Jan 28 '21 at 18:08