Kann man eine Queue sortieren?

3 Antworten

GreenFond
03.10.2020, 00:42

Ja, wenn du keine Laufzeit/Speicherbeschränkung hast, kann man das relativ einfach mit einer Hilfsliste machen. In Place geht es auch dann ungefähr so :

  1. Pop two elements from the queue.
  2. Compare them.
  3. Push the lesser one in the queue.
  4. Pop another element.
  5. Keep repeating from step no. 2.
  6. After n-1 comparisons, you will get the largest element in the queue.
  7. Push it and repeat the above n-1 times. At each iteration, you need to make one less comparison as the last element is already the maximum.
321QWERTZ123
03.10.2020, 01:37

Man könnte eine PriorityQueue nutzen:

public static <T extends Comparable<T>> 
        Queue<T> sortQueue(Queue<T> queue) {
    return new PriorityQueue<T>(queue);
}

Ansonsten kommen auch Streams in Frage (diese Lösung ist aber ineffizienter):

public static <T extends Comparable<T>> 
        Queue<T> sortQueue(Queue<T> queue) {
    return queue.stream()
            .sorted()
            .collect(Collectors.toCollection(ArrayDeque::new));
}

Die Objekte in der Queue müssen in beiden Fällen natürlich Comparable sein.

Test:

var q = new ArrayDeque<>(Arrays.asList(5, 2, 9, 4, 6, 1, 7, 3, 8));

System.out.println("### PriorityQueue ###");
printQueue(q);
printQueue(sortQueue(q));

System.out.println("\n### Streams ###");
printQueue(q);
printQueue(sortQueueWithStreams(q));

Ausgabe:

### PriorityQueue ###
[5, 2, 9, 4, 6, 1, 7, 3, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

### Streams ###
[5, 2, 9, 4, 6, 1, 7, 3, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9]