Сортировка элементов с использованием очереди в Java - PullRequest
Новая
       17

Сортировка элементов с использованием очереди в Java

1 голос
/ 31 марта 2020

Я пытаюсь отсортировать элементы (целые числа), присутствующие в очереди, используя другую очередь. Очередь не имеет отрицательных чисел или повторяющихся значений. Очередь должна быть отсортирована в порядке возрастания. (Голова -> хвост) пример ввода: 4 [7 3 9 5]

вывод: [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);
}

}

1 Ответ

1 голос
/ 01 апреля 2020

Поскольку у вас нет отрицательных чисел в очереди, я подумал сделать следующее:
1. вставить отрицательное число в первую очередь (метод «фиктивный»).
2. Найти минимальное число в первой очереди, пока вы не нажмете на пустышку.
3. Удалите пустышку.
4. Найдите в очереди минимальное значение, которое вы нашли на шаге 2, удалите его и вставьте во вторую очередь.
5. Выполняйте эти 4 шага, пока первая очередь не станет пустой.

Java код: 

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);
}
...