Sorry, I meant to say, a dynamic array of pointers to fixed-sized arrays.
That's for a stack. For a queue a nice implementation is a power-of-2 growable circular queue of pointers to fixed-sized arrays (chunks); plus a ("intrusive", no more memory needed) linked list of some of the last free blocks (that need to be cleared if they contain indirections).
For a deque the implementation is similar, just a bit more complex.
(In theory there is a small queue optimization, a union on the dynamic array that implements the circular queue, to remove one indirection level when the queue needs only one chunk of memory, but then you have to add one test to tell apart the two configurations every time you add or remove an item, so probably it's not worth it).
Bye, bearophile
