Дек является симбиозом стека и очереди - это та же структура, но
на этот раз с ней можно работать с обеих концов. Таким образом, если мы будем
работать с деком только с левого края, то фактически получается стек. Аналогично
мы получим стек, если будем работать только с правого края (конца дека). Пользуясь
предписаниями "добавить в конец" и "взять из начала", мы сможем
получить очередь, элементы которой будут продвигаться справа налево. Название
дека произошло от сокращения английских слов Double Ended Queue - очередь
с двумя концами.
Приведем пример реализации ограниченного дека на turbo pascal, основанного
на динамическом одномерном массиве.
unit Deq;
interface
type
TElem = char;
TErrCode = byte;
PDeq = ^TDeq;
TDeq = object
private
Fp: pointer;
FNmax: word;
{ максимальное кол-во элементов }
FHead, FTail: word;
{ хвост, голова }
FErrCode: TErrCode;
{ код ошибки }
public
constructor Create(Len: word);
constructor Copy(Ptr: PDeq);
destructor Destroy;
procedure MakeEmpty;
{ очищает дек }
function Empty: boolean;
{ дек пуст? }
function Full: boolean;
{ дек полон? }
function MaxLen: word;
{ максимальное кол-во элементов }
function PushH(x: TElem): boolean;
{ добавить элемент в голову дека }
function PushT(x: TElem): boolean;
{ добавить элемент в хвост дека }
function PopH(var x: TElem): boolean;
{ взять элемент из головы дека }
function PopT(var x: TElem): boolean;
{ взять элемент из хвоста дека }
function ChangeH(x: TElem): boolean;
{ изменить значение головного элемента }
function ChangeT(x: TElem): boolean;
{ изменить значение хвостового элемента }
function SeeH(var x: TElem): boolean;
{ посмотреть значение головы дека }
function SeeT(var x: TElem): boolean;
{ посмотреть значение хвоста дека }
function DelH: boolean;
{ удалить головной элемент из дека }
function DelT: boolean;
{ удалить хвостовой элемент из дека }
function ErrCode: TErrCode;
end;
implementation
const
MaxHeap = 65520;
type
{ внутренняя реализация дека }
PArray = ^TArray;
TArray = array[0..0] of TElem;
constructor TDeq.Create;
var
mem: longint;
begin
if Len <= 0 then
begin
Fail;
exit;
end;
mem:= (longint(Len) + 1) * longint(sizeOf(TElem));
{ необходимый размер свободной памяти }
if (mem > MaxAvail) or (mem > MaxHeap) then
begin
fail;
exit;
end;
getmem(Fp, mem);
FNMax:= Len;
{ признак пустого дека }
FHead:= 0;
FTail:= 0;
FErrCode:= 0;
end; { TDeq.Create }
constructor TDeq.Copy;
var
mem: longint;
i: word;
begin
if Ptr = nil then
begin
Fail;
exit;
end;
mem:= (longint(Ptr^.MaxLen) + 1) * longint(sizeof(TElem));
{ необходимый размер свободной памяти }
if (mem > MaxAvail) or (mem > MaxHeap) then
begin
fail;
exit;
end;
getmem(Fp, mem);
FHead:= Ptr^.FHead;
FTail:= Ptr^.FTail;
{ копируем элементы из исходного дека }
for i:= 0 to Ptr^.MaxLen do
PArray(Fp)^[i]:= PArray(Ptr^.Fp)^[i];
FNMax:= Ptr^.MaxLen;
FErrCode:= 0;
end; { TDeq.Copy }
destructor TDeq.Destroy;
begin
freemem(Fp, longint(FNMax+1)*longint((sizeof(TElem))));
end; { TDeq.Destroy }
procedure TDeq.MakeEmpty;
begin
FHead:= 0;
FTail:= 0;
FErrCode:= 0;
end; { TDeq.MakeEmpty }
function TDeq.Empty;
begin
Empty:= (FTail = FHead);
FErrCode:= 0;
end; { TDeq.Empty }
function TDeq.Full;
begin
Full:= (FHead = (FTail + 1) mod (FNMax+1));
FErrCode:= 0;
end; { TDeq.Full }
function TDeq.MaxLen;
begin
MaxLen:= FNMax;
FErrCode:= 0;
end; { TDeq.MaxLen }
function TDeq.PushH;
begin
if Full then
begin
PushH:= false;
FErrCode:= 1;
exit;
end;
FHead:= (longint(FHead)-1) mod (FNMax + 1);
PArray(Fp)^[FHead]:= x;
PushH:= true;
FErrCode:= 0;
end; { TDeq.PushH }
function TDeq.PushT;
begin
if Full then
begin
PushT:= false;
FErrCode:= 1;
exit;
end;
PArray(Fp)^[FTail]:= x;
FTail:= (FTail+1) mod (FNMax + 1);
PushT:= true;
FErrCode:= 0;
end; { TDeq.PushT }
function TDeq.ChangeH;
begin
if Empty then
begin
ChangeH:= false;
FErrCode:= 2;
exit;
end;
PArray(Fp)^[FHead]:= x;
ChangeH:= True;
FErrCode:= 0;
end; { TDeq.ChangeH }
function TDeq.ChangeT;
begin
if Empty then
begin
ChangeT:= false;
FErrCode:= 2;
exit;
end;
PArray(Fp)^[(longint(FTail) - 1) mod (FNMax+1)]:= x;
ChangeT:= True;
FErrCode:= 0;
end; { TDeq.ChangeT }
function TDeq.PopH;
begin
if Empty then
begin
PopH:= false;
FErrCode:= 2;
exit;
end;
x:= PArray(Fp)^[FHead];
FHead:= (FHead + 1) mod (FNMax + 1);
PopH:= true;
FErrCode:= 0;
end; { TDeq.PopH }
function TDeq.PopT;
begin
if Empty then
begin
PopT:= false;
FErrCode:= 2;
exit;
end;
FTail:= (longint(FTail) - 1) mod (FNMax + 1);
x:= PArray(Fp)^[FTail];
PopT:= true;
FErrCode:= 0;
end; { TDeq.PopT }
function TDeq.SeeH;
begin
if Empty then
begin
SeeH:= false;
FErrCode:= 2;
exit;
end;
x:= PArray(Fp)^[FHead];
SeeH:= true;
FErrCode:= 0;
end; { TDeq.SeeH }
function TDeq.SeeT;
begin
if Empty then
begin
SeeT:= false;
FErrCode:= 2;
exit;
end;
x:= PArray(Fp)^[(longint(FTail) - 1) mod (FNMax + 1)];
SeeT:= true;
FErrCode:= 0;
end; { TDeq.SeeT }
function TDeq.DelH;
begin
if Empty then
begin
DelH:= false;
FErrCode:= 2;
exit;
end;
FHead:= (FHead + 1) mod (FNMax + 1);
DelH:= true;
FErrCode:= 0;
end; { TDeq.DelH }
function TDeq.DelT;
begin
if Empty then
begin
DelT:= false;
FErrCode:= 2;
exit;
end;
FTail:= (FTail - 1) mod (FNMax + 1);
DelT:= true;
FErrCode:= 0;
end; { TDeq.DelT }
function TDeq.ErrCode;
begin
ErrCode:= FErrCode;
end; { TDeq.ErrCode }
end.
197-577-902