Menu
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"
760
5. Time Complexity Analysis. The stack follows LIFO order for all operations, which means the top is always pointing at the top-most element.
Stacks are based on the LIFO principle, i.e., the element inserted at the last, is the first element to come out of the list. Queues are based on the FIFO principle, i.e., the element inserted at the first, is the first element to come out of the list.
Inventory management and/or accounting procedure whereby the earliest arriving goods of their kind (first in) are shipped after those that have arrived more recently (last out).
FIFO (first in, first out) FILO (first in, last out) LIFO (last in, first out) LILO (last in, last out)
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.
153
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
