Часто в программах надо использовать такие типы данных, размер и структура которых должны меняться в процессе работы. Динамические массивы здесь не выручают, поскольку заранее нельзя сказать, сколько памяти надо выделить - это выясняется только в процессе работы. Например, надо проанализировать текст и определить, сколько каких слов в нем встретилось, а также расставить их по алфавиту.
В таких случаях применяют данные особой структуры, которые представляют собой отдельные элементы, связанные с помощью ссылок. Каждый элемент (узел) состоит из двух областей памяти:поля данных и ссылок
Ссылки представляют собой адреса других узлов этого же типа, с которыми данный элемент логически связан. В языке Си для организации ссылок используются переменные-указатели.
Очередь — это информационная структура, в которой для добавления элементов доступен только один конец, называемый хвостом, а для удаления — другой, называемый головой. В англоязычной литературе для обозначения очередей довольно часто используется аббревиатура FIFO (first-in-first-out — первый вошёл — первым вышел).
Очередь разумнее всего моделировать, отобразив её на двунаправленный кольцевой список. В этом случае в заглавном звене будет присутствовать информация как об указателе на голову, так и на хвост очереди.
Выделим типовые операции над очередями:
- добавление элемента в очередь (помещение в хвост);
- удаление элемента из очереди (удаление из головы);
- проверка, пуста ли очередь;
- очистка очереди.
