Реализация очереди

Очереди

В очередь данные добавляются в хвост очереди, а считываются из ее головы. Соответственно, у очереди два указателя, один из которых содержит адрес головы (для обращения к очереди с целью считывания), а другой указатель содержит адрес хвоста (для записи).

Очередь пуста, если оба указателя указывают на одно и то же место в памяти (причем оно на самом деле еще ничего не содержит).

После записи в хвост первого элемента, указатель хвоста изменяется и указывает на место позади последнего элемента, то есть на свободное место для записи, которое и называется хвостом очереди.

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

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

В случае, если достигнут конец области памяти, то указателю хвоста передается адрес начала области памяти, то есть очередь ползает как бы по кругу. Если же при этом хвост догонит голову, то есть если в очередь много элементов добавлено, но мало считано, то возникает необходимость выделить новую область памяти и поместить указатель на ее начало в хвост очереди, после чего передать адрес ее начала указателю хвоста. Тогда очередь вползет хвостом вперед в новую область памяти.

Голова очереди когда-нибудь достигнет этого указателя, он будет считан и это будет признаком того, что прежняя область памяти свободна. Тогда, если очередь в новой области памяти столкнется с проблемой переполнения, то есть опять хвост догонит голову, то она поползет в старую область памяти.

Таким образом, очередь по мере ее увеличения может разместиться в нескольких областях памяти и по мере освобождения какой-либо области памяти снова ее использовать. Для этого очередь характеризуется как парой указателей головы и хвоста, так и соответствующим количеством пар указателей начала и конца областей памяти.

Образуется область памяти, где хранятся подряд эти указатели. Таким образом, очередь характеризуется массивом указателей.