[학습 노트 - 데이터 구조 07 - 대기 열]

6589 단어 구조 알고리즘
대기 열의 정의
대기 열 은 한 끝 에 만 삽입 작업 을 할 수 있 고 다른 한 끝 에 서 는 삭제 작업 을 할 수 있 는 선형 표 입 니 다.
대열 은 FIFO 라 고 부 르 는 선진 적 인 선형 표 이다.삽입 을 허용 하 는 한 끝 을 팀 끝 이 라 고 하고 삭제 할 수 있 는 한 끝 을 팀 머리 라 고 합 니 다.
대기 열의 추상 데이터 형식
마찬가지 로 선형 표 이 고 대기 열 에 도 선형 표 와 유사 한 여러 가지 조작 이 있 습 니 다. 다른 것 은 데 이 터 를 삽입 하 는 것 은 팀 끝 에서 만 할 수 있 고 데 이 터 를 삭제 하 는 것 은 팀 머리 에서 만 할 수 있 습 니 다.
ADT 대기 열 (큐)
Data
     。        ,             

Operattion
 InitQueue(*Q) :     ,       Q

 DestroyQueue(*Q):    Q  ,    

 ClearQueue(*Q) :  Q

 QueueEmpty(Q):   Q  ,  true,    false

 GetHead(Q,*e):   Q     , e    Q     。

 EndQueue(*Q,e):   Q  ,     e   Q        

 DeQueue(*Q,*e):    Q     ,  e    

 QueueLength(Q):    Q     

endADT
순환 대기 열
선형 표 는 순서 저장 과 체인 저장 이 있 고 스 택 은 선형 표 이기 때문에 두 가지 저장 방식 이 있다.마찬가지 로 대기 열 은 특수 한 선형 표 로 서 이 두 가지 저장 방식 도 존재 한다.대기 열 순서 저장 부족
한 대기 열 에 n 개의 요소 가 있다 고 가정 하면 순서대로 저 장 된 대기 열 은 n 보다 큰 배열 을 만 들 고 대기 열의 모든 요 소 를 배열 의 앞 n 개의 단원 에 저장 해 야 합 니 다. 배열 아래 에 0 으로 표 시 된 것 은 바로 팀 머리 입 니 다.이른바 입 대기 열 조작 이란 사실 팀 끝 에 원 소 를 추가 하 는 것 이다. 원 소 를 이동 할 필요 가 없 기 때문에 시간 복잡 도 는 O (1) 이다.
스 택 과 달리 대기 열 요소 의 배열 은 팀 의 머리, 즉 아래 에 0 으로 표 시 된 위치 입 니 다. 그러면 대기 열 에 있 는 모든 요소 가 앞으로 이동 해 야 한 다 는 것 을 의미 합 니 다. 즉, 아래 에 0 으로 표 시 된 위치 가 비어 있 지 않 습 니 다. 이때 시간 복잡 도 는 O (n) 입 니 다.
만약 팀 이 앞장 서서 원 소 를 움 직 이지 않 는 다 면 팀 의 성능 은 크게 증가 할 것 이다.팀 헤드 가 꼭 0 으로 표 시 된 위치 에 있 을 필 요 는 없다 는 것 이다.하나의 요소 만 있 을 때 팀 머리 와 부속 이 겹 치 는 것 을 피하 기 위해 front 지침 은 팀 머리 요 소 를 가리 키 고 rear 지침 은 팀 꼬리 요소 의 다음 위 치 를 가리 키 며 front = rear 일 때 이 대기 열 은 비어 있 습 니 다.
긴 주인 이 5 인 배열, 초기 상태, 빈 대기 열 이 라 고 가정 합 니 다.front 와 rear 지침 은 모두 아래 표 시 된 0 의 위 치 를 가리킨다.그 다음 에 a1 / a2 / a3 / a4, 입단 front 지침 은 여전히 아래 표 시 된 0 위 치 를 가리 키 고 rear 지침 은 아래 표 시 된 4 위 치 를 가리킨다.
팀 을 나 가면 a1, a2 는 front 지침 이 아래 에 표 시 된 2 의 위 치 를 가리 키 고 rear 는 변 하지 않 으 며 다시 팀 에 들 어가 면 a5 가 변 하지 않 습 니 다. 이때 front 지침 은 변 하지 않 고 rear 지침 은 배열 밖으로 이동 합 니 다. 이런 현상 은 가짜 넘 침 입 니 다.순환 대기 열 정의
그래서 가짜 넘 침 을 해결 하 는 방법 은 뒤에 가득 차 면 처음부터 시작 하 는 것 이다. 즉, 머리 와 꼬리 가 연결 되 는 순환 이다.우 리 는 대열 의 끝 과 끝 이 연 결 된 순서 저장 구 조 를 순환 대열 이 라 고 부른다.
이 어 위 에 a6 가 입대 하여 아래 에 0 으로 표시 되 어 있 으 며, rear 지침 은 아래 에 1 로 표시 되 어 있 으 며, 다시 a7 에 들 어가 면 rear 지침 은 front 지침 과 겹 쳐 아래 에 2 로 표시 되 어 있 는 위 치 를 가리킨다.
  • 이때 문제 가 또 나 왔 습 니 다. 우리 가 방금 말 했 듯 이 빈 대기 열 은 front 는 rear 와 같 습 니 다. 지금 대기 열 이 가득 찼 을 때 도 front 는 rear 와 같 습 니 다. 그러면 이때 의 대기 열 공간 이 비어 있 는 지 가득 찬 지 어떻게 판단 합 니까?
  • 방법 은 표지 변수 flag 를 설정 하 는 것 입 니 다. front = = rear, 그리고 flag = 0 대기 열 이 비어 있 을 때 front = = rear 및 flag = 1 시 대기 열 이 가득 차 있 을 때
  • 방법 두 번 째 는 대기 열 이 비어 있 을 때 조건 은 front = rear 입 니 다. 대기 열 이 가득 찼 을 때 우 리 는 그 조건 을 수정 하여 요소 공간 을 유지 합 니 다.즉, 대기 열 이 가득 찼 을 때 배열 에 남 은 단원 이 있 습 니 다.
    우 리 는 두 번 째 방법 에 중심 을 두 고 토론 합 니 다. rear 는 front 보다 클 수도 있 고 front 보다 작 을 수도 있 기 때문에 한 위치 만 다 를 때 상황 이 가득 하지만 한 바퀴 가 다 를 수도 있 습 니 다.따라서 대기 열의 최대 크기 가 QueueSize 라면 대기 열 이 가득 찬 조건 은 (rear + 1)% QueueSize = = front 입 니 다.
    일반적인 대기 열 길 이 를 계산 하 는 공식: (rear - front + QueueSize)% QueueSize
    순환 대기 열의 순서 저장 구조 코드:
    typedef int  QElemType
    typedef struct
    {
         QElemType   data[MAXSIZE];
         int   front;
         int   rear;
    }SqQueue;
    
    //     
    Status InitQueue(SqQueue  *Q)
    {
       Q->front=0;
       Q->rear = 0;
        return OK;
    }
    
    //     
    int  QueueLength(QqQueue  Q)
    {
        return   (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
    }
    
    //    
    status  EnQueue(SqQueue  *Q,QElemType  e)
    {
         if((Q->rear+1)%MAXSIZE==Q->front)
             return ERROR;
         Q->data[Q->rear]=e;
         Q->rear = (Q-rear+1)%MAXSIZE;
         return OK;
    }
    
    //    
    status  DeQueue(SqQueue  *Q,QElemType  *e)
    {
         if(Q->front==Q->rear)
             return ERROR;
         *e = Q->data[Q->front];
          Q->front = (Q->front+1)%MAXSIZE;
         return OK;
    }

    대기 열의 체인 식 저장 구조 및 실현
    대열 의 체인 식 저장 구 조 는 사실은 선형 표 의 단일 체인 표 이다. 단지 그것 은 머리 만 들 어 갈 수 있 을 뿐 우 리 는 그것 을 체인 대열 이 라 고 부른다.
    //    
    typedef  struct  QNode
    {
        QElemType   data;
        struct  QNode  *next;
    }QNode,*QueuePtr;
    
    //       
    typedef  struct
    {
        QueuePtr   front,rear;
    }LinkQueue;

    대기 열의 체인 저장 구조 - 입 대 조작
    대열 에 들 어가 조작 할 때 사실은 링크 꼬리 에 결점 을 삽입 하 는 것 이다.
    Status EnQueue (LinkQueue *Q,QElemType  e)
    {
       QueuePtr  s = (QueuePtr)malloc(sizeof(QNode));
       if(!s)
          exit(OVERFLOW);
          s->data = e;
          s->next = NULL;
          Q->rear->next = s;
          Q->rear = s;
          return  OK;
    }

    대기 열의 체인 식 저장 구조 - 출 대 조작
    팀 을 나 와 조작 할 때 바로 머리 결점 의 후계 결점 이 팀 을 나 와 머리 결점 의 후계 점 을 그 뒤의 결점 으로 바 꾸 는 것 이다. 만약 에 링크 가 머리 결점 을 제외 하고 하나의 요소 만 남 았 을 때 rear 를 머리 결점 으로 가 리 켜 야 한다.
    /*     ,  Q     , e    ,   OK,    ERROR*/
    
    Status DeQueue (LinkQueue *Q,QElemType  *e)
    {
         QueuePtr  p;
         if(Q->front==Q->next)
            return  ERROR;
         p=Q->front->next;  //            p
         *e = p->data;   //              e
          Q->front->next=p->next; //        p->next        
           if(Q->rear==p)
               Q->rear=Q->front;
            free(p);
            return OK;
    }

    좋은 웹페이지 즐겨찾기