program LinkedStack;

type
  itemtype = integer;   {Contents of Stack-the items}

  nodePtr = ^stacknode; {a pointer to a node within the stack}

  stacknode = record    {Stack Node Structure}
    itemData: itemtype; {the data part of a node in the stack}
    next: nodePtr;      {a pointer to point to the next node in stack}
  end;

  stack = record  {Stack Structure}
    bottomPtr : nodePtr; {a pointer to point at the first item IN - last OUT}
    num : integer;       {number of items within the stack}
    topPtr : nodePtr;    {a pointer to point at the last item IN - first OUT}
  end;


{*****************************************
Procedure to Initialise a Stack
Pre: Stack not initialised
Post:Stack initialised to empty.
******************************************}
procedure init(var s:stack);
  begin
    s.bottomPtr:= nil;  {bottom pointer points at nothing}
    s.topPtr := nil;    {top pointer points at nothing}
    s.num:=0;           {set number of items to zero}
  end;


{*****************************************
Function to return True/False if stack is full
Pre: Stack initialised
Post:Stack unchanged
******************************************}
function isFull(s:stack): boolean;
begin
isFull:=false;  {can never be full}
end;

{*****************************************
Function to return True/False if stack is empty
Pre: Stack initialised
Post:Stack unchanged
******************************************}
function isEmpty(s:stack): boolean;
begin
isEmpty:=s.num=0;       {only if the number of items is still 0}
end;


{*****************************************
Function to return number of items in Stack
Pre: Stack initialised
Post:Stack unchanged
******************************************}
function itemNo(s:stack): integer;
begin
itemNo:=s.num;  {return the number of items part of the stack}
end;


{*****************************************
Procedure to Insert an item on top of Stack
Pre: Stack initialised and not full
Post:Stack has item inserted on top
******************************************}
procedure push(var s:stack;i:itemtype);
  var
     tempPtr : nodePtr;

  begin
    new(tempPtr);               {allocate memory for a node}
    tempPtr^.itemData:=i;       {place the item into its' data part}
    tempPtr^.next:=nil;         {set its' next pointer to nil since its' the lastest addition}
    s.topPtr^.next:=tempPtr;    {set the previous node to point to the new addition}
    s.topPtr:=tempPtr;          {set the top pointer to point to the new added node}
    if (s.num=0) then s.bottomPtr:=tempPtr;     {in case it's the first item set the bottom pointer to point to it}
    s.num:=s.num+1;             {increment the number of items in the stack}
  end;

{*****************************************
Procedure to Remove an item from top of Stack
Pre: Stack initialised and not empty
Post:Stack has item removed from top
******************************************}
procedure pop(var s:stack;var i:itemtype);
  var
    tempPtr:nodePtr;

  begin
    if (isEmpty(s))                             {if stack is empty}
     then writeln('Sorry - Stack is Empty')     {then}
     else                                       {else}
       begin
         i:=s.topPtr^.itemData;         {throw out the data part of the top node}
         tempPtr:=s.bottomPtr;          {set the temp pointer to the bottom node}
         if (s.num=1)                   {if it is the only node}
           then                         {then}
             begin
               s.topPtr:=nil;             {set top pointer to point at nothing}
               s.bottomPtr:=nil;          {set bottom pointer to point at nothing}
             end
           else                         {else}
             begin
               while (tempPtr^.next<>s.topPtr) do tempPtr:=tempPtr^.next;{move temp pointer to point at the node before the top - the soon be top}
               s.topPtr:=tempPtr;      {set top pointer to point where the temp is pointing}
               tempPtr:=tempPtr^.next; {move the temp pointer to the old top}
               s.topPtr^.next:=nil;    {set the new top node pointer to point at nothing}
             end;
         Dispose(tempPtr);      {release/free the memory not in use-the old top}
         s.num:=s.num-1;        {decrement the number of items in the stack}
       end;
  end;


{*****************************************
               MAIN PROGRAM
******************************************}
Var
  TestStack:stack;
  top:itemtype;

BEGIN
  init(TestStack);
  push(TestStack,21);
  push(TestStack,24);
  push(TestStack,28);
  writeln('Number of items in Stack: ',itemNo(TestStack));
  pop(TestStack,top);
  writeln('The item on top of Stack was ',top);
  writeln('Number of items now in Stack: ',itemNo(TestStack));
  pop(TestStack,top);
  pop(TestStack,top);
  pop(TestStack,top);
END.