Re: Decent datastructure for queue operations

"meng" <meng234@xxxxxxxxx> writes:

> Hi guys,
>
> I've been developing a tool which has to use lots of queues, well a
> FIFO data structure. So far, I used lists but they are obviously not
> efficient as enqueue operation can take linear time (this is because
> existing entries are not enqueued again, and we need to sort of search
> the queue). Binary search has come into mind, but vector is still not a
> good candidate due to difficulty of insertion. Binary search tree might
> be an option, so...
>
> - does anyone here have a better idea?
> - or if a binary search tree is really a great idea, are there built-in
> LISP functions for it?
>
> Thanks in advance for any idea!

Use a queue data structure built on top of lists: keep a reference to
the first and to the last last cons cell. You can google this group
for implementations -- in the case where your queue is just a cons
cell whose car is tht head of the queue and whose cdr is the tail,
this is sometimes called a tconc.

--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'
.

Loading