Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Топ:
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Интересное:
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2021-04-18 | 90 |
5.00
из
|
Заказать работу |
|
|
Ссылочная реализация очереди принципиально не отличается от ссылочной реализации стека, однако необходимость выполнять вставку и удаление на разных концах несколько усложняют детали. Во-первых, нужно хранить два дополнительных указателя — на хвост и голову очереди (обозначим их head и tail, как и в случае непрерывной реализации на массиве). Во-вторых, каждый элемент содержит указатель на следующий добавленный в очередь элемент, а не на предыдущий, как в стеке. Самый последний элемент очереди еще не имеет следующего элемента, поэтому содержит пустой указатель. Особенности ссылочной реализации очереди показаны на рисунке 2.5.
Рис.2.5. Представление очереди при помощи связного списка
Структура элемента очереди совпадает со структурой элементов стека с точностью до обозначений:
struct item //структура каждого элемента очереди
{ type_of_data data; // данные
item *next; // указатель на следующий элемент
};
Полное определение структуры queue приводить не будем, поскольку оно аналогично приведенной выше непрерывной реализации очереди (отсутствует только массив data). Можно самостоятельно определить структуру (или класс) очереди на основе шаблонов.
Интерес представляют операции добавления и удаления элементов, поскольку они выполняются немного иначе, чем аналогичные операции со стеком.
При добавлении элемента в хвост очереди достаточно (рис. 2.6):
· захватить под него память, заполнить информационную часть данными, указателю присвоить пустое значение;
· заполнить указующую часть элемента, бывшего последним (хвостом) в очереди — он теперь будет предпоследним и должен указывать на новый элемент;
· присвоить указателю на хвост указатель на новый элемент — он теперь будет хвостом очереди.
|
Рис.2.6. Добавление элемента в очередь
В соответствии с данным алгоритмом функция добавления имеет вид:
void queue::enqueue (type_of_data x)
{ item *i=new item; i->data=x; i->next=NULL; //элемент создан
if (isnull())//добавление первого элемента в пустую очередь
{ head=tail=i;
}
else // добавление в непустую очередь
{ tail->next=i; //последний элемент стал предпоследним
tail=i; // обновили указатель на хвост
}
}
Удаление из головы очереди также выполняется просто — достаточно изменить указатель на голову и освободить память, которую занимал элемент, воспользовавшись буферной переменной (рис.2.7).
Рис.2.7.Удаление (извлечение) элемента из очереди
void queue::dequeue ()
{ if (isnull()) { cerr << "Очередь пуста"; exit(1); }
item *i=head->next;//запомнили указатель на второй элемент
delete head; head=i;//удалили голову и изменили указатель
}
Полную очистку всей очереди можно реализовать, например, так:
void queue::makenull()
{ while (!isnull()) dequeue(); // удаляем элементы по порядку
}
|
|
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!