unit Queue;

{ Diese Unit implementiert den abstrakten Datentyp Queue, eine Warteschlange. }

interface

type
   PQueueElem = ^TQueueElem;
   TQueueElem = record
		   Data	: Pointer;
		   Next	: PQueueElem;
		end;	
   TQueue     = record
		   Head	: PQueueElem;
		   Tail	: PQueueElem;
		end;	
	       
procedure InitQueue(var Queue : TQueue);
procedure Enqueue(var Queue : TQueue; Elem : Pointer);
function Dequeue(var Queue : TQueue) : Pointer;
function IsEmpty(Queue : TQueue) : Boolean;

implementation

procedure InitQueue(var Queue : TQueue);
begin
   Queue.Head := nil;
   Queue.Tail := nil;
end;

procedure Enqueue(var Queue : TQueue; Elem : Pointer);
var
   NewElem : PQueueElem;
begin
   New(NewElem);
   NewElem^.Data := Elem;
   NewElem^.Next := nil;
   if Queue.Tail <> nil then
      Queue.Tail^.Next := NewElem;
   Queue.Tail := NewElem;
   if Queue.Head = nil then Queue.Head := NewElem;
end;
     
function Dequeue(var Queue : TQueue) : Pointer;
var
   OldElem : PQueueElem;
begin
   if Queue.Head = nil then  { Welcher Dummbatz hat dann Dequeue aufgerufen? }
   begin
      Dequeue := nil;
      exit;
   end;
   OldElem := Queue.Head;
   Queue.Head := OldElem^.Next;
   if Queue.Head = nil then Queue.Tail := nil;
   Dequeue := OldElem^.Data;
   Dispose(OldElem);
end;

function IsEmpty(Queue : TQueue) : Boolean;
begin
   IsEmpty := Queue.Head = nil;
end;

end.