Clojure has several pre-built data structures that can be used to implement our ideas. Here you have a comparison of the well-known vector and the poorly-documented clojure.lang.PersistentQueue.
Edit: I changed the code in quotes to a Github Gist since I like it much better the way it looks. Sorry for the horrible contrast of the gists and the blogger template, I believe nothing will save me from modifiying the colors.
There was a fatal flaw in the implementation. It is now corrected. Thanks to the commentators.
