52704.fb2
inc(FTail);
if (FTail = FList.Count) then
FTail := 0;
if (FTail = FHead) then
idGrow;
end;
procedure TtdIntDeque.idGrow;
var
OldCount : integer;
i, j : integer;
begin
{увеличить размер списка на 50%}
OldCount := FList.Count;
FList.Count := (OldCount * 3) div 2;
{распределить данные по увеличенной области, поддерживая при этом очередь с двусторонним доступом}
if (FHead= 0) then
FTail := OldCount else begin
j := FList.Count;
for i := pred(OldCount) downto FHead do
begin
dec(j);
FList.List^[j] := FList.List^[i] end;
FHead := j;
end;
end;
function TtdIntDeque.IsEmpty : boolean;
begin
Result := FHead = FTail;
end;
procedure TtdIntDeque.Push(aValue : integer);
begin
if (FHead = 0) then
FHead := FList.Count;
dec(FHead);
FList.List^[FHead] := pointer(aValue);
if (FTail = FHead) then
idGrow;
end;
function TtdIntDeque.Pop : integer;
begin
if FHead = FTail then
idError(tdeDequeIsEmpty, 'Pop');
Result := integer(FList.List^[FHead]);
inc(FHead);
if (FHead = FList.Count) then
FHead := 0;
end;
Алгоритм работает следующим образом. Поставим значение -1 в очередь с двусторонним доступом. Это специальное значение, которое указывает о необходимости выполнить считывание входной строки по одному элементу. Теперь поставим в очередь с двусторонним доступом номер исходного состояния. Установим целочисленное значение равным 0. Это значение будет индексом текущего символа в строке, сопоставление с которой выполняется.
После того, как подготовка закончена, мы входим в цикл. На каждом этапе выполнения цикла выполняется одно и то же действие: выталкивание верхнего значения из очереди. Если этим значением является -1 (как, естественно, это будет вначале), мы увеличиваем индекс текущего символа и извлекаем этот символ из сопоставляемой строки. Снова поставим значение -1 в очередь, чтобы знать, когда нужно выполнить считывание следующего символа. Если это значение не -1, оно должно быть реальным номером состояния. Взглянем на запись состояния в таблице переходов. Если текущий входной символ соответствует шаблону символов этого состояния, значение NextStatel состояния нужно поставить в очередь. Понятно, что если шаблоном символов состояния был е, символ не соответствовал шаблону. В этом случае в очередь с двусторонним доступом мы заталкиваем значение NextStatel, а затем значение NextState2.