Очередью в программировании называется структура данных, где новый элемент всегда добавляется в конец массива, а удаляется (извлекается) всегда первый. FIFO ( First In, First Out - Первым прибыл, первым вышел) - сокращённое название очереди как алгоритма. Очередь имеет свои ограничения: 1. Максимальный размер очереди определяется изначально неким числом max_size. В течение существования объекта класса количество его элементов не может быть больше этого max_size. 2. Нельзя удалить элемент, если его нет. Поэтому перед удалением всегда надо проверять, очередь на наличие минимум одного элемента. 3. Допустим есть массив из "4" элементов. Извлечём элемент. Получим что слева есть пустое место, но при этом добавить элемент справа напрямую мы не можем. То есть при max_size=4, очередь может содержать только три элемента ( а после повторного извлечения вообще только два). Самым простым способом будет просто переместить после извлечения все элементы массива на одну ячейку влево. Причём это точно всегда будет работать. Но если у нас массив будет не из "4" элементов, а из 1 000 000, то от извлечения 50 000 элементов будет сильная потеря производительности, так как при каждый из 50 000 извлечений мы перемещаем примерно по 1 000 000 элементов массива. Рассмотрим теперь алгоритм получше. Представим нашу очередь в виде замкнутого круга. Тогда, немного поигравшись с индексами, можем обойтись без перестановок элементов. Как именно это выглядит? Представим очередь в магазин, в которой не очередь перемещается к продавцу ( дружно шагая всем составом), а продавец к очереди: то есть позиция начала очереди постоянно изменяясь стремится к концу очереди. В таком случае следить нужно будет не только за концом очереди, но и за её началом. Как организовать круговую работу очереди? Когда мы добавляем или извлекаем элементы, то очередь движется вправо. Слева же от начала очереди остаются ненужные ячейки массива, которые и нужно заполнять при вставке новыми элементами, если справа уже дошли до конца массива. Ниже приведена сложная реализация класса Queue с помощью шаблонов. Скачать исходники можно по ссылке ниже. http://it-solutions.ucoz.ru/load/it/code_in_cpp/class_queue/10-1-0-4
| 
