데이터 구조 초학 의 대기 열 -- 앞장 서지 않 는 단일 체인 표 로 체인 대기 열 실현

앞에서 말 했 듯 이 앞장 서지 않 는 단일 체인 표 로 체인 대열 을 실현 하 는 것 은 앞장 서 는 단일 체인 표 보다 복잡 한 점 을 실현 하 는 것 이다. 주로 대열 을 초기 화하 고 대열 에 들 어 갈 때 차이 가 있다.특히 입단 할 때 는 입단 의 첫 번 째 요소 인지 아 닌 지 에 따라 논의 해 야 한다.
1. 대열 을 초기 화하 여 팀 헤드 포인터 front 와 팀 꼬리 포인터 rear 가 비 어 있 음 을 가리 키 고, Q. front = = = NULL 시 비 어 있 음 을 가리 키 며, Q. front = = = Q. rear 로 판단 할 수 없습니다. 그렇지 않 으 면 팀 에 들 어 갈 때 Q. front = = Q. rear 라 는 조건 이 처음부터 끝까지 성립 됩 니 다. 즉, 팀 헤드 포인터 와 팀 꼬리 포인터 가 항상 새로운 결점 을 가리 키 는 것 입 니 다.3. 팀 을 나 갈 때 먼저 팀 이 비 었 는 지 여 부 를 판단 해 야 하고 팀 이 비 었 으 면 팀 을 나 갈 수 없다.체인 대기 열 에 요소 가 하나 밖 에 없 을 때 쌍 을 나 눈 후 Q. rear 를 수 동 으로 비 워 야 합 니 다. 그렇지 않 으 면 야생 포인터 (void point) 가 됩 니 다.
typedef int elementType;
typedef struct LNode {
	elementType data;
	struct LNode* next;
}node;

//       
typedef struct {
	node* front;
	node* rear;
}linkQueue;

//      
//     
void initQueue(linkQueue& Q) {
	Q.front = NULL;//         
	Q.rear = Q.front;
}

//    
bool queueEmpty(linkQueue& Q) {
	return (Q.front == NULL);
	//     Q.front == Q.rear   
}

//     
void queueFront(linkQueue& Q, elementType& x) {
	if (queueEmpty(Q))
		cout << "    ,       !";
	else {
		x = Q.front->data;
	}
}

//  
void enQueue(linkQueue& Q, elementType x) {
	node* s = new node;
	s->data = x;
	s->next = NULL;
	//             
	if (queueEmpty(Q)) {
		Q.front = s;
		Q.rear = s;
	}
	else {
		Q.rear->next = s;
		Q.rear = s;
	}
}

//  
void outQueue(linkQueue& Q, elementType& x) {
	node* s;
	if (queueEmpty(Q)) {
		cout << "    ,        !" <<endl;
	}
	else {
		s = Q.front;
		Q.front = s->next;
		x = s->data;
		delete s;

		if (Q.front == NULL)//     void point
			Q.rear = Q.front;
	}
}

//     
void printQueue(linkQueue& Q) {
	node* p = Q.front;

	cout << "     " << endl;
	while (p) {
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

//         
int queueLen(linkQueue& Q) {
	node* p = Q.front;
	int cnt = 0;
	while (p) {
		cnt++;
		p = p->next;
	}

	return cnt;
}

좋은 웹페이지 즐겨찾기