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?

I can't figure out whether you are talking about a simple queue or a
priority queue.

For a simple queue, you can use a list with a pointer to the last
element (with appropriate use of a sentinel to simplify programming).
If you don't want to use a CONS cell per element, you can use a
circular buffer implemented as a vector, which you would then have to
resize from time to time; or you can use the Flexichain library from
cl.net which already does that for you.

For a priority queue, you need a more sophisticated data structure,
and you cannot get linear (even amortized) complexity of the
operations (as far as I know). The standard implementation uses a
heap which is implemented as a resizable vector. You can also use
other binary trees such as AVL, 2-3, skiplists, etc, but that would
probably be more expensive both in terms of space and time.

--
Robert Strandh
.

Relevant Pages

  • Re: Decent datastructure for queue operations
    ... Binary search tree might ... Use a queue data structure built on top of lists: ... the first and to the last last cons cell. ...
    (comp.lang.lisp)
  • Re: Decent datastructure for queue operations
    ... > FIFO data structure. ... So this is obviously not an ordinary queue. ... Regular Lisp lists can be used for FIFOs where the enqueue and dequeue ... The vector would have to be sorted in order to support a binary search. ...
    (comp.lang.lisp)
  • Re: C# Deque found on the web--thanks to The Game Programming Wiki
    ... The queue is ordered by priority, so it can use a binary search to find the correct insertion point. ... And I'd suggest that a more traditional approach, maintaining an ordered list of queues would work fine too (assuming that for a given priority, tasks are still FIFO). ... The ordered list could be a SortedList if one wants, but I think a regular list maintained by insertion sort would be fine, given that the number of unique priorities is likely to be low. ...
    (microsoft.public.dotnet.languages.csharp)
  • [RFC][PATCH 3/9] cgroups: block: cfq: I/O bandwidth controlling subsystem for CGroups based on CFQ
    ... Extends the original CFQ data sructures and adds the major cfqio_subsys ... * Each block device managed by CFQ I/O scheduler is represented ... * One more basic CFQ scheduler data structure is cfq_queue, ... * which is a queue of requests. ...
    (Linux-Kernel)
  • Re: after ids
    ... Hmm, with only a very slightly smarter data structure, you can have ... Have a hash table that maps afterID to the after event's data ... The after events' data structures are kept in a priority queue ...
    (comp.lang.tcl)