Домашние задания / школьные проекты всегда сложны, добавляя тонкие вещи к требованиям, которые могут заставить чей-то мозг растаять. Есть ли у вас какие-либо требования включать пробелы в очередь?
Лично я бы не стал этого делать, если бы не было явного требования: кажется, что проще представить ваши машины как пары Car, Space (вы можете определить пару как структуру, предполагая, что вам разрешено использовать структуры), где пространство является числовое значение, представляющее пространство в направлении следующего автомобиля в транспортном средстве. Затем, чтобы сжать, вам нужно только просмотреть элементы списка: когда вы найдете тот, который имеет Space > 0, выполните Space--; return;, и все другие автомобили будут уже «продвинутыми», так как они сохраняют пространство с теми, что в перед ними. Для вывода убедитесь, что выбрасываете Space точек для каждого автомобиля после (если стоп-сигнал справа, а автомобили идут слева) или перед (стоп-сигнал слева и автомобили, идущие справа) самого автомобиля, и там вы идете. Также обратите внимание, что Space первого автомобиля представляет расстояние до самого стоп-сигнала, так как до него нет автомобиля.
Если вы добавите в структуру указатель на следующий вагон (и нулевой указатель на последний вагон), у вас уже есть связанный список: сохраните «глобальную» переменную, которая указывает на первый вагон (или ноль для пустая очередь). Поскольку Java напрямую не поддерживает указатели, превратите структуру в класс и используйте «ссылки на объекты» (которые аналогичны указателям для всех целей, кроме арифметики указателей на C'ish), и все: только один класс, встроенный с нуля. Единственное, что вам нужно затронуть в библиотеках Java, - это стандартный ввод-вывод и, возможно, небольшая манипуляция со строками, которая является неотъемлемой потребностью, возникающей из-за необходимости принимать ввод и производить вывод (некоторые колледжи имеют свой собственный ввод-вывод для конкретного курса библиотеки, но это не имеет большого значения здесь). Чтобы перебрать очередь, вы должны сделать что-то вроде этого (если предположить, что класс называется «Node», что является довольно общим, и очевидные имена для полей):
for(Node pos = First; pos != null; pos = pos.Next) {
/* Do your stuff here, knowing that "pos" points to the "current" item on each iteration. */
}
Чтобы добавить новые узлы, вам, вероятно, придется пройти через очередь, чтобы выяснить, на каком расстоянии от последнего появится новый автомобиль; когда вы делаете это, сохраняйте ссылку с последнего узла и делайте его "следующую" контрольную точку с новым узлом:
Node last = First;
int distance = 0;
for(Node pos = First; pos != null; pos=pos.Next) {
distance += pos.Space;
last = pos;
}
last.Next = new Node(the_letter_for_this_car, MaxDistance-distance, null);
Конечно, настройте конструктор на то, что у вас есть.
Учитывая, что это проект колледжа, давайте посмотрим на некоторые детали: компактное время процесса становится O(n), а его использование памяти - O(0) (самому процессу не нужны никакие "локальные" переменные, другие чем, может быть, указатель для обхода коллекции, которая не зависит от длины очереди.) Кроме того, использование памяти для самой очереди гарантированно будет меньше или равно тому, что было бы для представления пробелов в качестве элементов (он получает только чтобы быть равным в худшем случае, когда достаточно много автомобилей застряли на красный свет). Поэтому, если в требования не входит что-то несовместимое с этим подходом, я бы ожидал, что именно этого хотят ваши учителя: это аргументировано, эффективно и соответствует тому, о чем вас просили.
Надеюсь, это поможет.