Objective: The goal of this assignment is to practice stacks and queues. Assignment: The first part of your assignment is to implement both a stack and a queue data structure. You may use either an array-based implementation or a reference-based list implementation (the one that is in the book). Your Stack class should implement the standard push(), pop(), and peek() methods, in addition to a constructor. Your Queue class should implement the standard enqueue(), dequeue(), and peek() methods, in addition to a constructor. Next, you will write two programs to test your Stack and Queue classes.

Queue Program: Expression Evaluator Write a program to convert an infix expression to a postfix expression. In class, we wrote a calculator that evaluated a postfix expression. In this program, there is no need to evaluate the result. You will just convert an expression (e.g., (5+2)/3 to 5 2 + 3 /). The algorithm to do the conversion is given below:

The problem can be solved using two stacks, named operandStack and operatorStack, for storing operands and operators, respectively. Operands and operators are pushed into the stacks before they are processed. When an operator is processed, it is popped from operatorStack and applied to the first two operands from operandStack (the two operands are popped from operandStack). The resultant value is pushed back into operandStack. The algorithm proceeds in two phases:

Phase 1: Scanning the expression The program scans the expression from left to right to extract operands, operators, and the parentheses (you might want to look at the RPN calculator example we did in class to see how to extract tokens from an expression with the .split() String method). If the extracted item is an operand, push it to operandStack. If the extracted item is a + or - operator, process all the operators at the top of operatorStack and push the extracted operator to operatorStack. If the extracted item is a * or / operator, process the * or / operators at the top of operatorStack and push the extracted operator to operatorStack. If the extracted item is a ( symbol, push it to operatorStack. If the extracted item is a ) symbol, repeatedly process the operators from the top of operatorStackuntil seeing the ( symbol on the stack. Phase 2: Clearing the stack Repeatedly process the operators from the top of operatorStackuntil operatorStack is empty.