Структуры и алгоритмы обработки данных


Очередь - часть 2


Кроме того. Учитывая то, что полустатическая очередь реализуется на одномерном массиве, необходимо следить за возможностью его переполнения. Сэтой целью вводится опнрация full(q).

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

потеря значимости. Операция empty, разумеется, выполнима всегда.

 

Пример реализации очереди в виде одномерного массива на Паскале:

const

  MaxQ = ...

type

  E = ...

  Queue = Array [1..MaxQ] of E;

var

  Q: Queue;

  F, R: Integer;

{Указатель F указывает на начало очереди. Указатель R указывает на конец очереди.     Если очередь пуста, то F = 1, а R = 0 (То есть R < F – условие пустоты очереди).}

 

Procedure Insert(I: Integer; var Q: Queue);

begin

  Inc(R);

  Q[R]:=I;

end;

Function Empty(Q: Queue): Boolean;

begin

  If R < F then Empty:=True Else Empty:=False;

end;

Procedure Remove(var I: Integer; Q: Queue);

begin

  If Not Empty(Q) then

    begin

      I:=Q[F];

      Inc(F);

    end;

end;

 

Пример работы с очередью с использованием стандартных процедур.

MaxQ = 5

Производим вставку элементов A, B  и C  в очередь.

Insert(q, A);

Insert(q, B);

Insert(q, C);

Убираем элементы A и B из очереди.

Remove(q);

Remove(q);

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

Одним из решений возникшей проблемы может быть модификация операции remove таким образом, что при удалении очередного элемента вся очередь смещается к началу массива.


- Начало -  - Назад -  - Вперед -



Книжный магазин