Deque can remove both the first and the last element efficiently.
Created attachment 206231 [details] patch
Comment on attachment 206231 [details] patch wrong patch
Created attachment 206233 [details] patch
Comment on attachment 206233 [details] patch r=me, though we should also improve remove() some day.. Also, this could use an API test.
http://trac.webkit.org/changeset/152449 (with API test)