Я не думаю, что очередь - лучший способ сделать кеш. Вы хотите, чтобы ваш кеш был очень быстрым! И выполнение линейного сканирования вашей очереди - это не выход, если вы не хотите, чтобы ваш кеш был очень маленьким, или ваша память действительно ограничена.
Предполагая, что вам не нужен очень маленький кеш или медленный кеш, использование связанного списка с хэш-картой значения для узла в связанном списке - хороший способ пойти. Вы всегда можете выселить голову, и всякий раз, когда к элементу обращаются, вы можете удалить его и поместить в начало списка. Для доступа вы можете напрямую получить его или проверить, находится ли он в кеше в O (1). Выделение элемента также O (1), и поэтому обновляется список.
Например, посмотрите ссылку LinkedHashMap в java.
http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html
Поправьте меня, если я ошибаюсь, но это не позволяет хранить только 99 записей? Выражение (in == (out-1 + SIZE)% SIZE) говорит, что если он один раньше. Но он еще не написан, поэтому 100-е место никогда не записывается. – 2010-09-27 04:20:45
@ Jonathon - Это правильно, и, хотя это достаточно очевидно для экспертов, это нацелено на новичков, поэтому я изменил код, чтобы сделать его более явным. Спасибо за примечание! – 2010-10-09 16:07:52
@AdamDavis. Этот код неверен. Если вы наблюдаете за буфером, он не только оставляет «отверстие», но и «просканирует» назад через буфер. Это послужило источником вдохновения для кода, который я опубликовал здесь, поэтому я хотел поблагодарить вас за публикацию этого кода с этой целью. http://stackoverflow.com/questions/827691/how-do-you-implement-a-circular-buffer-in-c/13888143#13888143 – RocketRoy 2012-12-29 01:36:36