Sorting Elements using Queue in Java

Question

I am trying to sort elements(Integers) present in queue, using another queue. Queue does not have negative numbers or duplicate values Queue must sorted in ascending order.(head -> tail) sample input:4 [7 3 9 5]

output: [3 5 7 9]

import java.util.*;

public class Source {
public static void main(String args[]) {
    Queue<Integer> queue = new LinkedList<Integer>();
    Scanner s = new Scanner(System.in);
    int n = s.nextInt();
    while (n-- > 0)
        queue.add(s.nextInt());
    sort(queue);
}

// Method to sort the queue
static void sort(Queue<Integer> queue) {
    Queue<Integer> queue2 = new LinkedList<Integer>();
    queue2.add(queue.remove());
    while(queue.size()!=0){
    int temp = queue.remove();
   queue2.add(temp);
    while(temp<queue2.peek()){
        queue2.add(queue2.remove());
    }
    }
    System.out.println(queue2);
}

}

Have you checked out this post? stackoverflow.com/questions/14397674/java-sorting-a-queue — Hamish Gibson
– Hamish Gibson, Commented Mar 31, 2020 at 20:42

NirF · Accepted Answer · 2020-03-31 21:25:23Z

Since you have no negative numbers in the queue I was thinking doing as follows:
1. insert a negative number to the first queue (the "dummy" technique).
2. Search for the minimum number in the first queue until you hit the dummy.
3. Remove the dummy.
4. Search in the queue for the minimum value that you found in step 2, remove it and insert it to the second queue.
5. Follow these 4 steps until the first queue is empty.

Java code:

static void sort(Queue<Integer> q1) {
    Queue<Integer> q2 = new Queue<Integer>();
    int min=Integer.MAX_VALUE;
    while (!q1.isEmpty())
    {
        q1.insert(-1);
        while(q1.head() != -1)
        {
            if (q1.head() < min)
            {
                min=q1.head();
            }
            q1.insert(q1.remove());

        }
        q1.remove(); //removing the -1
        while (q1.head() != min)
        {
            q1.insert(q1.remove());
        }
        min = Integer.MAX_VALUE;
        q2.insert(q1.remove()); //inserting the minimum to the second queue.
    }
    System.out.println(q2);
}

Collectives™ on Stack Overflow

Sorting Elements using Queue in Java

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related