Finger Tree — Deque

Push Left Push Right Pop Left Pop Right Reset

Finger tree: 2-3 tree with "fingers" at both ends for O(1) amortized push/pop at either end, O(log n) concat/split. Basis for Haskell's Data.Sequence.