Which data structure is most appropriate for evaluating a postfix expression?

Concept: Postfix (Reverse Polish) notation places each operator immediately after its operands, so the whole expression can be evaluated in a single left-to-right pass without needing parentheses or precedence rules. Operands are held until they are needed; whenever an operator is read, it combines exactly the two most recently pushed values that are still unconsumed and replaces them with the result — a Last-In-First-Out (LIFO) access pattern that is exactly what a stack's push and pop operations provide.

Application: Trace the expression 5 6 2 + * token by token:

1. Push 5. Stack: [5].

2. Push 6. Stack: [5, 6].

3. Push 2. Stack: [5, 6, 2].

4. Read '+'. Pop 2, then pop 6, compute 6 + 2 = 8, and push the result. Stack: [5, 8].

5. Read '*'. Pop 8, then pop 5, compute 5 × 8 = 40, and push the result. Stack: [40].

6. No tokens remain; the single value left on the stack, 40, is the value of the expression.

Cross-check: A queue removes elements in First-In-First-Out order, so applying an operator would pull the two oldest enqueued values rather than the two most recently produced ones — the wrong pairing for a notation that binds each operator to the operands immediately preceding it. A priority queue reorders elements by an assigned priority rather than by recency, so it likewise cannot preserve the operand order the expression encodes. An AVL tree keeps elements sorted for fast search, which has no relation to the left-to-right operand/operator sequence a postfix expression defines. Re-evaluating the same expression by fully parenthesizing it — 5 6 2 + * → 5 × (6 + 2) = 5 × 8 = 40 — confirms the stack-based left-to-right result.