상세 한 데이터 구조 C 언어 구현 순환 대기 열

본문 에서 말 하 는 것 은 순환 대열 이다.우선 우 리 는 아래 의 몇 가지 문 제 를 이해 해 야 한다.
순환 대열 의 기초 지식
1.순환 대기 열 은 몇 개의 인자 가 필요 합 니까?
순환 대기 열 은 2 개의 인자,front 와 rear 가 필요 합 니 다.
2.순환 대기 열 매개 변수의 의미
(1)대기 열 이 초기 화 될 때 front 와 rear 값 은 0 입 니 다.
(2)대기 열 이 비어 있 지 않 을 때 front 는 대기 열의 첫 번 째 요 소 를 가리 키 고 rear 는 대기 열의 마지막 요소 의 다음 위 치 를 가리킨다.
(3)대기 열 이 비어 있 을 때 front 는 rear 의 값 과 같 지만 0 이 아 닙 니 다.
3.순환 대기 열 입 대 를 위 한 알고리즘
(1)값 을 rear 가 있 는 위치 에 저장 합 니 다.
(2)rear=（rear+1）%maxsize 그 중에서 maxsize 는 배열 의 길 이 를 나타 낸다.
프로그램 코드:

bool Enqueue(PQUEUE Q, int val) 
{ 
  if(FullQueue(Q)) 
    return false; 
  else 
  { 
    Q->pBase[Q->rear]=val; 
    Q->rear=(Q->rear+1)%Q->maxsize; 
    return true; 
  } 
} 

4.순환대 목록 의 위조 알고리즘
(1)먼저 팀 의 값 을 저장 합 니 다.
(2)front=（front+1）%maxsize 그 중에서 maxsize 는 배열 의 길 이 를 나타 낸다.
프로그램 코드:

bool Dequeue(PQUEUE Q, int *val) 
{ 
  if(EmptyQueue(Q)) 
  { 
    return false; 
  } 
  else 
  { 
    *val=Q->pBase[Q->front]; 
    Q->front=(Q->front+1)%Q->maxsize; 
    return true; 
  } 
} 

5.순환 대기 열 이 비어 있 는 지 여 부 를 어떻게 판단 합 니까?if（front==rear）대기 열 이 비어 있 음;else  대기 열 이 비어 있 지 않 음;

bool EmptyQueue(PQUEUE Q) 
{ 
  if(Q->front==Q->rear)  //       
    return true; 
  else 
    return false; 
} 

6.순환 대기 열 이 가득 찼 는 지 여 부 를 어떻게 판단 합 니까?

 이 문 제 는 비교적 복잡 하 다.만약 에 배열 의 저장 공간 이 7 이 라 고 가정 하면 이때 1,a,5,7,22,90 여섯 개의 요 소 를 저장 했다.만약 에 배열 에 하나의 요 소 를 추가 하면 4,567914.이때 대열 이 가득 찬 것 은 대열 이 비어 있 는 판단 조건 과 4,567914.같다.그러면 우 리 는 대열 이 비어 있 는 지 가득 찬 지 판단 할 수 없다.
이 문 제 를 해결 하 는 데 는 두 가지 방법 이 있다.
하 나 는 배열 의 현재 요소 의 개 수 를 기록 하 는 매개 변 수 를 추가 하 는 것 이다.
두 번 째 방법 은 하나의 저장 공간,즉 배열 의 마지막 저장 공간 을 적 게 사용 하 는 것 이다.4.567914 일 때 대기 열 이 가득 하 다.

bool FullQueue(PQUEUE Q) 
{ 
  if(Q->front==(Q->rear+1)%Q->maxsize)  //         ，          
    return true; 
  else 
    return false; 
} 

부록:
queue.h 파일 코드:

#ifndef __QUEUE_H_ 
#define __QUEUE_H_ 
typedef struct queue  
{ 
  int *pBase; 
  int front;  //          
  int rear;  //                 
  int maxsize; //            
}QUEUE,*PQUEUE; 
 
void CreateQueue(PQUEUE Q,int maxsize); 
void TraverseQueue(PQUEUE Q); 
bool FullQueue(PQUEUE Q); 
bool EmptyQueue(PQUEUE Q); 
bool Enqueue(PQUEUE Q, int val); 
bool Dequeue(PQUEUE Q, int *val); 
#endif 

queue.c 파일 코드:

#include<stdio.h> 
#include<stdlib.h> 
#include"malloc.h" 
#include"queue.h" 
/*********************************************** 
Function: Create a empty stack; 
************************************************/ 
void CreateQueue(PQUEUE Q,int maxsize) 
{ 
  Q->pBase=(int *)malloc(sizeof(int)*maxsize); 
  if(NULL==Q->pBase) 
  { 
    printf("Memory allocation failure"); 
    exit(-1);    //     
  } 
  Q->front=0;     //      
  Q->rear=0; 
  Q->maxsize=maxsize; 
} 
/*********************************************** 
Function: Print the stack element; 
************************************************/ 
void TraverseQueue(PQUEUE Q) 
{ 
  int i=Q->front; 
  printf("      :
"); 
  while(i%Q->maxsize!=Q->rear) 
  { 
    printf("%d ",Q->pBase[i]); 
    i++; 
  } 
  printf("
"); 
} 
bool FullQueue(PQUEUE Q) 
{ 
  if(Q->front==(Q->rear+1)%Q->maxsize)  //         ，          
    return true; 
  else 
    return false; 
} 
bool EmptyQueue(PQUEUE Q) 
{ 
  if(Q->front==Q->rear)  //       
    return true; 
  else 
    return false; 
} 
bool Enqueue(PQUEUE Q, int val) 
{ 
  if(FullQueue(Q)) 
    return false; 
  else 
  { 
    Q->pBase[Q->rear]=val; 
    Q->rear=(Q->rear+1)%Q->maxsize; 
    return true; 
  } 
} 
 
bool Dequeue(PQUEUE Q, int *val) 
{ 
  if(EmptyQueue(Q)) 
  { 
    return false; 
  } 
  else 
  { 
    *val=Q->pBase[Q->front]; 
    Q->front=(Q->front+1)%Q->maxsize; 
    return true; 
  } 
} 

이상 은 C 언어 가 순환 대기 열 을 실현 하 는 모든 내용 으로 데이터 구조 와 알고리즘 에 대한 연구 에 도움 이 되 고 필요 한 친구 가 참고 할 수 있 습 니 다.