Question

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.

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. If not, PLEASE let me know before you rate, I’ll help you fix whatever issues. Thanks

//required method.
public static void rearrange(Queue q) {
        // creating two queues, one for storing odd values and another for
        // storing even values. assuming Queue class is defined. if Queue is an
        // interface, then replace 'new Queue()' with any child class of Queue
        // interface (like ArrayQueue, LinkedQueue etc, depends on your
        // implemnetation)
        Queue oddQueue = new Queue();
        Queue evenQueue = new Queue();
        // looping until q is empty
        while (!q.isEmpty()) {
                // removing from value from q
                int value = q.dequeue();
                // if the removed value is odd, adding to odd queue, else adding to
                // even queue
                if (value % 2 != 0) {
                        oddQueue.enqueue(value);
                } else {
                        evenQueue.enqueue(value);
                }
        }
        // now simply dequeuing each element from even queue, enqueuing to
        // original q
        while (!evenQueue.isEmpty()) {
                q.enqueue(evenQueue.dequeue());
        }
        // then dequeuing each element from odd queue, enqueuing to
        // original q
        while (!oddQueue.isEmpty()) {
                q.enqueue(oddQueue.dequeue());
        }
        // now all even values are arranged before odd values.
}