program LinkedQueue;

type
  itemtype = integer; {Contents of Queue}

  nodePtr = ^queuenode;

  queuenode = record    {Queue Node Structure}
    itemData: itemtype;
    next: nodePtr;
  end;

  queue = record  {Queue Structure}
    entryPtr : nodePtr;
    num : integer;
    frontPtr : nodePtr;
  end;


{*****************************************
Procedure to Initialise a Queue
Pre: Queue not initialised
Post:Queue initialised to empty.
******************************************}
procedure init(var q:queue);
  begin
    q.entryPtr:= nil;
    q.frontPtr := nil;
    q.num:=0;
  end;


{*****************************************
Function to return True/False if Queue is full
Pre: Queue initialised
Post:Queue unchanged
******************************************}
function isFull(q:queue): boolean;
begin
isFull:=false;
end;

{*****************************************
Function to return True/False if Queue is empty
Pre: Queue initialised
Post:Queue unchanged
******************************************}
function isEmpty(q:queue): boolean;
begin
isEmpty:=q.num=0;
end;


{*****************************************
Function to return number of items in Queue
Pre: Queue initialised
Post:Queue unchanged
******************************************}
function itemNo(q:queue): integer;
begin
itemNo:=q.num;
end;


{*****************************************
Procedure to add an item to the back of Queue
Pre: Queue initialised and not full
Post:Queue has item inserted at the back
******************************************}
procedure join(var q:queue;i:itemtype);
  var
     tempPtr : nodePtr;

  begin
    new(tempPtr);
    tempPtr^.itemData:=i;
    tempPtr^.next:=q.entryPtr;
    q.entryPtr:=tempPtr;
    if (q.num=0) then q.frontPtr:=tempPtr;
    q.num:=q.num+1;
  end;

{*****************************************
Procedure to Remove an item from front of Queue
Pre: Queue initialised and not empty
Post:Queue has item removed from front
******************************************}
procedure leave(var q:queue;var i:itemtype);
  var
    tempPtr:nodePtr;

  begin
    if (isEmpty(q))
     then writeln('Sorry - Queue is Empty')
     else
       begin
         i:=q.frontPtr^.itemData;
         tempPtr:=q.entryPtr;
         if (q.num=1)
           then
             begin
               q.entryPtr:=nil;
               q.frontPtr:=nil;
             end
           else
             begin
               while (tempPtr^.next<>q.frontPtr) do tempPtr:=tempPtr^.next;
               q.frontPtr:=tempPtr;
               tempPtr:=tempPtr^.next;
               q.frontPtr^.next:=nil;
             end;
         Dispose(tempPtr);
         q.num:=q.num-1;
       end;
  end;


{*****************************************
               MAIN PROGRAM
******************************************}
Var
  TestQueue:Queue;
  item:itemtype;

BEGIN
  init(TestQueue);
  join(TestQueue,21);
  join(TestQueue,24);
  join(TestQueue,28);
  writeln('Number of items in Queue: ',itemNo(TestQueue));
  leave(TestQueue,item);
  writeln('The item at the front of the Queue was ',item);
  writeln('Number of items now in Queue: ',itemNo(TestQueue));
  leave(TestQueue,item);
  leave(TestQueue,item);
  leave(TestQueue,item);
  join(TestQueue,1);
  join(TestQueue,2);
  join(TestQueue,3);
  join(TestQueue,4);
  join(TestQueue,5);
  join(TestQueue,6);
  join(TestQueue,7);
  join(TestQueue,8);
  join(TestQueue,9);
END.
