Programming: Queues

Given a Queue of Integers with the interface:

 public void enqueue(Integer i) // add to end public Integer dequeue() // remove from front public boolean isEmpty() // return true if empty

Write a method rearrange(Queue q) that takes a queue of integers as a parameter and 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, if a Queue contained

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

after call rearrange it would contain

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

You may use any internal data structures you chose.

Hint: I recommend even and odd queues.