이번에는 연결리스트를 사용하여 큐를 구현해보겠습니다.
큐에 대한 개념은 이전 게시물을 참조해주세요.
이전 게시물 링크 => 2020/03/04 - [공부/c언어 자료구조] - [자료구조 C 언어] C 프로그래밍 자료구조 - 5 : 배열을 사용한 큐 (Queue)
바로 전체 코드와 함께 설명드리겠습니다.
1. 연결리스트를 사용한 큐 구현
이 색상의 주석은 제가 코드를 구현할 때 추가한 주석입니다.
이 색상의 주석은 게시물을 작성하며 추가한 주석입니다.
#include <stdio.h>
#include <stdlib.h>
typedef struct NODE{ // 기본 NODE 구조체는 연결리스트와 동일합니다.
struct NODE *next;
int data;
} Node;
typedef struct QUEUE{ // 큐에 가장 처음 삽입된 데이터를 가리키는 front와
가장 마지막에 삽입된 데이터를 가리키는 rear를 포함하는 구조체입니다.
Node *front;
Node *rear;
int size;
} Queue;
Queue *InitQueue(void){ // QUEUE 구조체 포인터를 초기화 합니다.
Queue *queue = (Queue *)malloc(sizeof(Queue));
queue->front = queue->rear = NULL; // front와 rear 모두 NULL로 초기화 합니다.
queue->size = 0;
return queue;
}
void ResetQueue(Queue *queue){ // 큐의 저장된 모든 노드를 해제하고, 큐를 초기화 합니다.
Node *tmp;
Node *cur;
cur = queue->front; // cur은 큐에 저장된 연결리스트 노드 중 가장 처음 저장된 노드와 동일합니다.
while(cur != NULL){
tmp = cur->next; // tmp에 현재 cur에 저장된 노드의 다음 노드를 저장합니다.
free(cur); // 현재 cur에 저장된 노드에 동적할당된 메모리를 해제합니다.
cur = tmp; // cur은 다음 노드와 동일해집니다.
}
queue->front = queue->rear = cur;
queue->size = 0;
}
void Add(Queue *queue, int data){ // 큐에 원하는 데이터를 저장합니다.
Node *tmp = (Node *)malloc(sizeof(Node));
tmp->data = data; // 임시 구조체 포인터 tmp에 데이터를 저장합니다.
tmp->next = NULL; // tmp의 next는 NULL 가리킵니다.
if(queue->size == 0){ // size가 0일 때는 front를 바로 tmp와 동일하게 만들어줍니다.
queue->front = tmp; // 이때는 front는 tmp와 동일해지고, rear는 여전히 NULL을 가리킵니다.
}
else{ // size가 0이 아닐 때, 즉, front에 데이터가 저장되어 있을 때 입니다.
queue->rear->next = tmp; // front의 반대 방향으로 화살표 (next)를 보낸다.
} // rear의 next가 tmp를 가리키도록 합니다.
// rear는 바로 아래 코드에서 tmp와 동일해지기 때문에 이전 tmp의 next가 새로 만들어진 tmp를 가리키는 것과 동일한 역할을 합니다.
queue->rear = tmp; // front랑 관계없이 (front에는 size가 0일 때 저장한 주소가 할당되어있다.)
// rear는 tmp와 동일하게 됩니다.
// 스텍과 헷갈리면 안 되는 중요한 점은 rear의 next는 항상 NULL을 가리킵니다.
// 아래 Delete 함수에서 front에서부터 원하는 갯수만큼 큐에 저장된 노드의 데이터가 반환되며 삭제됩니다.
++queue->size;
}
void Delete(Queue *queue, int num){
Node *cur;
Node *tmp;
cur = queue->front; // cue는 큐의 제일 윗 노드와 동일합니다. (가장 마지막에 들어온 추가된 노드)
int size = queue->size;
puts("");
while(num--){
if(cur == NULL){
puts("Queue is empty.\n");
break;
}
else{
printf("Deleted queue (%d) data = %d.\n", size +1 - (queue->size--), cur->data);
// 데이터를 반환한 노드의 메모리를 해제하는 부분은 위에 ResetQueue와 동일합니다.
tmp = cur->next; // Add에서 Queue->rear->next = tmp; 해줬던 부분.
free(cur);
cur = tmp;
}
}
queue->front = cur;
}
void PrintQueue(Queue *queue){ // 큐의 모든 데이터를 출력합니다.
Node *tmp = (Node *)malloc(sizeof(Node));
tmp = queue->front;
int size = queue->size-1;
puts("\nPrinting queue starts.");
while(tmp != NULL){
printf("Queue (%d) data = %d\n", queue->size-(size--), tmp->data);
tmp = tmp->next;
}
puts("Printing queue is complete.");
}
int main(int argc, const char * argv[]) {
Queue *queue = InitQueue();
Add(queue, 11);
Add(queue, 12);
Add(queue, 13);
PrintQueue(queue);
Add(queue, 21);
Add(queue, 22);
Add(queue, 23);
PrintQueue(queue);
Delete(queue, 1);
Delete(queue, 2);
Delete(queue, 6);
return 0;
}
2. 프로그램 실행 결과
다음 게시물에선 원형 연결리스트와 이중 연결 리스트에 대해 설명드리겠습니다.