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

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

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