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:

- push 2
- push 3
- pop 2 and 3.
- push 5 (= 2 + 3)
- push 4
- push 5
- pop 4 and 5
- push 9 (= 4 + 5)
- pop 9
- pop 5
- push 45 (= 9 * 5)
- pop 45 to get the final result.