HELP QUEUE Robert Duncan, Nov 1989 Simple queues. CONTENTS - (Use 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. ----------