📚 Lesson: Stack vs Queue Calculator

Introduction

Stacks and Queues are two fundamental data structures that have different methods of adding and removing elements. In this lesson, we will compare Stacks and Queues and explore how they can be used to implement a calculator.

📝 What is a Stack?

A stack is a LIFO (Last In, First Out) data structure.
Elements are added and removed from the same end, called the top.

Stack Operations:

  • push(item): Add an item to the top of the stack.
  • pop(): Remove an item from the top of the stack.
  • peek(): View the item at the top without removing it.
  • isEmpty(): Check if the stack is empty.

Example:

If we push 1, 2, and 3 into the stack in this order, the stack will look like this:

📝 What is a Queue?

A queue is a FIFO (First In, First Out) data structure.
Elements are added at the rear and removed from the front.

Queue Operations:

  • enqueue(item): Add an item to the rear of the queue.
  • dequeue(): Remove an item from the front of the queue.
  • peek(): View the item at the front without removing it.
  • isEmpty(): Check if the queue is empty.

Example:

If we enqueue 1, 2, and 3 in this order, the queue will look like this:

📌 How Can We Use Stacks and Queues for a Calculator?

Using a Stack in a Calculator:

Stacks are ideal for evaluating mathematical expressions, particularly those in postfix notation (Reverse Polish Notation), where operators follow operands.

Steps to Evaluate Postfix Expression using Stack:

  1. Read the expression from left to right.
  2. If an operand (number) is encountered, push it onto the stack.
  3. If an operator is encountered, pop two operands from the stack, apply the operator, and push the result back onto the stack.
  4. Continue this process until the end of the expression.
  5. The final result will be the only value left in the stack.

Example: 5 3 + 4 *

  1. Push 5 → Stack: [5]
  2. Push 3 → Stack: [5, 3]
  3. Encounter +: Pop 3 and 5, calculate 5 + 3 = 8, push 8 → Stack: [8]
  4. Push 4 → Stack: [8, 4]
  5. Encounter *: Pop 4 and 8, calculate 8 * 4 = 32, push 32 → Stack: [32]
  6. Final result: 32

Using a Queue in a Calculator:

Queues are less commonly used for direct arithmetic calculations but can be useful in simulating processes like order of operations or handling multiple tasks.

For instance, a queue could be used in a multi-step calculator where tasks (like addition, subtraction, etc.) are added to the queue, and the system processes them in the order they were received.

💡 Example: Using a Stack for Infix to Postfix Conversion

The following steps can be used to convert an infix expression (like 3 + 5 * 2) to postfix notation using a stack:

  1. Initialize an empty stack.
  2. Process the infix expression from left to right.
  3. If a number is encountered, add it to the output expression.
  4. If an operator is encountered, pop operators from the stack and add them to the output expression until an operator with lower precedence is found.
  5. Push the current operator onto the stack.
  6. At the end of the expression, pop any remaining operators in the stack and add them to the output.

For example:

  • Infix: 3 + 5 * 2
  • Postfix: 3 5 2 * +

Java Code for Postfix Evaluation using Stack

```java import java.util.Stack;

public class PostfixCalculator {

public static int evaluatePostfix(String expression) {
    Stack<Integer> stack = new Stack<>();
    String[] tokens = expression.split(" ");

    for (String token : tokens) {
        if (token.matches("\\d+")) {
            stack.push(Integer.parseInt(token));
        } else {
            int num2 = stack.pop();
            int num1 = stack.pop();
            int result = 0;

            switch (token) {
                case "+":
                    result = num1 + num2;
                    break;
                case "-":
                    result = num1 - num2;
                    break;
                case "*":
                    result = num1 * num2;
                    break;
                case "/":
                    result = num1 / num2;
                    break;
            }
            stack.push(result);
        }
    }
    return stack.pop();  // Final result
}

public static void main(String[] args) {
    String expr = "3 5 2 * +";
    System.out.println("Postfix Evaluation: " + evaluatePostfix(expr));  // Output: 13
} }

Example: Using a Queue for Order of Operations Simulation

A queue can simulate the process of handling different operations in a calculator where operations are processed in the order they were added. For instance:

  • Enqueue tasks like 3 + 5, 2 - 1, etc.
  • Dequeue and process each task in order.
  • The queue ensures that the operations are executed in the correct sequence.

Java Code for Queue Simulation

```java import java.util.LinkedList; import java.util.Queue;

public class CalculatorQueue { public static void main(String[] args) { // Create a queue to store operations Queue operations = new LinkedList<>();

    // Enqueue tasks
    operations.add("3 + 5");
    operations.add("2 - 1");
    
    // Process tasks in order
    while (!operations.isEmpty()) {
        String operation = operations.poll(); // Dequeue
        System.out.println("Processing: " + operation);
        // In a real calculator, here you'd process the operation
    }
} }