LIFO

A LIFO in computer science is a data structure in which objects added last are removed first.

For example, if a, b, c were added to a stack in order, c would be removed first, then b, then a.

Synonym for stack. Compare: FIFO and Queue.

To add an element to a LIFO is to push it; to remove an element is to pop it. So, in the above example, a, b, and c was pushed onto the stack, and then c, b, and a were popped off of it.

Some algorithms really benefit from a stack data structure. Classic examples include parsing and evaluating postfix (and converting infix to postfix).

Example:

Postfix notation for expressions lists operands first, then operators. For example, 4 5 - is the same as 4 - 5. The advantage of postfix notattion is that parenthesis are not needed because the order of elements is the same as the order of operations.

A postfix evaluator using a LIFO reads in data one element at a time. If the element is a number, it is pushed onto the stack. If it is an operator, the top two elements are popped off the stack, the operator is applied, and the result is pushed onto the stack. At the end of input, pop the top element off the stack to get the final result. Example: To evaluate (2 + 3) * (4 + 5), first convert it to postfix: 2 3 + 4 5 + *. Then:

1. push 2
2. push 3
3. pop 2 and 3.
4. push 5 (= 2 + 3)
5. push 4
6. push 5
7. pop 4 and 5
8. push 9 (= 4 + 5)
9. pop 9
10. pop 5
11. push 45 (= 9 * 5)
12. pop 45 to get the final result.