Write a method rearrange that takes a Queue of integers as a parameter and that rearranges the order of the values so that all of the even values appear before the odd values and that otherwise preserves the original order of the list. For example, suppose a Queue called q stores this sequence of values:

front [3, 5, 4, 17, 6, 83, 1, 84, 16, 37] back

Then the following call:

rearrange(q);

should rearrange the order so that the queue stores the following sequence of values:

front [4, 6, 84, 16, 3, 5, 17, 83, 1, 37] back

Notice that all of the evens appear at the front of the queue followed by the odds and that the order of the evens is the same as in the original list and the order of the odds is the same as in the original list.

You are to use one stack as auxiliary storage to solve this problem.You may not use any other auxiliary data structures to solve this problem, although you can have as many simple variables as you like You also may not solve the problem recursively.

In writing your method, assume that you are using the Stack and Queue interfaces and the ArrayStack and LinkedQueue implementations discussed in lecture. As a result, values will be stored as Integer objects, not ints.

If you are running short of time, you can receive 15 points for a solution that puts all of the evens before the odds without preserving the original order of the evens and the odds. Your method should take a single parameter: the queue to rearrange.

Write your solution to rearrange below.