Принципы работы с динамической очередью

Условно очередь можно представить в виде трубки с шариками.

Для создания очереди и работы с ней необходимо иметь как минимум два указателя:

1. на начало очереди (возьмём идентификатор BegQ);
2. на конец очереди (возьмём идентификатор EndQ).

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

· Создание очереди

1. Исходное состояние:

1. Выделение памяти под первый элемент очереди:

1. Установка указателей на созданный первый элемент:

• Добавление элемента очереди.

1. Исходное состояние:

1. Выделение памяти под новый элемент и занесение в него информации:

1. Установка связи между последним элементом очереди и новым, а также перемещение указателя " конец очереди" EndQ на новый элемент:

• Удаление элемента очереди.

1. Исходное состояние:

1. Извлечение информации из удаляемого элемента в переменную Val и установка на него вспомогательного указателя P:

1. Переустановка указателя начала очереди BegQ на следующий элемент, используя значение поля Link, которое хранится в первом элементе. После этого освобождается память начального элемента очереди, используя дополнительный указатель P: