Допустим, нам дан список букв B, F, A, G, и что они расположены друг над другом, и я хочу распечатать порядок, в котором они были расположены друг над другом. Например, если бы мне дали информацию, что :
А-Г / Ф-Б / А-Б / А-Ф / ГБ / Г-Ф
где символ - означает «находится поверх» (так что A находится поверх G, F находится поверх B, A находится поверх B...), тогда я хочу вывести A, G, F, B на основе на приведенных данных. Проблема в том, что этот список читается построчно, поэтому после чтения первой строки ожидаемый вывод будет A, G, пока не будут прочитаны другие строки и ожидаемый вывод не будет обновлен. Моим первым побуждением было использовать стек, но тогда мне потребовалось бы много операций pop и push, и это было бы проблемой, потому что лучшая структура данных позволяла бы мне переключаться местами между буквами или свободно перемещать объекты, а деревья кажутся лучшим вариантом. но как именно это будет реализовано?
Все еще не ясно, чего вы хотите, и я не вижу здесь никакой сортировки. И я хочу вывести A, G, F, B. Похоже, вы просто печатаете их в том порядке, в котором они были введены. Также неясно, как предполагается использовать информацию в том виде, в каком она предоставляется. Опубликуйте ожидаемый результат и операции для показанных данных.
Я бы использовал ориентированный граф. В JDK нет классов ориентированного графа, но есть много библиотек, которые его реализуют (перечислены здесь), лично я бы посмотрел на jgrapht или библиотеку Google Guava (не помню, есть ли ориентированный граф).
Вот как выглядит ориентированный граф для ваших данных:
Как только ваш ориентированный граф создан и вы убедитесь, что в нем нет циклов (например, вы не определили A-B, B-C, C-A, что создает цикл), тогда сортировка — это просто вопрос написания компаратора со следующей логикой:
Вы можете использовать пары для создания компаратора следующим образом:
Set<List<String>> pairs = Arrays.stream(order.split(" / "))
.map(p -> p.split("-"))
.map(Arrays::asList)
.collect(Collectors.toSet());
Comparator<String> compare = (a, b) ->
pairs.contains(Arrays.asList(a, b)) ? -1 :
pairs.contains(Arrays.asList(b, a)) ? 1 :
0;
Затем используйте это, чтобы отсортировать ввод в любой структуре, которую вы хотите.
Вы можете использовать двусвязный список, если хотите много манипулировать им.