(*

Title: Stacks ADT
Author:  William M. Farmer
Revised: 18-OCT-2002

Description: Defines a Stacks ADT in which stacks are represented as 
             linked lists.

Interface:

INTERFACE Stacks;
  TYPE Stack;
  CONST Bottom: Stack;
  PROCEDURE Push(i: INTEGER; s: Stack): Stack;
  PROCEDURE Top(s: Stack): INTEGER;
  PROCEDURE Pop(s: Stack): Stack;
END Stacks.

*)

MODULE Stacks;

IMPORT Out;

(* Types *)

TYPE

  Stack* = POINTER TO StackRec;

  StackRec = 
    RECORD
      item: INTEGER;
      rest: Stack;
    END;

(* Constants *)

VAR Bottom-: Stack;   (* represents the empty stack *)

(* Exceptions: *)

PROCEDURE EmptyStackException();
BEGIN
  Out.String("Stacks.EmptyStackException: The stack is empty.");
  HALT(1)  (* Abort program *)
END EmptyStackException;

(* Local procedures *)

PROCEDURE Empty(s: Stack): BOOLEAN;
BEGIN
  RETURN s = Bottom
END Empty;

(* Interface procedures *)

PROCEDURE Push*(i: INTEGER; s: Stack): Stack;
  VAR t: Stack;
BEGIN
  NEW(t);
  t^.item := i;
  t^.rest := s;
  RETURN t
END Push;

PROCEDURE Top*(s: Stack): INTEGER;
BEGIN
  IF ~Empty(s) THEN
    RETURN s^.item
  ELSE
    EmptyStackException()
  END
END Top;

PROCEDURE Pop*(s: Stack): Stack;
BEGIN
  IF ~Empty(s) THEN
    RETURN s^.rest
  ELSE
    EmptyStackException()
  END
END Pop;

BEGIN
  Bottom := NIL   (* initializes Bottom *)
END Stacks.
