Re: bugs in queue operations

   Date: Thu, 24 Dec 2009 11:59:09 -0800
   From: Robert Ransom <[email protected]>

   Yes, when I was still thinking about ways to optimize
   DELETE-FROM-QUEUE!.  Our mutation-based queue implementations allow
   both ENQUEUE! and DEQUEUE! to be implemented in constant time; I am not
   aware of any functional data structures which would allow this.

For the standard functional queue implemented by a pair of stacks,
ENQUEUE and DEQUEUE run in constant amortized time.  QUEUE-HEAD can
lose and run in linear time, but it could be internally destructive in
order to run in constant amortized time.  The operations running in
constant amortized time can, as usual, at the cost of some overhead,
be adapted to do the work incrementally and thereby run in constant
real time.

   I have attached to this message a bug-fix patch for Taylor Campbell's
   queue package, and a Mercurial bundle for Scheme 48 that simplifies my
   QUEUES package and then changes it to use his data structure.

Oops -- thanks.  The operations with the bugs you found are, of
course, among those that I never actually use myself.  (For that
matter, I pretty much never use anything but ENQUEUE!, DEQUEUE!,
QUEUE-EMPTY?, and QUEUE-HEAD.)  I'll apply the fixes when I get a
chance.