A fixed array with a head index and a count where positions wrap around with modulo, so removing from the front never shifts elements. When full it can double (copying once) to keep amortized O(1) pushes.
Ring buffer
A fixed array with a head index and a count where positions wrap around with modulo, so removing from the front never shifts elements. When full it can double (copying once) to keep amortized O(1) pushes.