한정된 Queue에서 배열을 데이터 구조로 사용하는 것은 왜 나쁜 생각입니까?

배열을 사용하여 고정 된 용량의 제한된 큐를 구현할 생각을하고있었습니다. 그런 다음 바운드 큐에서이 wiki-article을 발견했습니다. 그것은 언급 :한정된 Queue에서 배열을 데이터 구조로 사용하는 것은 왜 나쁜 생각입니까?

배열 때문에 시간의 비효율적 인 지출 사실이 얼마나 큐

내가 확실히 이해하지 못했다 전면 에 항목을 복사? 대기열에 추가하거나 대기열에 추가 할 때 색인을 머리 또는 꼬리로 업데이트하는 중입니다. 항목을 대기열의 맨 앞으로 복사하는 위치는 어디입니까?

출처

2011-03-09 brainydexter

복사가 없습니다 - 설명이 잘못되었습니다. 기사의 역사를 되돌아 보면 누군가가 실제로 모든 항목을 옮긴 코드를 가지고 있지만 그 코드는 현재 볼 수있는 버전으로 대체되고 잘못된 문장이 남아 있습니다. 또한 거기에 C++ 코드에 적어도 하나의 오류가 있습니다. enqueue()에서 조건 if(tail<head+QMAX)은 주어진 코드 꼬리가 결코 QMAX보다 크거나 같지 않으므로 결코 실패하지 않습니다.

출처

2011-03-09 06:30:55 MahlerFive

나는 너무 느꼈다. 내가 옳은 길 위에 있다는 것을 알았 기 때문에 기쁘다. 우리가이 작업을 수행하는 동안 한정된 Queue에 배열을 사용하는 데는 단점이 있습니다. (가정하에 나는 언더 플로우/오버 플로우를 처리한다)? – brainydexter

배열을 사용하는 유일한 단점은 전체 큐의 공간을 일부만 사용하더라도 할당 할 수 있다는 것입니다. 작은 배열 만 할당 한 다음 확장 될 때 다시 할당하는 것이 가능하지만 재 할당을 위해서는 모든 기존 요소를 새로 할당 된 메모리에 복사해야 할 수 있습니다. 링크 된 구조를 사용하면이 문제를 완전히 피할 수 있지만 노드 당 더 많은 공간 오버 헤드와 같은 자체적 인 단점이 있습니다. – MahlerFive

한정된 Queue에서 배열을 데이터 구조로 사용하는 것은 왜 나쁜 생각입니까?

답변

관련 문제