|
Читайте также: |
Другой тип однонаправленного связанного списка – очередь (queue). Очередь, как способ организации ожидания в реальной жизни, воплощается в памяти компьютера по тем же правилам: первым пришел – первым обслужен. Её можно описывать как структуру FIFO, что означает first in – first out (первым вошел – первым ушел).
При реализации очереди с помощью массива необходимо иметь два параметра, указывающие на голову (head) очереди и её хвост (tail). Другое название этих параметров фронт (front) и тыл (rear). Элемент, добавляемый в очередь, оказывается в ее хвосте, а элемент, удаляемый из очереди, находится в ее голове. Существенное отличие очереди от стека состоит в том, что вставка новых элементов осуществляется в конец списка, а не в начало, как в стеках. Для работы с очередями также разработаем несколько процедур и функций, отражающих наиболее характерные операции над ними. Здесь принято использовать несколько иную терминологию:
Представим, что массив свернут в кольцо: за максимальным индексом 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 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Организация стеков. | | | Связанные списки. |