어떤 순환 대기열 구현이 가장 적합합니까?

Question

순환 대기열에 대해 배우고 있습니다. 어떤 원형 큐의 구현이 배열 구현 또는 연결된 목록 구현 중 가장 좋습니까?

Answer 1

링크 된 목록에서 수행하는 경우 마지막 노드가 첫 번째를 가리 키므로 실제로 순환 될 수 있습니다. 그러나 나는 당신이 '최고'라는 뜻을 분명히 할 필요가 있다고 생각합니다.

Answer 2

필자는 연결된 목록 버전이 배열에 더 많은 요소를 허용하는 메모리를 계속 조정할 필요가 없다는 두 가지 솔루션 중 더 좋을 것이라고 말합니다. Skilldrick이 링크드리스트에서 말했던 것뿐만 아니라 실제로 그것이 속한 곳을 가리키고 있습니다 (마지막 노드가 첫 번째 노드를 가리킴).

Answer 3

순환 목록에서 수행해야하는 작업에 따라 다릅니다. 예를 들어 랜덤 액세스 ("목록의 237 번째 항목 지정")가 필요할 경우 배열 구현이 훨씬 빨라질 것입니다.

반면에 구현을 사용하면 목록 크기를 조정해야 할 수도 있습니다. 느린 경우도 있습니다. 당신은 상환 할 수있어 O (1) 인서트 당 상환 시간을 얻지 만, 실시간 시스템에서는 가끔 느리게 작동하는 것이 용납되지 않을 수 있습니다.

Answer 4

순환 큐는 배열을 구현하는 바운드 큐입니다.

우리는 메모리 공간을 효과적으로 활용할 수 있기 때문에 일반적인 큐보다 낫습니다. 정상 큐가 있고 거기에서 일부 요소가 삭제 된 경우 빈 공간이 생성되고 큐에 빈 셀이있는 경우에도 또한 삽입은 한면 (즉, 뒤 또는 꼬리)에서 수행되어야하고 삭제는 다른면 (즉, 앞 또는 머리)에서 수행되어야하기 때문에 새로운 요소를 삽입 할 수 없습니다. 그러나 순환 큐의 경우 앞면과 뒷면 서로 인접 해있다.