스칼라에서 배열을 사용하는 큐 구현 방법을 큐에 넣기

Question

def enqueue(elem: T): Unit = {  
    A(rear) = elem 
    rear += 1 
    size += 1 
    if (size == 0) { 
     front = 0 
     rear = 0 
     } 
    if (size == A.length) { 
     grow() 
     } 
    } 

배열을 사용하여 큐를 구현할 때 큐잉 메서드에 문제가 있지만 정확히 어디에 오류가 있는지 알 수 없습니다. 그래서 내가 실수 한 부분에 대한 힌트를 좀주세요. 위의 코드에서 size는 배열 대기열의 요소 수입니다. grow은 배열이 가득 차면 배열을 두 배로 늘리는 함수입니다. 미리 감사드립니다.

Answer 1

무엇이 잘못되었는지 알려주지 않으므로 어둠 속의 장면이므로 선택한 데이터 구조에 대해 논의하지 않습니다.

테스트 size == 0은 쓸모없는 것처럼 보입니다. 크기는 enqueue 바로 뒤에 0이 아닙니다. 그러나 큐를 대기열에 넣을 때 수행 할 작업을 알려주는 경우 front에 요소를 반환하고 front을 증가시키고 size을 감소시킵니다.

그래서 몇 가지 발언

1. 결코 일어날 수 대기열의 다음 호출, 예방 적 성장 전화 놀라운 일이다. 빈 공간이 부족할 때 엔큐가 매우 시작됩니다.
2. 데이터를 디큐하고 다시 엔큐 할 때 데이터가 배열의 오른쪽으로 이동합니다. 따라서 매우 작은 항목 (크기가 작음)이있는 대기열에서도 항목이 배열의 오른쪽 가장자리에있을 수 있으며 공간이 부족할 수 있습니다. 성장을위한 테스트 (또는 적어도 뭔가를하는 것)는 크기가 아니라 뒤쪽에 있어야합니다.
3. 결과적으로 배열에 필요한 것보다 훨씬 많은 공간이 있어도 결과가 커질 수도 있고 적어도 수행해야 할 수도 있습니다. 배열이 거의 꽉 차 있다면 실제로 확장해야합니다 (공간이 남아 있더라도 그렇지 않으면 모든 값을 복사하고 성능을 O (N)으로 유지하기 위해 대기열에 넣기/빼내기 사이클이 발생할 위험이 있습니다). 여유 공간이 부족하면 요소를 배열의 시작 부분으로 간단히 이동해야합니다.

요약 : 후면 배열의 길이에있는 경우 대기열의 시작, 당신은 크기는 배열, 앞의 시작 요소를 복사, 절반의 공간을 말한다 이하

• 입니다해야하는 경우 = 0 = 크기 후면 크기가 더 큰 경우 size == 0을 테스트하려는 경우
• , 새로운 배열을 할당하고 새로운 배열

Answer 2

의 시작 부분에 요소를 복사, 먼저 그렇게해야한다.

클래스의 불변 조건과 메소드의 사전 조건 및 사후 조건을 문서화하여 각 메소드가 대기열 구현 내부의 주요 특성을 유지하는지 확인하는 데 도움이 될 수 있습니다. http://en.wikipedia.org/wiki/Design_by_contract을 참조하십시오.

불변 는 같은 크기의 배열 길이 또는 크기> = 0 항상 작거나 같은 수 있었다.