Re: Decent datastructure for queue operations



>>>>> "meng" == meng <meng234@xxxxxxxxx> writes:

meng>

meng> To Kaz: the idea of using a hash table along side a list is
meng> not a bad idea, indeed. The only problem I encountered was
meng> the data structures became too big when many queues were in
meng> use.

meng> It doesn't have to be a priority queue, but the items should
meng> never be enqueued once they are there.

If your are looking only at EQ uniqueness then I believe a hash-table
will be your best bet. Ultimately there is a trade off between speed
and space requirements - you seem to want both.

If you can compare your items using a less-than type operation then a
priority queue using a binary heap (see Cormen, Leiserson and Rivest,
"Introduction to Algorithms", pp. 140--152, MIT Press) would probably
be more efficient in speed and possibly in space if you control the
heap extension and initial allocation to be appropriate for the
usage. An implementation of this in CL is available from the CMU/AI
depository.

--
John Williams
.