HELP QUEUE                                       Robert Duncan, Nov 1989

Simple queues.


    CONTENTS - (Use <ENTER> g to access required sections)

 -- The Queue Module
 -- The Queue Type
 -- Functions on Queues


-- The Queue Module ---------------------------------------------------

signature Queue
structure Queue : Queue
    The structure -Queue-  is an  autoloadable library  module with  the
    following signature:

        signature Queue = sig

            type 'a queue

            exception Dequeue
            exception Front

            val nilqueue    : 'a queue
            val enqueue     : 'a * 'a queue -> 'a queue
            val dequeue     : 'a queue -> 'a * 'a queue
            val front       : 'a queue -> 'a
            val isempty     : 'a queue -> bool

        end;    (* signature Queue *)


-- The Queue Type -----------------------------------------------------

type 'a queue
    The  type  of  queues.  A  queue  is  a  "first-in-first-out"   data
    structure, where insertions take  place at the  "back" of the  queue
    and deletions at  the "front". This  implementation is a  functional
    (side-effect free)  one,  giving  a constant  insertion  time  and a
    constant average deletion time. The  type is abstract, and does  not
    admit equality.


-- Functions on Queues ------------------------------------------------

val nilqueue : 'a queue
    The empty queue.


val enqueue (x : 'a, q : 'a queue) : 'a queue
    Inserts the item -x- at the front of the queue -q-.


exception Dequeue
val dequeue (q : 'a queue) : 'a * 'a queue
    Deletes and returns  an item from  the front of  the queue -q-.  The
    result is a  pair containing the  deleted item and  the rest of  the
    queue. The exception -Dequeue- is raised if -q- is the empty queue.


exception Front
val front (q : 'a queue) : 'a
    Returns (but does not  delete) an item from  the front of the  queue
    -q-. The exception -Front- is raised if -q- is the empty queue.


val isempty (q : 'a queue) : bool
    Returns -true- if -q- is the empty queue.


--- C.all/pml/help/queue
--- Copyright University of Sussex 1991. All rights reserved. ----------