Предыдущий раздел

Очередь

Иначе говоря, двунаправленный список.

Программирование этого способа организации данных, при подготовке профессиональных программистов, является типичным упражнением и примером применения указателей и динамической памяти. Для математиков организация очереди, может быть, не так полезна, но традиция – это традиция! Детально разобрать описываемые ниже программные решения очень полезно с учебной точки зрения.

Представление об очереди можно получить, рассматривая последовательность тем этого пособия, которое вы сейчас читаете. Обратите внимание, что каждый раздел имеет собственное содержимое (т.е. то, что он содержит существенного для объяснения темы), а в начале его есть ссылка на предыдущий раздел и в конце – на следующий раздел. Только первый раздел, естественно, не имеет ссылки на предыдущий, а последний не имеет ссылки на следующий раздел. Благодаря такому способу организации последовательности элементов очереди между ними, ничего не изменяя в их содержимом, легко вставить новый элемент (что я сейчас и делаю при написании раздела "Очередь"). И так же легко удалить элемент из очереди, связав оставшиеся обрывки в цельную очередь.

А то, что вы видите на левой панели, очередью не является. Это просто массив из названий разделов и ссылок на них.

Еще одно типичное свойство очереди – возможность перемещения вдоль нее. Из элементов очереди всегда выделяется один, называемый текущим, – тот, с содержимым которого мы сейчас работаем. Мы перемещаемся вдоль очереди, прекращая работу с данным текущим элементом и делая текущим другой элемент. Имеющиеся у элементов очереди ссылки на ближайших соседей позволяют сделать шаг (или несколько шагов) в направлении к началу (голове) или к концу (хвосту) очереди. Кроме того, всегда известны первый и последний элементы очереди, к которым можно перейти непосредственно.

И вот, если для ваших данных характерны указанные операции, из них и следует строить очередь. Например, так можно обрабатывать текстовый файл:

В текстовом редакторе
С точки зрения очереди
Строка текста Содержимое элемента
Строка, на которой стоит курсор Содержимое текущего элемента
Перемещение курсора по строке, редактирование строки Обработка содержимого текущего элемента
Перемещение курсора на 1 строку вверх или вниз Переход к предыдущему или следующему элементу
Перемещение по тексту на 1 страницу вверх или вниз Перемещение на несколько элементов очереди в соответствующем направлении
Вставка или удаление строки Вставка или удаление элемента
Разбиение строки на две (нажатием <Enter>) Изменение (укорочение) содержимого текущего элемента и вставка после него нового элемента
Слияние двух строк Изменение содержимого текущего элемента (добавление содержимого следующего), после чего удаление следующего элемента
Переход к первой или последней строке Переход к первому или последнему элементу
И т.д.
И т.д.

Выводы сделаем в несколько формализованном виде.

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

Головной (первый) элемент очереди - тот, который не имеет предыдущего элемента. В непустой очереди существует ровно один такой элемент.

Хвостовой (последний) элемент очереди - тот, который не имеет последующего элемента. В непустой очереди существует ровно один такой элемент.

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

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

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

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

  Задача. Написать модуль, реализующий указанные свойства и операции.

Решение можно получить уже сейчас. Имейте только в виду, что не все функции и процедуры модуля прошли отладку. Так что можете приступать к работе (по отладке).

Но полезнее было бы внимательно почитать далее. Это даст вам лучшее представление о том, как работает модуль и как вам работать с очередью.

Продолжение следует

Следующий раздел