데이터 구조지식 포인트대열

1. 대기 열 정의

//      
typedef struct
{
    elemType data[maxSize];
    int front, rear;        
}queue; 

//      
typedef struct Node
{
    elemType data;
    Node *next;
};

typedef struct queue
{
    Node *front;
    Node *rear;
};

대열 의 정 의 를 통 해 알 수 있 듯 이 대열 은 선착순 으로 데 이 터 를 저장 하 는 것 외 에 두 개의 지침 이 필요 하 다. 각각 팀 의 머리 와 팀 의 꼬리 를 대표 해 야 한다.
2. 진 팀 출전 조작
팀 을 나 가 는 동작 은 팀 의 머리 지침 을 한 명 뒤로 이동 시 키 고, 팀 에 들 어가 서 조작 하면 팀 의 꼬리 지침 을 한 명 뒤로 이동 시킨다.
순차 저장 대기 열
대열 에 들어가다

bool enterQueue(queue &q, elemType data)
{
    if(q.rear == maxSize)
        return false;
    //       ，    
    q.rear++;
    q.data[q.rear] = data;
    
    return true;    
}

대열 에 나가다

elemType outQueue(queue &q)
{
    //        
    if(q.front == q.rear)
        return -9999;
    //      ，           
    return q.data[q.front++];
}

링크 저장 큐
대열 에 들어가다

bool enterQueue(queue &q,elemType e)
{
    Node *p;
    p = (Node *)malloc(sizeof(Node));
    
    p->data = e;
    p->next = NULL;
    
    //                   
    q.rear->next = p;
    //          
    q.rear = p;
    
    return true;
}

대열 에 나가다

elemType outQueue(queue &q)
{
    //        
    if(q.front == q.rear)
        return -999;
    
    elemType e;
    e = q.front->next->data;
    
    //           
    Node *p = q.front->next;
    q.front->next = p->next;
    //              
    free(p);
    
    return e;
}

3. 특수 대기 열 - 순환 대기 열과 양단 대기 열
순환 대기 열 만 토론 합 니 다.순환 대기 열 은 순서 표를 기반 으로 합 니 다. 일반 대기 열과 다른 것 은?

포인터 가 배열 의 마지막 으로 이동 할 때 처리 하여 배열 의 맨 앞 을 가리 키 도록 해 야 한다

팀 의 길 이 를 어떻게 계산 합 니까

대열 의 빈 팀 을 어떻게 판단 하고 팀 을 꽉 채 웁 니까

질문

//            ，      ，    0
front = (front + 1) % maxSize;

문제

//    
length = q.rear - q.front;
//    
length = (q.rear - q.front + maxSize) % maxSize;

일반 대기 열 과 달리 순환 대기 열 에 q. rear < q. front 가 존재 하 는 경우 입 니 다.

q. rear < q. front 시 q. rear - q. front 는 대기 열 에 있 는 빈 위치 개수 의 반대 수 와 같 습 니 다. (q. rear - q. front + maxSize) 는 파티 길이 와 같 습 니 다. 다시% maxSize 는 길이 자체

와 같 습 니 다.

q. rear > q. front 일 때 (q. rear - q. front + maxSize)% maxSize 는 q. rear - q. front 즉 파티 길이

문제 3 일반적인 상황 에서 순환 대기 열 이 비어 있 을 때 q. rear = q. front, 팀 이 꽉 찼 을 때 q. rear = q. front.그래서 팀 이 비어 있 고 팀 이 꽉 찼 다 는 것 을 구분 할 수 없다.

tag 를 추가 하고 팀 은 0 이 며 팀 은 1.

size 속성 을 추가 하여 매번 파티 / 파티 에 들 어간 후 대기 열 길 이 를 수정 합 니 다

rear 는 마지막 요소 의 다음 위 치 를 가리 키 며 대기 열 에 빈 자 리 를 비 웁 니 다.(1) 팀 이 비어 있 는 조건 은 여전히 q. front = = q. rear (2) 팀 이 꽉 찬 조건 은: (q. rear + 1)% maxSize = = q. front 이다. 이때 팀 이 꽉 찬 것 은 두 가지 상황 만 존재 한다. (1) rear = = maxSize & & front = = 0 (2) rear > front 는 모두 (rear + 1)% maxSize 를 통 해 front 를 구 할 수 있다.

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

데이터 구조지식 포인트대열

좋은 웹페이지 즐겨찾기