русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Реализация очереди


Дата добавления: 2013-12-23; просмотров: 799; Нарушение авторских прав


Очереди

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

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

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

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


 

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

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



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

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

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


 



<== предыдущая лекция | следующая лекция ==>
Реализация стека | Хранение в бинарном дереве алфавитного списка


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.005 сек.