[데이터 구조] 제3 장 - 창고 와 대열 (독서 노트 3)

제3 장 - 창고 와 대열
□ 3.4 대기 열 은 스 택 과 달리 대기 열 (queue) 은 먼저 나 오 는 (first in first out) 선형 표 로 표 의 한 끝 에 만 삽입 할 수 있 고 다른 한 끝 에 요 소 를 삭제 할 수 있다.대기 열 에 삽입 할 수 있 는 한 끝 을 팀 끝 (rear) 이 라 고 하고 삭제 할 수 있 는 한 끝 을 팀 머리 (front) 라 고 합 니 다.대기 열 은 프로그램 관련 에서 도 자주 나타난다.가장 전형 적 인 예 는 운영 체제 의 작업 줄 을 서 는 것 이다.2 단 대기 열 (deque): 스 택 과 대기 열 을 제외 하고 한 정 된 데이터 구 조 는 2 단 대기 열 입 니 다.이것 은 표 의 양 끝 에 삽입 과 삭 제 를 제한 하 는 선형 표 입 니 다.
□ 3.4.2 체인 대기 열 - 대기 열의 체인 표시 와 실현 을 체인 으로 표시 하 는 대기 열 을 체인 대기 열 이 라 고 약칭 한다.하나의 체인 대열 은 분명히 두 개의 지시 팀 머리 와 팀 꼬리 의 지침 이 있어 야만 유일 하 게 확정 할 수 있다.체인 큐 의 작업 은 단일 체인 시트 의 삽입 과 삭제 작업 의 특수 한 상황 입 니 다. 다만 꼬리 지침 이나 머리 지침 을 수정 해 야 합 니 다.

typedef int QElemType;
/*----------------------------------------
       
------------------------------------------*/
typedef struct QNode{/*    */
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;

typedef struct{
	/*                   */
	QueuePtr front,rear; /*   、     */
}LinkQueue;

Status InitQueue(LinkQueue *Q)
{ /*        Q */
	(*Q).front = (*Q).rear = (QueuePtr)malloc(sizeof(QNode));
	if(!(*Q).front){
		exit(OVERFLOW);
	}
	(*Q).front->next = NULL;
	return OK;
}
Status DestroyQueue(LinkQueue *Q)
{ /*     Q(      ) */
	QueuePtr p = NULL;
	while((*Q).front){
		p = (*Q).front->next;
		free((*Q).front);
		(*Q).front = p;
	}
	return OK;
}
Status ClearQueue(LinkQueue *Q)
{ /*  Q      */
	QueuePtr p = NULL;
	QueuePtr q = NULL;
	(*Q).rear = (*Q).front;
	p = (*Q).front->next;
	(*Q).front->next = NULL;
	while (p){
		q = p;
		p = p->next;
		free(q);
	}
	return OK;
}
Status QueueEmpty(LinkQueue Q)
{ /*  Q    ,   TRUE,    FALSE */
	if(Q.front == Q.rear){
		return TRUE;
	}
	else{
		return FALSE;
	}
}
int QueueLength(LinkQueue Q)
{ /*        */
	int count = 0;
	QueuePtr p = Q.front;
	while (Q.rear != p){
		p = p->next;
		count++;;
	}
	return count;
}
Status EnQueue(LinkQueue *Q, QElemType e)
{ /*     e Q        */
	QueuePtr p = NULL;
	p = (QueuePtr)malloc(sizeof(QNode));
	p->data = e;
	p->next = NULL;
	(*Q).rear->next = p;
	(*Q).rear = p;
	return OK;
}

Status DeQueue(LinkQueue *Q, QElemType *e)
{ /*      ,  Q     , e    ,   OK,    ERROR */
	QueuePtr p = NULL;
	if ((*Q).front == (*Q).rear){
		return ERROR;
	}
	p = (*Q).front->next;
	*e = p->data;
	(*Q).front->next = p->next;
	if ((*Q).rear == p){
		(*Q).rear = (*Q).front;
	}
	free(p);
	p = NULL;
	return OK;
}
Status QueueTraverse(LinkQueue Q,void(*vi)(QElemType))
{ /*            Q         vi()。  vi  ,      */
	QueuePtr p = NULL;
	p = Q.front->next;
	while(p){
		vi(p->data);
		p = p->next;
	}
	printf("
");
	return OK;
}
Status GetHead_Q(LinkQueue Q, QElemType *e) /*    bo2-6.c   */
{ /*      ,  e  Q     ,   OK,    ERROR */
	QueuePtr p = NULL;
	if (Q.front == Q.rear){
		return ERROR;
	}
	p = Q.front->next;
	*e = p->data;
	return OK;
}
void visit(QElemType i)
{
	printf("%d ",i);
}
int _tmain(int argc, _TCHAR* argv[])
{
	int i;
	QElemType d;
	LinkQueue q;
	i=InitQueue(&q);
	if(i){
		printf("           !
");
	}
	printf("     ？%d(1:  0: )  ",QueueEmpty(q));
	printf("      %d
",QueueLength(q));
	EnQueue(&q,-5);
	EnQueue(&q,5);
	EnQueue(&q,10);
	printf("  3   (-5,5,10) ,      %d
",QueueLength(q));
	printf("     ？%d(1:  0: )  ",QueueEmpty(q));
	printf("        ：");
	QueueTraverse(q,visit);
	i = GetHead_Q(q,&d);
	if(i == OK){
		printf("     ：%d
",d);
	}
	DeQueue(&q,&d);
	printf("       %d
",d);
	i = GetHead_Q(q,&d);
	if(i == OK){
		printf("       ：%d
",d);
	}
	ClearQueue(&q);
	printf("     ,q.front=%u q.rear=%u q.front->next=%u
",q.front,q.rear,q.front->next);
	DestroyQueue(&q);
	printf("     ,q.front=%u q.rear=%u
",q.front, q.rear);
	return 0;
}

□ 3.4.3 순환 대기 열 - 대기 열의 순서 표시 와 실현 은 대기 열의 순서 저장 구조 에서 한 그룹의 주소 로 연속 적 인 저장 장치 로 대기 열 머리 에서 대기 열 꼬리 까지 의 요 소 를 순서대로 저장 하 는 것 을 제외 하고 두 개의 포인터 front 와 rear 를 추가 하여 각각 대기 열 머리 요소 와 대기 열 꼬리 요소 의 위 치 를 표시 해 야 한다.대기 열 헤드 포인터 로 대기 열 꼬리 포인터 의 다음 위치 (반지 위의 다음 위치) 에 대기 열 이 가득 찬 상태 로 표 시 됩 니 다.C 언어 에 서 는 동적 으로 분 배 된 1 차원 배열 로 순환 대기 열 을 실현 할 수 없습니다.사용자 의 프로그램 에 순환 대기 열 이 설치 되 어 있다 면 최대 대기 열 길 이 를 설정 해 야 합 니 다.사용자 가 사용 하 는 대기 열의 최대 길 이 를 예측 할 수 없다 면 체인 대기 열 을 사용 하 는 것 이 좋 습 니 다.

/*---------------------------------------------
    
---------------------------------------------*/
typedef int QElemType;
/*       (      ，        1) */
#define MAXSIZE 5
typedef struct {
	QElemType *base;	/*              */
	int rear;			/*    ,     ,        */
	int front;			/*    ,     ,              */
}SqQueue;

/* bo3-3.c     (     c3-3.h  )     (9 ) */
Status InitQueue(SqQueue *Q)
{ /*        Q */
	(*Q).base = (QElemType *)malloc(MAXSIZE * sizeof(QElemType) );
	if(!(*Q).base){ /*        */
		exit(OVERFLOW);
	}
	(*Q).front = (*Q).rear = 0;
	return OK;
}
Status DestroyQueue(SqQueue *Q)
{ /*     Q,Q     */
	if((*Q).base){ 
		free((*Q).base);
	}
	(*Q).base = NULL;
	(*Q).front = (*Q).rear = 0;
	return OK;
}
Status ClearQueue(SqQueue *Q)
{ /*  Q      */
	(*Q).front = (*Q).rear = 0;
	return OK;
}
Status QueueEmpty(SqQueue Q)
{ /*    Q    ,   TRUE,    FALSE */
	if(Q.front==Q.rear){ /*        */
		return TRUE;
	}
	else{
		return FALSE;
	}
}
int QueueLength(SqQueue Q)
{ /*   Q     ,       */
	return ( Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}
Status GetHead(SqQueue Q,QElemType *e)
{ /*      ,  e  Q     ,   OK,    ERROR */
	if(Q.front == Q.rear){
		return ERROR;
	}
	*e = *(Q.base + Q.front);
	return OK;
}
Status EnQueue(SqQueue *Q,QElemType e)
{ /*     e Q        */
	/*      */
	if (((*Q).rear + 1) % MAXSIZE == (*Q).front ){
		return ERROR;
	}
	(*Q).base[(*Q).rear] = e;
	(*Q).rear = ((*Q).rear + 1) % MAXSIZE;
	return OK;
}
Status DeQueue(SqQueue *Q,QElemType *e)
{ /*      ,   Q     , e    ,   OK;    ERROR */
	if ((*Q).rear == (*Q).front){/*      */
		return ERROR;
	}
	*e = (*Q).base[(*Q).front];
	(*Q).front = ((*Q).front + 1) % MAXSIZE;
	return OK;
}
Status QueueTraverse(SqQueue Q,void(*vi)(QElemType))
{ /*            Q         vi().  vi  ,      */
	int pos = Q.front;
	while (pos != Q.rear){
		vi(Q.base[pos]);
		pos = (pos + 1) % MAXSIZE;
	}
	printf("
");
	return OK;
}

void visit(QElemType i)
{
	printf("%d ",i);
}

int _tmain(int argc, _TCHAR* argv[])
{
   Status j;
   int i=0,l;
   QElemType d;
   SqQueue Q;
   InitQueue(&Q);
   printf("      ，    ？%u(1:  0: )
",QueueEmpty(Q));
   printf("         (   %d ),-1      : ",MAXSIZE-1);
   do
   {
     scanf("%d",&d);
     if(d==-1)
       break;
     i++;
     EnQueue(&Q,d);
   }while(i<MAXSIZE-1);
   printf("     : %d
",QueueLength(Q));
   printf("      ？%u(1:  0: )
",QueueEmpty(Q));
   printf("  %d        ,      :
",MAXSIZE);
   for(l=1;l<=MAXSIZE;l++)
   {
     DeQueue(&Q,&d);
     printf("      %d,         : ",d);
     scanf("%d",&d);
     EnQueue(&Q,d);
   }
   l=QueueLength(Q);
   printf("         : 
");
   QueueTraverse(Q,visit);
   printf("       %d   
",i+MAXSIZE);
   if(l-2>0)
     printf("       %d   :
",l-2);
   while(QueueLength(Q)>2)
   {
     DeQueue(&Q,&d);
     printf("       %d
",d);
   }
   j=GetHead(Q,&d);
   if(j)
     printf("       : %d
",d);
   ClearQueue(&Q);
   printf("     ,     ？%u(1:  0: )
",QueueEmpty(Q));
   DestroyQueue(&Q);
	return 0;
}