data structures – is FILO always LIFO?

data structures – is FILO always LIFO?

Maybe Im a bit late, but theres a simple proof by contradiction.

Assume that there is a LIFO structure which is not FILO. That means that the element (lets 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 its obvious that B≠A. But, according to the LIFO principle, its 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 its 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.

data structures – is FILO always LIFO?

Leave a Reply

Your email address will not be published.