CODEWITHSUNDEEP
data-structuresstacklifo
Raymond Chenon
Raymond Chenon

Reputation: 12702

is FILO always LIFO?

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"

Upvotes: 18

Views: 17247

Answers (1)

trolley813
trolley813

Reputation: 932

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.

Upvotes: 23

Related Questions