Какую структуру данных я должен использовать для этой конкретной ситуации?

Question

Это не проблема homeowrk

Я проектирование стоянки и позволяет сказать, что у меня есть переменная used, которая подсчитывает, сколько пятен используют и Hashmap который отображает номера автомобиля VIN номерам парковки.

Я начинаю с used = 0

Когда Cara прибывает:

used = used + 1; 
h.put("CarA" , used) //CarA-> 1 

Когда Carb прибывает:

used = used + 1; 
h.put("CarB" , used) //CarB-> 2 

Когда Carc прибывает:

used = used + 1; 
h.put("CarC" , used) //CarC-> 3 

В Thi s used содержит 3

Теперь я удаляю CarA.

used = used - 1 // used contains 2 

Вопрос: Но теперь мне нужно следить за тем, что слот 1 пуст, и я не должен забывать использовать его снова для любого другого автомобиля. Как мне отслеживать этот факт?

Мое решение (которое я хотел бы улучшить и получить критику) заключается в том, что я могу хранить такие количества (освобождающихся при удалении автомобилей) в очереди и по мере того, как машины приходят, если очередь не пуста Я должен просто использовать слоты в очереди, пока очередь не будет пустой.

Answer 1

Ваше решение в порядке, за исключением того, что не требуется очередь: любая структура данных с O(1) вставка и O(1) удаление сделаю. Например, использование стека вместо очереди даст вам такую ​​же производительность.

Эта идея похожа на использование списков look-aside для буферов памяти: вместо того, чтобы выделять новый ресурс (в вашем случае, новое место для парковки), сначала проверьте коллекцию освобожденных ресурсов, чтобы увидеть, есть ли элемент доступный для повторного использования. Дополнительным преимуществом такого подхода является то, что у вас есть «высокий водяной знак», доступный вам всегда, рассказывая, сколько автомобилей у вас было на пике.

Answer 2

Бесплатный список - это структура данных, используемая в схеме распределения динамической памяти. Он работает путем соединения нераспределенных областей памяти вместе в связанном списке, используя первое слово каждой нераспределенной области в качестве указателя на следующий. Он наиболее подходит для выделения из пула памяти, где все объекты имеют одинаковый размер.

Бесплатные списки делают операции выделения и освобождения очень простыми. Чтобы освободить регион, можно просто связать его со свободным списком. Чтобы выделить регион, вы просто удалили бы одну область из конца бесплатного списка и использовали бы ее. Если регионы имеют переменный размер, возможно, придется искать область с достаточно большим размером, что может быть дорогостоящим.

Источник: http://www.wisegeek.com/what-is-a-free-list.htm

Полезная ссылка: http://docs.oracle.com/cd/B10500_01/rac.920/a96598/freelist.htm

Answer 3

Вы можете создать очереди/список пустых слотов, но это может быть более инженерии.Если вы знаете все пробелы в диапазоне от 0 до n, вы просто просматриваете карту до тех пор, пока она не вернет значение null для пробела.

Альтернатива - это сохранение двух карт, пустых пространств и пробелов. Ваш код будет только перемещать значения от одного к другому. Чтобы получить доступное пространство из доступной карты, получите Iterator и получите следующий() элемент.

Но опять же, над инженерной. Самое простое решение состоит в том, что карта является единственной точкой истины для автомобилей в пространствах. Вы знаете, что пространство доступно, потому что карта возвращает значение null, когда вы проверяете содержимое пробела.

Вызов map.size() покажет вам, сколько пробелов используется. Если это равно вашим общим доступным пространствам, вы знаете, что партия заполнена.