статическая очередь с доступом по индексу

Через деревья разного рода. Подойдёт битмап если мн-во относительно компактно, если кусочно компактно, то sparse битмапы.

Хотя не совсем понятно. Вставка только в конец идёт, т.е. есть только операция push()?

Вставка только в конец идёт, т.е. есть только операция push()?

да

Если элементы не повторяются, то битовое множество.

Тогда всё очень просто, стуктура данных будет состоять из массива фиксированного размера и оффсета. При каждой вставке пишем значение в ячейку (offset + size - 1) % size и обновляем offset = (offset + 1) % size. Типа ~ кольцевой буфер.

Действительно просто, спасибо за ответ, mashina :)

если хранятся не цифры, а нормальные объекты, то проще всего делать так. Адрес элемента хранится в массиве и вставляется по циклу. Т.е. первая вставка перезаписывает 0 элемент, вторая 1 и т.п. Соответственно получение адреса элемента по индексу это что-то вроде get(i) = p[i + count % len], где count это кол-во вставок, len это длина твоего статической очереди.