JArchive 프로그래밍 일기

링크드 큐 

링크드 리스트로 만든 큐입니다.

배열로 만든 순환 큐와는 달리 공백/포화를 구분할 필요가 없습니다. 

head 노드에서 제거하고, tail 노드에서 삽입합니다. 

노드 선언과 큐 

노드는 링크드 리스트의 노드와 똑같습니다. 

링크드 큐 구조체는 전단과 후단을 가리킬 포인터와 총 노드 개수 변수를 가집니다. 

typedef struct Node {
	char* data;
	struct Node* nextNode;
};

typedef struct LQ {
	struct Node* front;
	struct Node* rear;
	int nodeCnt;
};

노드 생성과 메모리 해제

void CreateQueue(LQ** lq) {

	(*lq) = (LQ*)malloc(sizeof(LQ));
	(*lq)->front = NULL;
	(*lq)->rear = NULL;
	(*lq)->nodeCnt = 0;
}

삽입

/* 후단에 삽입 */
void Enqueue(LQ* lq, Node* newNode) {

	if (NULL == lq->front) {
		lq->front == newNode;
		lq->rear == newNode;
	}
	else {
		lq->rear->nextNode = newNode;
		lq->rear = newNode;
	}

	lq->nodeCnt++;

}

제거 

/* 전단에서 제거 */
Node* Dequeue(LQ* lq) {

	Node* out = lq->front;

	if (NULL == lq->front->nextNode) {
		lq->front = NULL;
		lq->rear = NULL;
	}
	else {
		lq->front = lq->front->nextNode;
	}

	lq->nodeCnt--;

	return out;
}