C 언어 구현 대기 열 및 기본 동작 +

대열 1. 대기 열의 정의 와 기본 연산 스 택 은 후진 선 출 데이터 구조 로 실제 문제 에서 '선진 선 출' 의 데이터 구 조 를 자주 사용 합 니 다. 즉, 표 한 끝 에 삽입 하여 진행 하고 표 의 다른 한 끝 에 삭제 하여 진행 합 니 다. 이런 데이터 구 조 를 팀 또는 대기 열 이 라 고 부 르 고 삽입 할 수 있 는 한 끝 을 팀 꼬리 (rear) 라 고 부 르 며 삭제 할 수 있 는 한 끝 을 팀 머리 (front) 라 고 부 릅 니 다.둘. 대기 열의 저장 실현 과 연산 실현 은 선형 표, 스 택 과 유사 하고 대기 열 에 도 순서 저장 과 체인 저장 두 가지 저장 방법 이 있다.1. 순서 대기 열 순환 대기 열의 유형 정 의 는 다음 과 같다.

#define MAXQSIZE 100 //      
typedef struct {
QElemType *base; //        
int front; //   ，     ，       
int rear; //   ，     ，             
} SqQueue;

다음은 순환 대기 열의 기본 조작의 실현 이다.(1) 입대:

int EnQueue (SqQueue &Q, QElemType e) {
if((Q.rear+1)%MAXQSIZE == Q.front) return ERROR;
Q.base[Q.rear] = e;
Q.rear = (Q.rear+1) % MAXQSIZE;
return OK;
}

(2) 출전:

int DeQueue (SqQueue &Q, QElemType &e) {
if (Q.front = = Q.rear) return ERROR;
e = Q.base[Q.front];
Q.front = (Q.front+1) % MAXQSIZE;
return OK;
}

(3) 순환 대기 열 요소 개수 구하 기:

int QueueLength（SqQueue Q）{
return (Q.rear-Q.front+MAXQSIZE) %MAXQSIZE；
}

2. 체인 큐 체인 식 으로 저 장 된 팀 을 체인 큐 라 고 합 니 다.체인 스 택 과 유사 하 게 단일 체인 표 로 체인 대열 을 실현 하고 팀 의 선진 적 인 선 출 원칙 에 따라 조작 상의 편 의 를 위해 각각 머리 지침 과 꼬리 지침 이 필요 합 니 다.체인 대기 열의 형식 설명 은 다음 과 같 습 니 다.

typedef struct QNode { //     
QElemType data;
struct QNode *next;
} QNode, *QueuePtr;
typedef struct { //     
QueuePtr front; //    
QueuePtr rear; //    
} LinkQueue;

체인 대기 열 을 가리 키 는 지침 을 정의 합 니 다: LinkQueue Q;다음은 체인 대기 열의 기본 연산 의 실현 이다.(1) 입대

int EnQueue (LinkQueue &Q, QElemType e) {
QNode *p;
p = （QNode *）malloc（sizeof（QNode））;
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}

(2) 출대

int DeQueue (LinkQueue &Q, QElemType &e) {
if (Q.front == Q.rear) return ERROR; //  ，    
p = Q.front->next;
e = p->data; //      e  
Q.front->next = p->next;
if(Q.rear==p) Q.rear= Q.front; //       ，          
free (p);
return OK;
}

3. 스 택 과 대기 열 을 제외 하고 한 정 된 데이터 구 조 는 쌍 단 대기 열 입 니 다.(1) 양 끝 대기 열: 양 끝 에 삽입 하고 삭제 할 수 있 는 선형 표 입 니 다.(2) 제 한 된 양 끝 대기 열 을 입력 하 십시오. 선형 표 의 양 끝 은 모두 데이터 요 소 를 출력 할 수 있 지만 한 끝 에 만 데이터 요 소 를 입력 할 수 있 습 니 다.(3) 출력 이 제 한 된 양 끝 대기 열: 선형 표 의 양 끝 에 데이터 요 소 를 입력 할 수 있 지만 한 끝 에 만 데이터 요 소 를 출력 할 수 있 습 니 다.