Очередь (структура данных).

Очередь – структура данных типа «список», позволяющая добавлять элементы лишь в конец списка, и извлекать их из его начала. Она функционирует по принципу FIFO (First In, First Out — «первым пришёл — первым вышел»), для которого характерно, что все элементы a1, a2, …, an-1, an, добавленные раньше элемента an+1, должны быть удалены прежде, чем будет удален элемент an+1. Также очередь может быть определена как частный случай односвязного списка, который обслуживает элементы в порядке их поступления. Как и в «живой» очереди, здесь первым будет обслужен тот, кто пришел первым.


Очередь

Очередь

Стандартный набор операций (часто у разных авторов он не идентичен), выполняемых над очередями, совпадает с тем, что используется при обработке стеков:

  • добавление элемента;
  • удаление элемента;
  • чтение первого элемента.

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

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

Реализация очереди с помощью массива.

Данный способ позволяет организовать и впоследствии обрабатывать очередь, имеющую фиксированный размер. Определим список операций, который будет использоваться как при реализации статической очереди, так и динамической:

  • Creation(Q) – создание очереди Q;
  • Full(Q) – проверка очереди Q на пустоту;
  • Add(Q) – добавление элемента в очередь Q (его значение задается из функции);
  • Delete(Q) – удаление элемента из очереди Q;
  • Top(Q) – вывод начального элемента очереди Q;
  • Size(Q) – размер очереди Q.

В программе каждая из этих операций предстанет в виде отдельной подпрограммы. Помимо того, потребуется описать массив данных data[N], по сути, являющийся хранилищем данных вместимостью N, а также указатель на конец очереди (на ту позицию, в которую будет добавлен очередной элемент) – last. Изначально last равен 0.

В функции main, сразу после запуска программы, создается переменная Q структурного типа Queue, адрес которой будет посылаться в функцию (в зависимости от выбора операции) как фактический параметр. Функция Creation создает очередь, обнуляя указатель на последний элемент. Далее выполняется оператор цикла do..while (цикл с постусловием), выход из которого осуществляется только в том случае, если пользователь ввел 0 в качестве номера команды. В остальных случаях вызывается подпрограмма соответствующая команде, либо выводиться сообщение о том, что команда не определена.

Из всех подпрограмм особого внимания заслуживает функция Delete. Удаление элемента из очереди осуществляется путем сдвига всех элементов в начало, т. е. значения элементов переписываются: в data[0] записывается значение элемента data[1], в data[1] – data[2] и т. д.; указатель конца смещается на позицию назад. Получается, что эта операция требует линейного времени O(n), где n – размер очереди, в то время как остальные операции выполняются за константное время. Данная проблема поддается решению.

Вместо «мигрирующей» очереди, наиболее приемлемо реализовать очередь на базе циклического массива. Здесь напрашивается аналогия с «живой» очередью: если в первом случае покупатели подходили к продавцу, то теперь продавец будет подходить к покупателям (конечно, такая тактика оказалась бы бесполезной, например, в супермаркетах и т. п.). В приведенной реализации очередь считалась заполненной тогда, когда указатель last находился над последней ячейкой, т. е. на расстоянии N элементов от начала.

В циклическом варианте расширяется интерпретация определения позиции last относительно начала очереди. Пусть на начало указывает переменная first. Представим массив в виде круга – замкнутой структуры. После последнего элемента идет первый, и поэтому можно говорить, что очередь заполнила весь массив, тогда когда ячейки с указателями last и first находятся радом, а именно за last следует first. Теперь, удаление элемента из очереди осуществляется простым смещением указателя first на одну позицию вправо (по часовой); чтобы добавить элемент нужно записать его значение в ячейку last массива data и сместить указатель last на одну позицию правее. Чтобы не выйти за границы массива воспользуемся следующей формулой:

(A mod N) + 1

Здесь A – один из указателей, N – размер массива, а mod – операция взятия остатка от деления.

В циклической реализации, как и прежде, очередь не содержит элементов тогда, когда first и last указывают на одну и ту же ячейку. Но в таком случае возникает одно небольшое отличие этой реализации от предшествующей. Рассмотрим случай заполнения очереди, основанной на базе массива, размер которого 5:

Элементы first last
1 1
1 1 2
1, 2 1 3
1, 2, 3 1 4
1, 2, 3, 4 1 5

В левом столбце записаны произвольные значения элементов, а в двух других значения указателей при соответствующем состоянии очереди. Необходимо заметить, что в массив размером 5 удалось поместить только 4 элемента. Все дело в том, что еще один элемент требует смещения указателя last на позицию 1. Тогда last=first. Но именно эта ситуация является необходимым и достаточным условием отсутствия в очереди элементов. Следовательно, мы не можем хранить в массиве больше N-1 элементов.

В следующей программе реализован интерфейс очереди, основанной на базе циклического массива:

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

Реализация очереди с помощью указателей.

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

Также понадобиться определить указатели на начало и конец очереди:

Следующее консольное приложение обслуживает очередь, каждый элемент которой – целое число. Весь процесс обуславливают все те же операции: Creation, Full, Add, Delete, Top, Size.

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


Похожие записи:

Оставить комментарий

Ваш e-mail не будет опубликован. Обязательные поля отмечены *