I’m looking for a data structure that will push its oldest/last element out if a new element is inserted. For example, let
Drepresent the structure.
Dcontains 3 elements of the type
D‘s default values will be initialized to
D = [1, 2, 3]
Numberthat contains the value
5is inserted into
3will be pushed out, while
2are shifted right.
D = [5, 1, 2]
The first thing that comes to mind would be an array, but the definition does not include the pushing behavior.
Fixed-size queues are often implemented using what some people call circular buffers. If you remove the protection against it being full, you get the desired behaviour.
Of course, no actual pushing will happen in the array — that would be too expensive — but it will look like it from the outside.