Какую структуру данных я должен использовать, чтобы отслеживать недавно использованные элементы? - PullRequest
2 голосов
/ 26 марта 2009

Мне нужно что-то вроде ограниченной очереди, куда я могу вставить только 10 элементов. Новый элемент должен переопределить последний вставленный элемент. Должно быть только n различных элементов

Кстати, я ищу предложения на Java.

Ответы [ 2 ]

5 голосов
/ 26 марта 2009

Это классическое приложение для структуры данных очереди. Стек размером 10 будет отслеживать элементы first 10, которые вы добавили в него, тогда как очередь размера 10 будет отслеживать 10 самых последних элементов. Если вы ищете список «недавних товаров», как это следует из заголовка вашего вопроса, тогда очередь - это путь.

edit: Вот пример для наглядности:

Допустим, вы хотите отслеживать последние 4 элемента и получите доступ к восьми элементам в следующем порядке:

F, O, R, T, Y, T, W, O

Вот как будут выглядеть ваши структуры данных с течением времени:

access  item      queue          stack
  1      F     [ F . . . ]    [ . . . F ]
  2      O     [ O F . . ]    [ . . O F ]
  3      R     [ R O F . ]    [ . R O F ]
  4      T     [ T R O F ]    [ T R O F ]
  5      Y     [ Y T R O ]    [ Y R O F ]
  6      T     [ T Y T R ]    [ T R O F ]
  7      W     [ W T Y T ]    [ W R O F ]
  8      O     [ O W T Y ]    [ O R O F ]

Удаление верхнего элемента из стека удаляет элемент, который был добавлен последним, а не самый старый элемент.

Удаление одного элемента из очереди удаляет самый старый элемент, поэтому ваша очередь автоматически будет содержать самые последние элементы.

edit: благодаря Adam Jaskiewicz , вот некоторая документация по реализации Java's Queue .

4 голосов
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...