By data structure standards, the requisite amount of "fanciness" to implement a queue in a vector is table stakes, hardly even worth 10 minutes of class time at

By data structure standards, the requisite amount of "fanciness" to implement a queue in a vector is table stakes, hardly even worth 10 minutes of class time at the sophomore level, if not simply given out as homework. It is no problem at all to put a queue in a vector. You'd need a doubly-linked list for this, too, and as the article mentions, your linked-list queue is likely to lose just on malloc & free (or local equivalents) versus the vector. (The best optimization you could do in such a case would be to allocate multiple slots per pointer, to amortize the malloc/free time. Then you'd want to run benchmarks to tell what the optimal amount of slots would be. If a vector is optimal, as I strongly expect it would be, the answer would come out to be, "all of them".) Modern processors move chunks of RAM around really quickly. They're really optimized for it. It is one of the major things I'm referring to when I say our systems have been optimized for C. I often wonder about what an architecture designed in a world where linked lists were dominant would look like. However, it is certainly not this world.