주소 지정 가능한 FIFO 대기열을 구현하는 방법은 무엇입니까?

Question

나는 현재 모든 O (1) 작업

• 삽입으로 데이터 구조를 찾고 있어요 (K, V) : 큐의 끝 부분에 값을 삽입합니다.
• remove_key (K) : 제공된 키에 해당하는 대기열에서 값을 제거하십시오.
• remove_head() : 대기열 (가장 오래된 대기열)의 앞면에서 값을 제거합니다.

내가 생각할 수있는 것은 합리적으로 쉽게 구현할 수있는 것은 이중 구조의 목록을 기본 데이터 구조로 사용하고 해시 테이블의 목록 노드에 포인터를 유지하는 것입니다. 그러면 원하는 점근 동작을 얻을 수 있습니다. 이것은 실제 런타임에서 가장 효율적인 옵션이 아닐 수도 있습니다.

"주소 지정 가능 우선 순위 대기열"은 문헌에서 발견되었지만 다소 복잡하고 (어쩌면 더 비싼) 데이터 구조이기 때문에 누군가에게 더 좋은 제안이 있는지 궁금해하고있었습니다. 지금까지 녹에 대해 이렇게 구현 한 사람이 아무도없는 것 같습니다. 그래서 나는 너무 복잡해지지 않기를 바랍니다.

Answer 1

pub struct VecDeque<T>을 사용하고 remove_head() 대신 pop_front()을 사용합니다. VecDeque이