Динамическая реализация очереди


Аналогично стеку, каждый элемент очереди должен иметь ссылку на следующий за ним элемент, поэтому элемент очереди объявляется как запись с двумя полями – информационное поле и связующее поле. Но для реализации операций с очередью необходимы уже две переменные: указатель pFirst на начало очереди и указатель pLast на конец очереди.

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

               
 
эл-т 1
next : 2

 

 
эл-т 2
next : 3

 

 
эл-т 3
next : 4

 

 
эл-т N
nil

 

 


. . . . . . . .

       
   
 
pFirst

 

 


Основные операции с динамической очередью:

· проверка отсутствия элементов в очереди

· добавление нового элемента в конец очереди

· удаление элемента из начала очереди

  • проход по очереди от начала к концу

Добавление нового элемента немного по-разному реализуется для пустой и непустой очереди. Аналогично, по-разному выполняется удаление из очереди, содержащей один или более одного элемента. Для того, чтобы эти операции во всех случаях выполнялись единообразно, часто используется следующий прием: в начало очереди вводится фиктивный элемент-заголовок, который НИКОГДА не удаляется и всегда содержит адрес первого элемента очереди.

В этом случае создание пустой очереди включает в себя:

· выделение памяти для заголовка с помощью указателя pFirst

· занесение в ссылочную часть заголовка пустого указателя nil

· установка указателя конца очереди pLast = pFirst

Схемы пустой и непустой очереди приводятся на следующих рисунках:

               
   
заголовок
Next: 1

 

 
элем. 1
Next: 2

 

 
элем. N
nil

 

 

 


…..

               
     
       
 
pFirst

 


Необходимые описания типов и переменных:

type pQueueItem = ^ TQueueItem;

{ссылочный тип для адресации элементов очереди}

TQueueItem = record{базовый тип: структура элемента очереди}

inf : integer; {информационная часть}

next : pQueueItem;

{ссылочная часть: адрес следующего элемента}

end;

var pFirst, pLast : pQueueItem;

Тогда условие пустой очереди можно записать следующим образом:

pFirst^.next = nil

Для прохода по очереди от первого реального элемента к последнему необходимо:

· ввести вспомогательную ссылочную переменную pTemp

· установить pTemp в адрес первого реального элемента: pTemp := pFirst^.next

· организовать цикл по условию достижения конца очереди

  • в цикле обработать очередной элемент с помощью указателя pTemp и изменить этот указатель: pTemp := pTemp^.next

Добавление элемента в конец очереди выполняется следующим образом:

· выделить память для нового элемента с помощью стандартной функции Newи вспомогательной ссылочной переменной pTemp:

· заполнить поля нового элемента, в частности в связующую часть установить значение nil: pTemp^.next := nil

· изменить связующую часть бывшего последнего элемента таким образом, чтобы она адресовала новый добавленный элемент: pLast^.next := pTemp;

· изменить значение указателя pLast так, чтобы он указывал новый последний элемент: pLast := pTemp;

       
   

 


Удаление элемента из начала очереди (но после заголовка!) выполняется следующим образом:

· адресуем удаляемый элемент с помощью вспомогательной переменнойpTemp: pTemp := pFirst^.next;

· изменить связующую часть заголовка так, чтобы она указывала на второй элемент очереди, который теперь должен стать первым: pFirst^.next := pTemp^.next

· если после удаления в списке не остаётся реальных элементов, то необходимо изменить указатель pLast: pLast := pFirst

· обработать удаленный элемент, например - освободить занимаемую им память с помощью стандартной подпрограммы Dispose(pTemp)или включить его во вспомогательную очередь удаленных элементов

       
 
   

 


Сравнение двух способов реализации очереди полностью аналогично стеку. Интересной разновидностью очереди являются приоритетные очереди, в которых элементы выстраиваются не только в порядке поступления, но и в соответствии с их приоритетами: сначала идут более приоритетные элементы, потом – все менее приоритетные. Одноприоритетные элементы располагаются в порядке поступления. Это требует изменения процедуры добавления элемента в очередь: надо прежде всего найти место в очереди, куда должен вставиться новый элемент в соответствии с его приоритетом, а потом уже выполнить саму вставку. Фактически, приоритетную очередь можно рассматривать как разновидность упорядоченного линейного списка. Реализация линейных списков подробно рассматривается в следующей теме.

 



Дата добавления: 2020-07-18; просмотров: 436;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.01 сек.