Какой правильный термин для очереди FIFO фиксированного размера? - PullRequest
6 голосов
/ 28 мая 2009

Какое правильное имя для следующей структуры данных? Это:

  • очередь фиксированного размера
  • Новые элементы добавлены в начало
  • Всякий раз, когда очередь становится больше определенного размера, с конца удаляется несколько элементов

Ответы [ 5 ]

2 голосов
/ 28 мая 2009

«очередь FIFO фиксированного размера»

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

1 голос
/ 28 мая 2009

Я думаю, это может зависеть от фактической реализации этого. Практическим примером того, что вы описываете, является Круговой буфер или Кольцевой буфер, где самые старые данные перезаписываются новыми данными после заполнения буфера. Это был бы один из традиционных способов реализации такой структуры данных в чем-то вроде C.

РЕДАКТИРОВАТЬ: Хорошо, поэтому круговой буфер не совсем подходит. Как насчет очереди с конечным буфером или очереди с конечной емкостью ? Но на самом деле они не охватывают самоограничивающий аспект ...

Самоограничивающаяся очередь Bratt с конечной емкостью.

Авто-всплывающее окно ...

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

РЕДАКТИРОВАТЬ: Или, возможно, это Циклическая очередь . Статья описывает это как:

В этой статье описывается очередь, аналогичная System.Collections.Queue, за исключением того, что она имеет> фиксированный размер буфера. Это, конечно, означает, что буфер не может быть достаточно большим, чтобы> содержать все элементы, добавленные в очередь, и в этом случае самые старые элементы удаляются.

... что очень похоже на ваше. Красиво и лаконично.

1 голос
/ 28 мая 2009
0 голосов
/ 29 мая 2009

Во встроенных системах это почти повсеместно называется круговыми буферами.

0 голосов
/ 28 мая 2009

В аппаратном обеспечении подобная структура называется сдвиговым регистром .

...