자료구조 (연결 큐)

---

참고자료

 

https://jung-story.tistory.com/25

자료구조 (원형 큐)

 

---

개요

이번에는 자료구조의 큐 알고리즘에 대해서 연결로 구현 하는 것을 알아 보도록 하겠습니다. 

 

---

큐(Queue) 란?

 

큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말하는데, 이와 같은 알고리즘은 실생활에서 놀이기구의 줄을 서는 방식으로 설명 할 수 있다. 

큐는 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념입니다.

프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용이 됩니다.

 

---

연결 큐 구현

 

#include <stdio.h>
typedef char element;
typedef struct QNode {
	element data;
	struct QNode* link;
}QNode;
typedef struct {
	QNode* front, * rear;
}LQueueType;

LQueueType* createLinkQueue() {
	LQueueType* LQ;
	LQ = malloc(sizeof(LQueueType));
	LQ->front = NULL;
	LQ->front = NULL;
	return LQ;
}
int isEmpty(LQueueType* LQ) {
	if (LQ->front == NULL) {
		printf("비어있음");
		return 1;
	}
	else {
		return 0;
	}
}
void enQueue(LQueueType* LQ, element item) {
	QNode* newNode = malloc(sizeof(QNode));
	newNode->data = item;
	newNode->link = NULL;
	if (LQ->front == NULL) {
		LQ->front = newNode;
		LQ->rear = newNode;
	}
	else {
		LQ->rear->link = newNode;
		LQ->rear = newNode;	// 마지막 노드가 변경되었으므로 마지막의 값을 변경해준다!
	}
}
element deQueue(LQueueType* LQ) {
	QNode* old = LQ->front;
	element item;
	if (isEmpty(LQ)) {
		return 0;
	}
	else {
		item = old->data;
		LQ->front = LQ->front->link;
		if (LQ->front == NULL)
			LQ->rear = NULL;
		free(old);
		return item;
	}
}
void printLQ(LQueueType* LQ) {
	QNode* temp = LQ->front;
	while (temp) {
		printf("%3c", temp->data);
		temp = temp->link;
	}
}
void main() {
	LQueueType* LQ = createLinkQueue();
	element data;
	enQueue(LQ, 'A');
	enQueue(LQ, 'B');
	enQueue(LQ, 'C');
	enQueue(LQ, 'D');
	printLQ(LQ);
	deQueue(LQ);
	printf("\n-------------------------\n");
	printLQ(LQ);
}

 

---

실행 화면

 

삽입 후 삭제

 

---