>> I used a linked-list for a deque last time I had to implement one myself.

You're referring to a double-ended queue in general rather than the deque interface specified by the standard, right?