순환 대기열front==rear

순환 대열이 가득 차거나 비어 있는 조건은 모두front==rear인데 이 두 사람 사이의 차이를 어떻게 구분합니까?

시나리오 1:

분석: 이 순환 수열은 데이터 그룹, 헤더 포인터front, 팀의 요소 개수count 필드를 포함합니다.처음에는 front와count를 모두 0으로 설정합니다.대열이 비어 있는 조건은count0입니다.팀이 꽉 찬 조건은countmaxsize입니다.코드는 다음과 같습니다.

class SqQueueClass2
{
  const  int  MaxSize=5;   
private  string[]  data；   // 
private  int  front;       // 
private  int  count;      // 
public  SqQueueClass2()  // ， 
{
  data=new  string  [MaxSize];
  front=0;
  count=0;
}
}
//----------------- -----------------
// -
public  bool  QueueEmpty()
{
  return  (count==0);
}
// 
public  bool  enQueue(string e)
{
  int  rear;
  rear=(front+count)%MaxSize;
  if(count==MaxSize)      // 
Return false;
  rear=(rear+1)%MaxSize;
  data[rear]=e;
  count++;
  return  true;
}
// 
public  bool  deQueue()
{
  if (count==0)
return false;
front=(front+1)%MaxSize;
e=data[front];
  count--;
  return true;
}
// 
public int GetCount()
{
 return count;
}

시나리오 2:

front와rear를 각각 대열의 머리와 대열의 끝 지침으로 하고, 또 하나의 표지tag로 대열이 비어 있을 수도 있고, 가득 찰 수도 있으며, frontrear는 대열이 비어 있거나 꽉 차는 조건으로 사용할 수 있다.Tag 초기값은 0으로 설정하고 입대에 성공할 때마다 Tag=1, 출대에 성공할 때마다 Tag=0입니다.frontrear & &tag1은 입대 작업 후front=rear를 나타낸다. 이때 팀이 가득 차면 같은 이치로frontrear & &tag=0이면 팀이 비어 있음을 나타낸다.코드는 다음과 같습니다.

namespace ConsoleApplication
{
   class sqQueueClass
   {
        const int MaxSize = 100;
        public string[] data;
        public int front, rear;
        public int tag = 0;
        public sqQueueClass()
        {
            data = new string[MaxSize];
            front = rear = -1;
         }
// 
         public bool QueueEmpty()
         {
            return (front == rear && tag == 0);
          }
// 
          public bool enQueue(string e)
          {
            if (front == rear && tag == 1)
                return false;
            rear = (rear + 1) % MaxSize;
            data[rear] = e;
            tag = 1;
            return true;
          }
// 
          public bool deQueue(ref string e)
          {
            if (front == rear && tag == 0)
                return false;
            front = (front + 1) % MaxSize;
            e = data[front];
            tag = 0;
            return true;
          }
    }
}

비교:

방안1의 판단 조건은 비교적 간단하지만 저장 공간을 낭비하고count 변수로 대기열에 있는 요소의 개수를 직접 알 수 있다.방안2는 저장 공간을 충분히 이용할 수 있지만 출대 입대 작업을 할 때 매번 tag에 대해 재정의를 해야 한다. 이외에 방안2 판단 조건도 비교적 복잡하다.

요약:

비순환 대기열의 가짜 넘침 현상과 수조의 저장 공간을 충분히 사용할 수 있도록 수조의 전단과 후단을 연결하여 순환 대기열을 형성한다.순환 대열은 입대 출대 조작을 실현할 때 알고리즘의 실현 순서에 주의해야 한다. 입대할 때 먼저 대열이 꽉 찼는지 판단하고 출대할 때 대열이 비어 있는지 판단한 다음에 상응하는 입대 출대 조작을 해야 한다.