The Language is JAVA

1) Implement MyArrayStack (constructor, push, pop, peek and isEmpty) MyLinkedStack (constructor, push, pop, peek and isEmpty) and MyLinkedaueue(constructor, enqueue, dequeue, peek and isEmpty), and write the following two program to test them. (5 points) 2) For stack testing, write a program to check if a string has matching 3) For stack testing, use it to "Evaluating.Expressions" using the algorithm 4) Animal Shelter: An animal shelter, which holds only dogs and cats, parenthesis such as "(0)", but not "(". (5 points) given below. (5 points) operates on a strictly."first in, first out" basis. People must adopt either the oldest" (based on arrival time) of all-animals at the shelter, or they can select whether they would prefer a dog.or a cat (and will receive the oldest animal-of that type). They cannot select which specific animal they would like. Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, degueueDog, and degueueCat. You may use the mylinkedlist data structure you created in previous homework. The Algorithm for Step 3:1 Phase 1: Scanning the expression The program scans the expression from left to right to extract operands, operators, and the parentheses.T 1.1.- Ifthe extracted item is an operand, push it to operandStackl 1.2.If the extracted item is a+or-operator, process all the operators at the top of and push the extracted operator to gperatorStack,T 1.3. If the extracted item is a or/operator, process the*or/operators at the top of gperatorStack and push the extracted operator to operatorStack, 1.4.-+ If the extracted item is a (symbol push it to operatorstass i 1.5. If the extracted item isa)symbol, repeatedly process the operators from the top of operatorStack until seeing the ( symbol on the stack. I Phase 2: Clearing the stack Repeatedly process the operators from the top of operatorStack until gperatorStack is empty. Bonus: 1) Add support for exponent~ for the step 3 abovel 2) Flip Bit to Win: You-have an integer and you can flip exactly one bit from a O toa 1. Write code to find the lengthof the longest sequence of 1 s you could create. EXAMPLE Input: 1775 (or: 11011101111)1 Output: 8 1) Implement MyArrayStack (constructor, push, pop, peek and isEmpty) MyLinkedStack (constructor, push, pop, peek and isEmpty) and MyLinkedaueue(constructor, enqueue, dequeue, peek and isEmpty), and write the following two program to test them. (5 points) 2) For stack testing, write a program to check if a string has matching 3) For stack testing, use it to "Evaluating.Expressions" using the algorithm 4) Animal Shelter: An animal shelter, which holds only dogs and cats, parenthesis such as "(0)", but not "(". (5 points) given below. (5 points) operates on a strictly."first in, first out" basis. People must adopt either the oldest" (based on arrival time) of all-animals at the shelter, or they can select whether they would prefer a dog.or a cat (and will receive the oldest animal-of that type). They cannot select which specific animal they would like. Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, degueueDog, and degueueCat. You may use the mylinkedlist data structure you created in previous homework. The Algorithm for Step 3:1 Phase 1: Scanning the expression The program scans the expression from left to right to extract operands, operators, and the parentheses.T 1.1.- Ifthe extracted item is an operand, push it to operandStackl 1.2.If the extracted item is a+or-operator, process all the operators at the top of and push the extracted operator to gperatorStack,T 1.3. If the extracted item is a or/operator, process the*or/operators at the top of gperatorStack and push the extracted operator to operatorStack, 1.4.-+ If the extracted item is a (symbol push it to operatorstass i 1.5. If the extracted item isa)symbol, repeatedly process the operators from the top of operatorStack until seeing the ( symbol on the stack. I Phase 2: Clearing the stack Repeatedly process the operators from the top of operatorStack until gperatorStack is empty. Bonus: 1) Add support for exponent~ for the step 3 abovel 2) Flip Bit to Win: You-have an integer and you can flip exactly one bit from a O toa 1. Write code to find the lengthof the longest sequence of 1 s you could create. EXAMPLE Input: 1775 (or: 11011101111)1 Output: 8