열혈 자료구조 - 7-3 큐의 연결 리스트 기반 구현

연결 리스트 기반의 큐 구현

- 구조체 정의

typedef struct _node
{
	Data data;
	struct _node * next;
} Node;

typedef struct _lQueue
{
	Node * front;		// 삭제를 위한 노드 포인터
	Node * rear;		// 삽입을 위한 노드 포인터
} LQueue;

- 초기화

void QueueInit(Queue * pq)
{
	pq->front = NULL;
	pq->rear = NULL;
}

- 비어있는지 확인

    -> rear는 볼 필요 없이 front만으로 비어있는지 판단

    -> 노드가 삽입 후 모두 삭제하면 front는 null로 설정되게 정의하기 때문에 front만 비교

int QIsEmpty(Queue * pq)
{
	if(pq->front == NULL)	
		return TRUE;
	else
		return FALSE;
}

- 삽입

    -> 첫 삽입때는 front와 rear 모두 new node를 가르키고 그 이후에는 rear는 새 new node를 가르킴

    -> 첫 삽입 때 바로 rear는 new node를 가르키고 QIsEmpty에도 front만 비교하기 때문에 굳이 rear를 NULL로 초기화 할 필요는 없음

void Enqueue(Queue * pq, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->next = NULL;
	newNode->data = data;

	if(QIsEmpty(pq))
	{
		pq->front = newNode;
		pq->rear = newNode;
	} // 비어있었으면(첫 삽입) front와 rear 모두 새 노드를 가르킴
	else
	{
		pq->rear->next = newNode;
		pq->rear = newNode;
	} // 마지막으로 rear 였던 노드의 next에 새 노드를 설정
}

- 데이터 조회(삭제 O)

    -> 모두 삭제를 하면 front는 NULL을 가르키지만 rear는 쓰레기 값을 가지게 됨

    -> 그렇기 때문에 QIsEmpty에서 front만 비교하는 것이 맞음

Data Dequeue(Queue * pq)
{
	Node * delNode;
	Data retData;

	if(QIsEmpty(pq))
	{
		printf("Queue Memory Error!");
		exit(-1);
	} // 비어있으면 종료

	delNode = pq->front;		// 현재 front의 노드를 따로 저장
	retData = delNode->data;
	pq->front = pq->front->next;	// front를 현재 front의 next로 설정

	free(delNode);		// 삭제(소멸)
	return retData;
}

- 데이터 조회(삭제 X)

Data QPeek(Queue * pq)
{
	if(QIsEmpty(pq))
	{
		printf("Queue Memory Error!");
		exit(-1);
	}

	return pq->front->data;		// 현재 front의 데이터를 반환
}