Непейвода Н.Н. Программирование. Раздел 3

Непейвода Н.Н. Программирование. Страница 355

В приводимой программе используется следующий подход к реализации очередей. Хранилище элементов представляется массивом Containerобъ­ема MaxSize. Для указания компоненты массива, в которой при очередном обращении к процедуре PutEIQueueразместится элемент очереди, исполь­зуется переменнаяиндекс IB. Элемент, который должен быть извлечен из Container'а при обращении к функции GetEIQueue, указывается перемен­нойиндексом IE. Три структуры данных: Container, IBи IE — являются основой реализационного представления очереди.

Все хранимые элементы очереди размещаются между компонентами, ин­дексируемыми IBи IE(см. рис. 8.9а). Запись элемента влечет увеличение

Рис. 8.9. Представление очереди массивом и двумя индексами

индекса 1В, а чтение — 1Е. Если после чтения элемента 1Е оказывается рав­ным 1В, то это означает, что все элементы очереди прочитаны (состояние

очереди — Empty). Когда в результате записи элемента значения индекса IBдостигает своего максимума (MaxSize), то, за счет произошедших ранее чте­ний из очереди, в массиве Containerможет оказаться свободное место в его начале, которое целесообразно переиспользовать. Это достигается сбрасы­ванием IBв минимально возможное значение (в примере: IB := 1). Теперь заполнение очереди возможно до тех пор, пока IBне станет равным IE(см. рис. 8.96), и, таким образом, состояние заполненности очереди (Full) есть равенство индексов IBи IEпосле записи элемента.

При чтении очередного элемента возможно, что IEуказывает на послед­ний элемент массива. Это означает, что после чтения он должен быть уста­новлен на начало Container'a. В результате конфигурация занятости массива снова принимает вид, изображенный на рис. 8.9а.

Нагляднее всего описанный процесс можно представить при помощи изображения массива Containerв виде кольца, т. е. склеивая его начало с концом, благодаря чему особые случаи работы с индексами исключаются (см. рис. 8.10). Следует обратить внимание на равенство IE = IB, которое

Новости

  • 1
  • 2
Prev Next

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

24.01.2016

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

Роскосмос не планирует в течение ближайшего десятилетия осуществлять пуск тяжёлой ракеты-носителя А...

Ученые РФ опровергли выводы исследований о вреде ГМО

24.01.2016

Ученые РФ опровергли выводы исследований о вреде ГМО

Исследователи из Института проблем передачи информации (ИППИ РАН) проанализировали несколько самых п...

Летающие "Крокодилы"

24.01.2016

Летающие "Крокодилы"

20 удивительных фактов о боевом вертолете Ми-24.Этот вертолет стал таким же узнаваемым символом сове...

В Аргентине описали новый вид динозавра-гиганта

24.01.2016

О ранее неизвестном виде динозавра, относящемуся к инфраотряду зауроподов, рассказали аргентинские п...

Реклама