Статическая реализация очереди на основе массива

Материал из DRKB


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

Очевидно, что со временем указатель на конец при очередном включении элемента достигнет верхней границы той области памяти, которая выделена для очереди. Однако, если операции включения чередовались с операциями исключения элементов, то в начальной части отведенной под очередь памяти имеется свободное место. Для того, чтобы места, занимаемые исключенными элементами, могли быть повторно использованы, очередь замыкается в кольцо: указатели (на начало и на конец), достигнув конца выделенной области памяти, переключаются на ее начало. Такая организация очереди в памяти называется кольцевой очередью. Возможны, конечно, и другие варианты организации: например, всякий раз, когда указатель конца достигнет верхней границы памяти, сдвигать все непустые элементы очереди к началу области памяти, но как этот, так и другие варианты требуют перемещения в памяти элементов очереди и менее эффективны, чем кольцевая очередь.

В исходном состоянии указатели на начало и на конец указывают на начало области памяти. Равенство этих двух указателей (при любом их значении) является признаком пустой очереди. Если в процессе работы с кольцевой очередью число операций включения превышает число операций исключения, то может возникнуть ситуация, в которой указатель конца "догонит" указатель начала. Это ситуация заполненной очереди, но если в этой ситуации указатели сравняются, эта ситуация будет неотличима от ситуации пустой очереди. Для различения этих двух ситуаций к кольцевой очереди предъявляется требование, чтобы между указателем конца и указателем начала оставался "зазор" из свободных элементов. Когда этот "зазор" сокращается до одного элемента, очередь считается заполненной и дальнейшие попытки записи в нее блокируются. Очистка очереди сводится к записи одного и того же (не обязательно начального) значения в оба указателя. Определение размера состоит в вычислении разности указателей с учетом кольцевой природы очереди.

Программный пример иллюстрирует организацию очереди и операции на ней.

{==== Программный пример ====}
unit Queue;                 { Очередь FIFO - кольцевая }

interface
const
  SIZE = ...;             { предельный размер очереди }
type
  TData = ...;            { элементы могут иметь любой тип }

{ инициализация - начало=конец=1 }
procesure QInit;
{ очистка - начало=конец }
procedure QClr;
{ запись в конец }
function QWrite(a: TData): Boolean;
{ выборка из начала }
function QRead(var a: TData): Boolean;
{ определение размера }
function QSize: Integer;

implementation

{ Очередь на кольце  }
var
  Queue: array [1..SIZE] of TData;   { данные очереди }
  Top, Bottom: Integer;   { начало  и конец  }

{ инициализация - начало=конец=1 }
procedure QInit;
begin
  Top := 1;
  Bottom := 1;
end;

{ очистка - начало=конец }
procedure QClr;
begin
  Top := Bottom;
end;

{ запись в конец }
function QWrite(a: TData): Boolean;
begin
  if ((Bottom mod SIZE) + 1) = Top then
    { очередь полна }
    Result := False
  else
  begin
    { запись, модификация указ.конца с переходом по кольцу }
    Queue[Bottom] := a;
    Bottom := (Bottom mod SIZE) + 1;
    Result := True;
  end;
end;

{ выборка из начала }
function QRead(var a: TData): Boolean;
begin
  if Top = Bottom then
    Result := False
  else
  begin
    { запись, модификация указ.начала с переходом по кольцу }
    a := Queue[Top];
    Top := (Top mod SIZE) + 1;
    Result := True;
  end;
end;

{ определение размера }
function QSize: Integer;
begin
  if top <= bottom then
    Result := Bottom - Top
  else
    Result := Bottom + SIZE - Top;
end;

end.


Source: http://algolist.manual.ru
ID: 03963