This is pretty easy to implement, by combining a double linked list with a hashtable, however I wanted this to have the same interface as a double linked list, so I made a new
dequeuesvocabulary which abstracts the operations on a double linked list, such as
Double linked lists in the
dlistsvocabulary now implement this protocol instead of exposing dlist-specific operations.
The dequeue protocol also has a
dequeue-member?generic word. This word runs in linear time on dlists.
Search dequeues in the
search-dequeueswrap an assoc and a dequeue and provide a sub-linear implementation of
dequeue-member?(constant time if the assoc is a hashtable). Pushing elements adds them to both the dequeue and assoc; the membership test is then just a call to
key?on the assoc.