Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Организация очереди

Введение. | Введение | Текстовые файлы | Экспериментальный раздел работы. |


Читайте также:
  1. II.Организация и порядок проведения
  2. IV. Организация и порядок проведения Конкурса
  3. IV. Организация и проведения конкурса
  4. IV. Организация питания
  5. IV. Организация раннего выявления туберкулеза у взрослого населения
  6. IV. Организация учебного процесса
  7. Lt;variant>неформальная организация

Другой тип однонаправленного связанного списка – очередь (queue). Очередь, как способ организации ожидания в реальной жизни, воплощается в памяти компьютера по тем же правилам: первым пришел – первым обслужен. Её можно описывать как структуру FIFO, что означает first in – first out (первым вошел – первым ушел).

При реализации очереди с помощью массива необходимо иметь два параметра, указывающие на голову (head) очереди и её хвост (tail). Другое название этих параметров фронт (front) и тыл (rear). Элемент, добавляемый в очередь, оказывается в ее хвосте, а элемент, удаляемый из очереди, находится в ее голове. Существенное отличие очереди от стека состоит в том, что вставка новых элементов осуществляется в конец списка, а не в начало, как в стеках. Для работы с очередями также разработаем несколько процедур и функций, отражающих наиболее характерные операции над ними. Здесь принято использовать несколько иную терминологию:

 

  1. EnQueue(x,Q) – вставляет элемент x в конец очереди Q;
  2. DeQueue(Q) - удаляет первый элемент очереди.

 

Представим, что массив свернут в кольцо: за максимальным индексом maxlength сразу следует первый. Простейшая аналогия – часы, тогда maxlength=12 и пусть параметры tail=9, а head=4. Элементы очереди располагаются в этом кольце последовательно от 4 до 9. Теперь, для вставки нового элемента в очередь, достаточно переместить «стрелку –указатель» конца очереди Q.tail на одну позицию по часовой стрелке и записать элемент в эту позицию. При удалении элемента из очереди надо переместить «стрелку – указатель» начала очереди Q.head по часовой стрелке на одну единицу. При таком представлении очереди операции вставки и удаления выполняются за фиксированное время, независимое от длины очереди.

Заметим, что при данной интерпретации очереди нельзя отличить, когда она пуста, а когда заполняет весь массив. Следует поэтому ввести механизм определения пустых очередей при максимальной длине массива maxlength или ввести запрет на количество элементов превышающих значение maxlength-1.

Определим тип данных Queue как запись, имеющую два поля

 

const maxlength =12;

type elementtype = integer;

queue = record

elements: array[1..maxlength] of elementtype;

head, tail: integer

end;

var rq: qqueue; k: integer;

 

function AddOne(n: integer): integer;

begin

AddOne:= (n mod maxlength) + 1

end;

 

procedure EnQueue(x:elementtype; var Q:queue);

begin

with Q do

if AddOne(AddOne(tail))=head then

begin writeln(‘ Очередь полная’); Exit end

else begin

tail:= AddOne(tail);

elements[tail]:=x

end

end;

 

Для организации ввода данных напишем процедуру MakeNull(Q), очищающую очередь, делая её пустой. Она может быть полезна также и в других подпрограммах.

 

procedure MakeNull(var Q: queue);

begin

with Q do begin

head:= 1; tail:= maxlength

end

end;

 

procedure Data(var Q:queue);

var k:integer;

begin

MakeNull(Q);

for k:=1 to 10 do EnQueue(2*k-1,Q)

end;

 

Введем две новые функции: логическую функцию Empty(Q), возвращающую значение true тогда и только тогда, когда Q является пустой очередью, и функцию Front(Q), возвращающую первый элемент очереди Q. Используя эти функции, построим процедуру, удаляющую первый элемент из очереди DeQueue(Q) и процедуру вывода данных OutData(Q).

 

function Empty (Q:queue):boolean;

begin

with Q do

if AddOne(tail) = head then Empty:= true

else Empty:= false

end;

 

function Front (Q:queue):elementtype;

begin

with Q do

if Empty(Q) then

begin writeln(‘ Очередь пустая’); Exit end

else Front:=elements[head]

end;

 

procedure DeQueue(var Q:queue);

begin

with Q do

if Empty(Q) then

begin writeln(‘ Очередь пустая’); Exit end

else head:= AddOne(head)

end;

 

procedure OutData(Q:queue);

var k:integer;

begin

with Q do

for k:=head to tail do write(elements[k]:3,’ ’);

writeln

end;

 

Begin

Data(rq); OutData(rq);

DeQueue(rq); OutData(rq);

k:=Front(rq); writeln(‘ k=’,k:4)

readln

End.

 


Дата добавления: 2015-07-19; просмотров: 55 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Организация стеков.| Связанные списки.

mybiblioteka.su - 2015-2024 год. (0.008 сек.)