A queue type data structure that allows you to quickly determine the position of an element. There is?

Question

Mathematics

Suppose I have a large list of elements (unique strings).
Elements can be added to it at the end, moved within this list (not exchanged), and removed from the beginning.
Maybe you know such a data structure that will allow me to quickly (without enumeration of the entire list) determine the number of its position in such a list by an element, such a structure MUST allow you to quickly move elements (with a calculation of the changed positions of other elements).
Number of elements of the order of 5 million.
Ideal case when:
Time to add to the tail: O(1)
Time to get from the head: O(1)
Time to determine the position: O(1) or O(log n)
Time to move one element from the end back to top: O(log n) or O(1)
Any links welcome. Thank you.

Answer 1

Maybe something like this will come in: we store the elements in an ordinary doubly linked list: insert into the tail, get from the beginning - O (1). Swapping the tail and head is also O(1). Now we need to figure out how to deal with indexes. Given that the elements inside the queue are not mixed, you can always maintain an added variable that will increment by 1 when the next element is added. (It will never decrease). Also support the droped variable, which reflects how many items were removed from the head. Further, when adding an element, we will write the following information to the hash table: key-string, value - variable added at the time of adding the element. To find the real index of an element, you will need to find the difference between the value in the hash table and the droped variable.
Plus a little bit of confusion with droped and added overflow protection

Answer 2

If the elements inside you need to be able to only swap in pairs and there is a reasonable estimate for the volume - a ring buffer.

Answer 3

A queue that does not physically move elements (ring or some kind of std:: deque) and allows you to quickly determine the position by the pointer.
Plus any index (hash or wood) whose elements are pointers to the elements of the queue. If the elements of the queue are unique_ptr, then the pointers will be exactly on unique_ptr! For "garbage" languages ​​(C#, Java), instead of pointers, you can come up with some kind of identification codes - for example, a combination of a number in an array pool and a number in an array.
Enqueue - enter the element into the index. Dequeue - remove from the index. Exchange of positions - we adjust these two elements of the index.