2012-08-23 5 views
0

가능한 중복 :
how to find number of elements in a Circular Queue원형 큐 크기

나는 원형 큐를 구현하고 있지만 제대로 큐의 크기를 얻을 수 없습니다. 같은 문제에 관한 이전 주제를 찾았습니다. 제안 된 솔루션은 두 개의 포인터를 사용하고 첫 번째 것과 동일한 객체를 가리키는 동안 두 번째 포인터를 증가시키는 것입니다. 하지만 큐에 다른 객체가있을 때만이 appoach가 작동한다고 생각합니다. 내 경우에는 모든 객체가 비슷합니다. 순환 대기열의 크기는 어떻게 알 수 있습니까? 이 공식이 너무 나를 위해 작동하지 않습니다

m_front 및 m_tail 꼬리와 전면 큐 인덱스입니다
int size = abs(m_front -m_tail) ; 

.

감사

+0

Q : 배열로 구현 된 큐입니까? 링크 된 목록 일 경우 front == tail을 결정하는 것이 가장 좋습니다. 당신은 카운트를 직접 지키지 않는 한 "크기"를 결정할 수 없습니다. – paulsm4

+0

같은 하나 : http://stackoverflow.com/questions/4459141/how-to-find-number-of-elements-in-a-circular-queue –

+0

@ paulsm4 : 예, 배열로 구현됩니다. 앞 == 꼬리이면 배열이 비어 있다는 뜻입니다. – Galileo

답변

2

이 그것을 수행해야합니다 N은 배열의 길이입니다

if m_front > m_tail 
    size = (m_front - m_tail) 
else 
    size = (m_front + N - m_tail) 

.

또는 Queue() 일 때 카운터를 증가시키고 Dequeue() 일 때 카운터를 줄이면됩니다.

+3

머리글과 꼬리 색인 만 있으면 'N'자를 모두 채우도록 허용하면 목록이 비어 있는지 가득 차 있는지 확인할 방법이 없습니다. 속도를위한 최상의 솔루션은 마지막 위치가 채워지는 것을 막는 것인데 반해, 저장을위한 최상의 솔루션은 푸시 및 팝 작업 중에 '빈'또는 '가득 참'플래그를 유지하는 것입니다. – paddy

+0

답장을 보내 주셔서 감사합니다. 이유는 모르지만 위의 공식은 작동하지 않습니다. 항상 제로의 결과를 제공합니다. 두 번째 제안에 대해서는 대기열을 늘리거나 줄이려고 할 때이 절차로 액세스 경쟁을 생성하지 않을 것입니다. ame 시간에 크기 (병렬로 enqueue와 dequeuerun) ?? – Galileo

+0

스레드를 사용하는 경우에는 동일한 잠금 객체를 사용하여이 (및 큐/대기열 해제 메소드)를 잠금으로 묶어야합니다. –