Write a method called rearrange that accepts 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 queue. For example, if the queue stores [3, 5, 4, 17, 6, 83, 1, 84, 16, 37], your method should rearrange it to store [4, 6, 84, 16, 3, 5, 17, 83, 1, 37]. Notice that all of the evens appear at the front followed by the odds and that the relative order of the evens and odds is the same as in the original. Use one stack as auxiliary storage.

See explaination

Explanation:

import java.util.*;

public class qs {

public static void rearrange(Queue<Integer> q)

{

int n = q.size();

Stack<Integer> st = new Stack<Integer>();

Integer f;

for(int i = 0; i < n ; i++)

{

f = q.poll();

// Even elements are added back to the list

if(f%2==0)

q.add(f);

else

st.push(f);

}

// Odd elements are added to the list in reverse order

while(st.size()>0)

{

q.add(st.pop());

}

// Repeats the above process to correct the order of odd elements

for(int i = 0; i < n ; i++)

{

f = q.poll();

// Even elements are added back to the list

if(f%2==0)

q.add(f);

else

st.push(f);

}

//Order of Odd elements are reversed so as to match the actual order

while(st.size()>0)

{

q.add(st.pop());

}

}

public static void main(String[] args) {

int arr[] = {3, 5, 4, 17, 6, 83, 1, 84, 16, 37};

int n = arr.length;

Queue<Integer> q = new LinkedList<Integer>();

for(int i = 0;i<n;i++)

q.add(arr[i]);

System.out.print("\nOriginal Queue\n");

System.out.println(q.toString());

rearrange(q);

System.out.print("\nReordered Queue\n");

System.out.println(q.toString());

}

}