Абсолютно иной подход к реализации очередей заключается в использовании двусвязных списков. Для хранения указателей на начало и конец списка можно
использовать метки. Новые элементы добавляются перед меткой конца очереди,
а удаляются после метки начала очереди. На рис. 3.7 показан двусвязный список,
используемый в качестве очереди.
Добавлять и удалять элементы из двусвязного списка очень просто, поэтому
вам не нужно использовать сложные алгоритмы для изменения размеров. Пре-
имущество этого метода также в том, что он интуитивно понятнее по сравнению Рис. 3.7. Очередь на основе связанного списка
с циклической очередью на основе массива. Недостатком данного способа явля-
ется то, что требуется дополнительная память для указателей связанного списка
NextCell и PrevCell. Это делает очереди на основе связанных списков менее
эффективными, чем циклические очереди.
Программа LinkedQ работает с очередью при помощи двусвязного списка. Вве-
дите строку и щелкните по кнопке Enter, чтобы добавить новый элемент в конец
очереди. Щелкните по кнопке Leave для удаления из очереди первого элемента.
Главная
Каталог файлов
