A search deque is a data structure with constant-time insertion and removal of elements at both ends, and constant-time membership tests. Inserting an element more than once has no effect. Search deques implement all deque operations in terms of an underlying deque, and membership testing with deque-member? is implemented with an underlying assoc. Search deques are defined in the search-deques vocabulary.