[데이터 구조] 선형 순환 대기 열

선형 대기 열 과 선형 스 택 은 약간 비슷 하지만 대기 열 안의 데 이 터 는 '선진 선 출' 입 니 다.실제 응용 할 때 대부분 순환 대기 열 을 사용 합 니 다. 대기 열의 순환 실현 에 대해 두 가지 일 을 경계해 야 합 니 다. 1. 대기 열 이 비어 있 는 지 확인 해 야 합 니 다.2. 대기 열 이 가득 찼 는 지 확인 합 니 다.다음은 순환 대기 열의 기본 동작 을 간단하게 소개 합 니 다.
1. 대기 열의 데이터 노드
typedef struct _Queue
{
	int *pData;       //     
	int capacity;     //    
	int front;        //     
	int rear;         //     
	int count;        //     
}Queue;

2. 지정 한 용량 대기 열 생 성
Queue* createQueue(int num)
{
	Queue *pQueue = NULL;
	if (0 == num)
		return NULL;

	pQueue = (Queue *)malloc(sizeof(Queue));  //      
	assert(NULL != pQueue);
	memset(pQueue, 0, sizeof(Queue));

	pQueue->pData = (int *)malloc(sizeof(int)* num);   //       
	if (NULL == pQueue->pData)
	{
		free(pQueue);          //       ,        
		pQueue = NULL;
		return NULL;
	}
	pQueue->capacity = num;    //    

	return pQueue;
}

3. 대기 열 이 비어 있 음, 가득 찼 음 을 판단 합 니 다.
bool isFull(Queue *pQueue)
{
	return (pQueue->count == pQueue->capacity);
}

bool isEmpty(Queue *pQueue)
{
	return (0 == pQueue->count);
}

4. 대열 에 들어간다
선형 순환 대기 열 등 효 과 는 데이터 필드 가 하나의 링 의 배열 공간 이 라 고 생각 합 니 다. 이렇게 대기 열 에 들 어 갈 때 대기 열 끝 위치 (실제 대기 열 은 엄격 한 수미 의 구분 이 없 음) 는 (rear + 1) mod capacity 입 니 다.단순 한 추가 처리 가 아니 라
bool enQueue(Queue *pQueue, int value)
{
	if (NULL == pQueue)
		return false;

	if (isFull(pQueue))
		return false;

	pQueue->pData[pQueue->rear] = value;
	pQueue->rear = (pQueue->rear + 1) % pQueue->capacity;
	pQueue->count++;

	return true;
}

5. 대열 에 나가다
4. 567913. 대기 열의 특징 을 파악 하고 대기 열 을 나 갈 때 팝 업 대기 열 전단 데이터 입 니 다.
6. 대기 열 방출
2 급 포인터 로 전달 하 는 것 은 메모 리 를 방출 한 후에 대기 열 지침 을 NULL 로 설정 하여 이후 의 기본 동작 에 편리 한 매개 변수 판단 입 니 다.1 단 포인터 사용 시 메모리 사용 가능
bool deQueue(Queue *pQueue, int *value)
{
	if (NULL == pQueue)
		return false;

	if (isEmpty(pQueue))
		return false;

	*value = pQueue->pData[pQueue->front];
	pQueue->count--;
	pQueue->front = (pQueue->front + 1) % pQueue->capacity;

	return true;
}

7, 인쇄 대기 열 데이터
4. 567913. 디자인 순환 대기 열 데이터 구조 가 비교적 간단 하 므 로 주의해 야 할 것 은 데이터 도 메 인 순환 의 '링' 처리 이다.

좋은 웹페이지 즐겨찾기