순환 대기 열 상세 설명 및 대기 열 순서 표시 및 구현

순환 대열―대열 의 순서 표시 와 실현
앞에서 순서 팀 을 분석 할 때 우 리 는 순서 팀 에'가짜 넘 침'문제 가 존재 한 다 는 것 을 알 고 있다.이 문 제 는 때때로 매우 큰 메모리 낭 비 를 초래 할 수 있다.순환 대기 열 은 이 문 제 를 해결 하기 위해 교묘 한 방법 을 제시 하 는 것 이다.순환 대기 열과 순서 대기 열의 주요 차이 점 은 순환 대기 열 이 순서 대기 열 을 억측 하여 환상 공간 을 조성 하 는 것 이다.조작 에 있어 서 이러한 공통점 과 차이 점 은 다음 과 같다.
같은 점:
순서 대기 열과 순환 대기 열 에서 출 대,입 대 조작 을 할 때,팀 의 우두머리,팀 의 꼬리 지침 은 모두 1 을 더 해서 앞으로 이동 해 야 한다.
다른 점:
1.순환 대기 열 에서 선두,꼬리 포인터 가 벡터 상계(MAXQUEUE_SIZE-1)시 1 조작 을 더 한 결 과 는 벡터 의 하계 0 을 가리킨다.순서 대기 열 에 설명 팀 이 가득 찼 습 니 다.이때 동적 순서 체인 을 사용 하면 신청 메모 리 를 추가 할 수 있 습 니 다.정적 순서 체인 을 사용 하면 프로그램 을 종료 할 수 있 습 니 다.
2.순서 대기 열 중 q.front=q.rear 는 대기 열 이 비어 있 음 을 나 타 냅 니 다.q.rear=MAXQUEUE_SIZE 는 팀 이 꽉 찼 음 을 표시 합 니 다.순환 대기 열 에서.front=q.rear 는 팀 이 비어 있 음 을 표시 합 니 다..rear=MAX 를 사용 할 수 없습니다.QUEUE_SIZE 는 팀 이 꽉 찼 음 을 나타 낸다.
순환 팀 이 꽉 찬 것 을 판단 하 는 두 가지 방법(본 고 는 두 번 째 방법 을 사용한다).
1.대기 열 이 비어 있 는 지 가득 찬 지 구분 하기 위해 표지 위 치 를 따로 설정 합 니 다.
2.요소 공간 을 적 게 사용 하고'대기 열 헤드 포인터 가 대기 열 꼬리 포인터 의 다음 위치 에 있 음'을 약속 하 며 대기 열 이 가득 찬 상태 로 표 시 됩 니 다.
두 번 째 방법의 실현:
◆rear 가 가리 키 는 단원 은 항상 비어 있다.
◆순환 대기 열 이 비어 있다:front=rear.
◆순환 대기 열 가득:(rear+1)%MAXQUEUE_SIZE=front 。
순환 대기 열 작업 및 포인터 변화 상황 은 다음 그림 과 같 습 니 다.

순환 대기 열 은'가짜 넘 침'문 제 를 해결 할 수 있 지만 동적 으로 분 배 된 1 차원 배열 을 통 해 이 루어 질 수 없 기 때문에 순환 대기 열 을 실현 하기 전에 최대 대기 열 길 이 를 설정 해 야 합 니 다.필요 한 최대 대기 열 길 이 를 예측 할 수 없다 면 링크 로 만 이 루어 질 수 있 습 니 다.
코드 구현:
순환 대기 열과 순서 대기 열의 헤더 파일 은 같 습 니 다

/*              */
#define true 1
#define false 0


/*        */
#define MAX_QUEUE_SIZE 6
/*         */
typedef int datatype;

/*          */
typedef struct queue{
  datatype sp_queue_array[MAX_QUEUE_SIZE];
  /*    */
  int front;
  /*    */
  int rear;
}cir_queue;


/*            */


/*         */
cir_queue queue_init();

/*         ,   
 *   true
 *     false
*/
int queue_empty(cir_queue q);


/*     e  q       
 *       true
 *     false
*/
int queue_en(cir_queue *q, datatype e);


/*       
 *  e      ,   true
 *      false
*/
int queue_de(cir_queue *q, datatype *e);

/*     */
void queue_clear(cir_queue *q);


/*       
 *     , e      ,   true
 *     false
*/
int get_front(cir_queue, datatype *e );


/*      */
int queue_len(cir_queue q);

/*     */
void queue_traverse(cir_queue q, void(*visit)(cir_queue q));


void visit(cir_queue s);


/*             */
#include<stdio.h>
#include<stdlib.h>
#include"cir_queue.h"

cir_queue queue_init()
{
  cir_queue q;
  q.front = q. rear = 0;
  return q;
}


int queue_empty(cir_queue q)
{
  return q.front == q.rear;
}

int queue_en(cir_queue *q, datatype e)
{
  /*         */
  if (q -> front == (q -> rear + 1) % MAX_QUEUE_SIZE)
    return false;
  /*    */
  q -> sp_queue_array[q -> rear] = e;
  q -> rear = (q -> rear + 1) % MAX_QUEUE_SIZE;
  return true;
}

int queue_de(cir_queue *q, datatype *e)
{
  /*          */
  if(q -> front == q -> rear)
    return false;
  /*  e       */

  *e = q -> sp_queue_array[q -> front];
  q -> front = (q -> front + 1 ) % MAX_QUEUE_SIZE;
  return true;
}


void queue_clear(cir_queue *q)
{
  q -> front = q -> rear = 0;
}

int get_front(cir_queue q, datatype *e)
{
  /*          */
  if (q.front == q.rear)
    return false;
  *e = q.sp_queue_array[q.front];
  return true;
}

int queue_len(cir_queue q)
{
  /*  front > rear */
  if(q.front > q.rear)
    return (q.rear + MAX_QUEUE_SIZE - q.front);
  else
    return (q.rear - q.front);
}


void queue_traverse(cir_queue q, void(*visit)(cir_queue q))
{
  visit(q);
}


void visit(cir_queue q)
{
  while(q.front != q.rear)
  {
    printf("%d ",q.sp_queue_array[q.front]);
    q.front = (q.front + 1) % MAX_QUEUE_SIZE;
  }
}


int main()
{
   cir_queue q = queue_init();
  queue_en(&q, 1);
  queue_en(&q, 2);
  queue_en(&q, 3);
  queue_en(&q, 4);
  queue_en(&q, 5);
  printf("    :length=%d
", queue_len(q));
  queue_traverse(q, visit);
  printf("  6   
");
  queue_en(&q, 6);
  queue_traverse(q, visit);
  datatype *x = (datatype *)malloc(sizeof(*x));
  queue_de(&q,x);
  printf("  :%d,    =%d
", *x, queue_len(q));
  printf("  6   
");
  queue_en(&q, 6);
  printf("length=%d
", queue_len(q));
  queue_traverse(q,visit);
  datatype *e = (datatype *)malloc(sizeof(*e));
  queue_de(&q,e);
  printf("queue_de(),e=%d length=%d
", *e,  queue_len(q));
  queue_traverse(q, visit);
  queue_clear(&q);
  queue_traverse(q, visit);
  printf("length:%d
", queue_len(q));
}

캡 처 실행:

읽 어 주 셔 서 감사합니다. 여러분 에 게 도움 이 되 기 를 바 랍 니 다.본 사이트 에 대한 여러분 의 지지 에 감 사 드 립 니 다!