with Ada.Unchecked_Deallocation;

package body Stack is
   procedure Free is new Ada.Unchecked_Deallocation (Node, Node_Access);

   procedure Push (S : in out Stack; Val : T) is
      New_Top : Node_Access := new Node;
   begin
      New_Top.Val := Val;
      New_Top.Bottom := S.Top;
      S.Top := New_Top;
   end Push;

   function Pop (S : in out Stack; Val : out T) return Boolean is
      Old_Top : Node_Access := S.Top;
   begin
      if Old_Top /= null then
         Val := Old_Top.Val;
         S.Top := Old_Top.Bottom;
         Free (Old_Top);
         return True;
      else
         return False;
      end if;
   end Pop;

   function Empty (S : Stack) return Boolean is
   begin
      return S.Top = null;
   end Empty;
end Stack;