\manpage {stack} {E} {Stacks} 
 
\definition
An instance $S$ of the parameterized data type \name\ is
a sequence of elements of data type $E$, called the element
type of $S$. Insertions or deletions of elements take place only at one end of
the sequence, called the top of $S$. The size of $S$ is the length of the
sequence, a stack of size zero is called the empty stack.
 
\creation S  
 
\create { }
   { creates an instance \var\ of type \name. \var\ is initialized
            with the empty stack. }
 
 
\operations 2 4
 
\op  E top {()}
           {  returns the top element of \var.\\
             \precond $S$ is not empty. }
 
 
\op  void push {(E\ x)}
           {  adds $x$ as new top element to \var. }
 
 
\op  E pop {()}
           {  deletes and returns the top element of \var.\\
             \precond $S$ is not empty. }
 
 
\op  int  size {()}
           {  returns the size of \var. }
 
 
\op  bool  empty {()}
           {  returns true if \var\ is empty, false otherwise. }
 
 
\op  void clear {()}
           {  makes \var\ the empty stack. }
 
 
\implementation
Stacks are implemented by singly linked linear lists. All operations take 
time $O(1)$, except clear which takes time $O(n)$, where $n$ is the size of 
the stack.
 
