Стивен Прата - Язык программирования C. Лекции и упражнения (6-е изд.) 2015

bool EnQueue(Item item, Queue * pq);

Наконец, удаление элемента может быть реализовано несколькими способами. Если элемент определен как структура или один из фундаментальных типов, функция может его возвращать. Аргументом функции могла бы быть переменная Queue либо указатель на нее. Таким образом, один из возможных прототипов выглядит так:

Item DeQueue(Queue q);

Однако следующий прототип является чуть более общим:

bool DeQueue(Item * pitem, Queue * pq);

Элемент, удаленный из очереди, помещается в место, на которое ссылается указатель pitem, а возвращаемое значение отражает, успешно ли выполнена операция. Единственным аргументом, который должен быть предоставлен функции опустошения очереди, является адрес очереди, что и демонстрирует приведенный далее прототип:

void EmptyTheQueue(Queue * pq);

Реализация представления данных интерфейса

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

746 Глава 17 удаление элемента из начала очереди заключается в копировании значения первого элемента в массиве (что просто) и последующем перемещении каждого элемента, оставшегося в массиве, на одну позицию в направлении его начала. Хотя эти действия легко программировать, они занимают много процессорного времени (рис. 17.6).

Рис. 17.6. Использование массива в качестве очереди

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

Рис. 1 7.7. Переопределение начального элемента

Расширенное представление данных 747

Более искусное решение проблемы теряемого пространства предполагает превращение очереди в кольцевую. Это означает, что конец массива должен быть соединен с его началом. То есть вообразите, что первый элемент массива следует непосредственно за последним элементом, поэтому при достижении конца массива вы начинаете добавлять элементы в начальные позиции, как если бы они были освобождены (рис. 17.8). Такой процесс можно сравнить с рисованием на бумажной ленте, склеенной в кольцо. Естественно, теперь придется выполнять дополнительные действия по обеспечению того, чтобы конец очереди не перекрывал ее начало.

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

Рис. 1 7.8. Кольцевая очередь

748 Глава 17

Чтобы проверить свои идеи, начнем с создания очереди целых чисел:

typedef int Item;

Связный список построен из узлов, поэтому давайте определим узел:

typedef struct node

{

Item item; struct node * next;

} Node;

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

typedef struct queue

{

Node * front; /* указатель на начало очереди */

Node * rear; /* указатель на конец очереди */

int items; /* количество элементов в очереди */

} Queue;

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

Теперь пора подумать о размере очереди. В случае связного списка размер очереди ограничен объемом доступной памяти, но часто имеет смысл применять очередь значительно меньшего размера. Например, очередь можно использовать для эмуляции самолетов, ожидающих приземления в аэропорту. Если количество ожидающих самолетов становится слишком большим, новые прибывающие самолеты могут направляться в другие аэропорты. Мы установим максимальный размер очереди равным 10. Определения и прототипы интерфейса очереди приведены в листинге 17.6. В нем от сутствует конкретное определение типа Item. Во время применения интерфейса в него будет помещено определение, соответствующее потребностям конкретной программы.