[kccqzy]

In C++ the std::vector type handles this by doubling the capacity when full. I think this approach also works for this data structure. When the capacity has been reached simply double the capacity and rebuild from scratch. Perhaps quadruple because then each double-ended queue would double in size, avoiding that pesky sqrt(2). The amortized time should be the same.

[saagarjha]

> In C++ the std::vector type handles this by doubling the capacity when full.

Of course, the growth factor is implementation-dependent and I believe some compilers use smaller growth factors to improve performance.

[rurban]

Th optimal growth factor is the golden ratio 1+sqrt(5) [1.618], but 2 is much faster to calculate.

[saagarjha]

Is calculating the new size really the bottleneck here?