How about a circular array? If you keep the index of the last element and the first, you can have O(1) for every criteria you gave.

How about a circular array? If you keep the index of the last element and the first, you can have O(1) for every criteria you gave.

EDIT: You could take a C++ vector approach for capacity: double the size when it gets full.