Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Циклическая очередь

Циклическая очередь является важной структурой данных. Физически это массив, но его индекс используется особым способом. Рис. 2.1 иллюстрирует простой пример. На нем показан массив из 16 байт с символами, из которых одни добавлены в «конец», а другие -удалены из «начала». Обе позиция конца и начала перемещаются, и два указателя s и е все время на них указывают. На рис. (а) имеется 8 символов sid_east, а остаток буфера пуст. На рис. (Ь) все 16 символов заняты, а е указывает на конец буфера. На (с) первая буква s была удалена, а буква 1 в easily была вставлена. Заметьте, что указатель е теперь размещается слева от s. На рис. (d) две буквы id были удалены просто перемещением указателя s; сами символы все еще находятся в массиве, но они уже эффективно удалены из очереди. На рис. (е) два символа у_ были добавлены в очередь и указатель е переместился. На рис. (f) указатели показывают, что буфер кончается на teas, а начинается на tman. Добавление новых символов в циклическую очередь и перемещение указателей эквивалентно перемещению содержимого очереди. Итак, нет необходимости что-то двигать или перемещать.

Isidueast________|

т т

Isidueastmanueasil

t t

llidueastmanueasil

tt

s e

s e

es

(а)

(b)

(c)

llidueastmanueasil

t t

1 lyuueastmanyeasi |

tt

| lyuteastmartpeas i |

tt

е s

es

es

(d)

(e)

(f)

Рис. 2.1. Циклическая очередь.

Похожие материалы