Answer:
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());
}
}
