I figured it couldn't be that hard to implement just by sticking things on one end of a list and taking them off the other, so I wrote one between having breakfast and setting off late for work.
This evening I polished it off a bit, and even added logging so you could see how big your queue had grown.
The code is available for download under a CC license from my Maths and Stats web pages.
If anyone wants to add this to a package or make a package of it, let me know and I'll help you write a stack and a deque too.