Data.Queue
Library with double-ended queues supporting access at both ends in constant amortized time
Detailed package documentation (available shortly after this version has been published)