There are several libraries that implement variations of deque for Clojure, but Clojure also allows transparent use of Java, so when necessary you can just use the Java deque, which I think is highly optimized.
Java's Deque is mutable (so, naturally, it will be much more performant). Also, I tried adding it to the benchmark but turns out that it doesn't support random access (for no good reason).