Stack & Queue — RPN Calculator

• Stack & Queue — RPN Calculator
  • Stack vs Queue — the core difference
    • 📚 Stack — LIFO
    • 🚛 Queue — FIFO
• How RPN uses both structures
• Step-through visualizer
• Live RPN calculator
• Quiz — why pop b before a?
• How this maps to AutoTriage
• Stack & Queue — complete!

from IPython.display import HTML, display display(HTML(“””

Stack & Queue — RPN Calculator

Data Structures 2 · Sprint 7 objective · demonstrated via AutoTriage capstone

XP Progress

★ 0 / 300 XP

1

Stack vs Queue — the core difference

Data Structure DS2 Objective

📚 Stack — LIFO

Last In, First Out. Like a stack of plates — you always take from the top. Push adds to top. Pop removes from top.

push(3) → [3]
push(5) → [3,5]
pop() → 5, stack=[3]

🚛 Queue — FIFO

First In, First Out. Like a line at a store — first person in is first out. Enqueue adds to back. Dequeue removes from front.

enqueue(3) → [3]
enqueue(5) → [3,5]
dequeue() → 3, queue=[5]

💡 In the RPN calculator: the input expression is processed like a queue (left to right). The operands are managed on a stack (push numbers, pop to compute).

2

How RPN uses both structures

Reverse Polish Notation puts operators after their operands. 3 4 + 2 * means (3 + 4) × 2 = 14.

The algorithm has two phases:

// Phase 1: tokenize input into a Queue (left to right) Queue<String> tokenQueue = new LinkedList<>(); for (String token : expression.split(" ")) { tokenQueue.enqueue(token); // FIFO — preserve left-to-right order } // Phase 2: evaluate using a Stack Stack<Double> operandStack = new Stack<>(); while (!tokenQueue.isEmpty()) { String token = tokenQueue.dequeue(); // pull next token if (isNumber(token)) { operandStack.push(Double.parseDouble(token)); // push operand } else { // operator: pop TWO operands, compute, push result double b = operandStack.pop(); // right operand (popped first) double a = operandStack.pop(); // left operand operandStack.push(compute(a, token, b)); } } // final answer sits alone on the stack return operandStack.pop();

3

Step-through visualizer

Expression: 3 4 + 2 *  → expected result: 14

Token queue (input — dequeued left to right)

Operand stack (top = right)

Press Next Step to begin

4

Live RPN calculator

+100 XP on first correct eval

Type any RPN expression and evaluate it. Separate tokens with spaces.

Try: 5 1 2 + 4 * + 3 -  (answer: 14)  ·  2 3 4 * +  (answer: 14)

?

Quiz — why pop b before a?

+100 XP

In the code above, when we hit an operator we do b = pop() then a = pop(). Why does order matter?

🔗

How this maps to AutoTriage

DS2 → Capstone

The same stack/queue thinking appears directly in the AutoTriage backend:

Queue pattern

ActivityRepository.findAllSince() returns events in insertion order — FIFO, oldest first. DigestGenerator processes them left to right just like the token queue.

Stack pattern

The VSCode extension uses a Set<String> to accumulate files (like pushing onto a stack), then drains it all at once when Generate is called — analogous to popping the final result.

This is the answer to "how do your DS2 objectives map to your project?" — point at these two classes and explain the analogy.

🏆

Stack & Queue — complete!

★ 0 / 300 XP  ·  You're ready to demo this to Mortensen.

”””))