\manpage {queue} {E} {Queues}
 
\definition
An instance $Q$ of the parameterized data type \name\ is
a sequence of elements of data type $E$, called the element
type of $Q$. Elements are inserted at one end (the rear) and deleted at the
other end (the front) of $Q$. The size of $Q$ is the length of the sequence;
a queue of size zero is called the empty queue.
 
\creation Q  
 
\create { }
   { creates an instance \var\ of type \name. \var\ is initialized
            with the empty queue. }
 
 
\operations 2 4 
 
\op  E top {()}
           {  returns the front element of \var.\\
              \precond $Q$ is not empty. }
 
 
\op  E pop {()}
           {  deletes and returns the front element of \var.\\
	      \precond $Q$ is not empty. }
 
 
\op  void append {(E\ x)}
           {  appends $x$ to the rear end of \var. }
 
 
\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 queue. }
 
 
\implementation
Queues 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 
queue.
 
