데이터 구조 순환 대기 열의 자동 확장 용량

순환 대기 열의 기본 조작 및 자동 용량 확장

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0

typedef int QElemType;
typedef int Status;

1. 대기 열 초기 화

Status InitQueue(SqQueue * Q)
{
    Q->queue_size = MAX_QUEUE_SIZE;
    Q->base = malloc(Q->queue_size * sizeof(SqQueue));
    if (!Q->base)
        return ERROR;
    Q->font = 0;
    Q->rear = 0;

    return OK;
}

2. 입단 조작
rear 의 레이 블 이 font 의 레이 블 보다 클 때 확장 은 매우 간단 합 니 다. font + 1 을 직접 사용 하면 됩 니 다. 그러나 순환 대기 열 이기 때문에 rear 의 레이 블 이 font 보다 작은 레이 블 이 나타 날 수 있 습 니 다. 이때 rear 의 레이 블 + 1 을 직접 사용 하면 rear = font 는 이때 문제 가 발생 할 수 있 습 니 다.그러면 rear 가 font 보다 작은 상황 을 어떻게 해결 합 니까? 기본 적 인 생각 은 다음 과 같 습 니 다. 대기 열 에 있 는 요 소 를 새로운 배열 에 넣 은 다음 에 배열 의 요 소 를 대기 열 의 헤드 포인터 가 가리 키 는 배열 에 할당 한 다음 에 삽 입 된 요 소 를 이 대기 열 에 넣 으 면 행렬 이 font 가 rear 보다 큰 상황 으로 초기 화 됩 니 다.블랙박스 밖의 사용자 에 게 는 대기 열의 특징 만 볼 수 있다.코드 는 다음 과 같 습 니 다:

Status EnQueue(SqQueue * Q, QElemType e)
{
    if (!Q)
        return ERROR;
    if ((Q->rear + 1) % Q->queue_size == Q->font)
    {
        Q->queue_size = Q->queue_size + INCREMENT_SIZE;
        Q->base = realloc(Q->base, sizeof(QElemType) * Q->queue_size);
        if (!Q->base)
            return ERROR;

        if (Q->rear < Q->font)
        {
            int i = Q->font;
            int j = 0;
            int temp_A[Q->queue_size];      // hold the value of the queue

            for (i; i != Q->rear; j++)
            {
                temp_A[j] = Q->base[i];
                i = (i + 1) % (Q->queue_size - INCREMENT_SIZE);
            }
			
			// put the value of the array to the queue Q
            for (int k = 0; k < (Q->queue_size-1-INCREMENT_SIZE); k++)
            {
                Q->base[k] = temp_A[k];
                printf("Q: %d    A: %d 
", Q->base[k], temp_A[k]);
            }
			// put the new elem to the queue
            Q->base[Q->queue_size-1-INCREMENT_SIZE] = e;
            Q->font = 0;
            Q->rear = Q->queue_size-1;

            return OK;
        }
    }

    Q->base[Q->rear] = e;
    Q->rear = (Q->rear+1) % Q->queue_size;

    return OK;
}

3. 출전 조작

Status DeQueue(SqQueue * Q, QElemType * e)
{
    if (!Q || (Q->font == Q->rear))
        return ERROR;
    *e = Q->base[Q->font];
    Q->font = (Q->font + 1) % Q->queue_size;

    return OK;
}

// If the queue is empty return true else return false
Status QueueEmpty(SqQueue * Q)
{
    if (Q->font == Q->rear)
        return TRUE;
    else
        return FALSE;
}

4. 인쇄 대기 열

Status printQueue(SqQueue * Q)
{
    int status = TRUE;

    if (!Q || (Q->font == Q->rear))
        status = FALSE;
    int index = Q->font;
    int i = Q->font;
    while ( i % Q->queue_size != Q->rear)
    {
       // printf(" array[%d]  num %d 
", i, Q->base[index]); //       vist   ，     
        printf("\t num %d 
", Q->base[index]); //       vist   ，     
        i++;
        index = (i) % Q->queue_size ;
    }

    return status;
}

PS: 전재 출처 를 밝 혀 주세요!!