Значит STL реализация вектора не подходит в данном случае и должна быть подходящая "искаробки".

  man queue - там почему-то не стесняются указать чего и как лучше использовать:

Linked lists are the simplest of the doubly linked data structures and support only the above functionality over singly-linked lists.

     Tail queues add the following functionality:
           1.   Entries can be added at the end of a list.
           2.   They may be traversed backwards, from tail to head.
           3.   They may be concatenated.
     However:
           1.   All list insertions and removals must specify the head of the
                list.
           2.   Each head entry requires two pointers rather than one.
           3.   Code size is about 15% greater and operations run about 20%
                slower than singly-linked lists.

И как видите, меня снова не волнует как оно устроено внутри. достаточно знать чем мне грозит использование функциональности.