이번에는 배열을 사용해서 큐를 구현해보겠습니다.
큐 (Queue)
큐는 양 쪽이 뚫려있는 원통을 생각하면 편합니다.
한쪽으로 물건을 계속 집어넣다 보면, 반대쪽으로 제일 첨에 넣었던 물건이 밀려나오겠죠?
즉, 큐는 선입선출 혹은 FIFO (First Input First Output)입니다.
큐는 다음과 같은 구조로 되어 있습니다.
(그림 1) 데이터가 없을 때 rear는 -1을 가리킵니다.
따라서 rear+1이 front와 같을 때 큐는 비어있습니다.
(그림 2) 데이터가 하나 있을 땐 front와 rear가 첫 번째 데이터를 가리킵니다.
(그림 3) 데이터가 더 들어오면 rear의 위치가 한 칸 씩 이동하며, 해당 위치에 데이터를 저장합니다.
(그림 4) 항상 front는 제일 처음 들어온 데이터를, rear는 제밀 마지막에 들어온 데이터를 가리킵니다.
데이터는 제일 처음 들어온 데이터 (front가 가리키는 데이터) 부터 빠져나옵니다.
1) 큐의 ADT
- ADT Queue
- Create(max_size) : max_size만큼의 빈 큐를 생성
- IsFull(queue, max_size) : 꽉 찼는지 검사
- Add(queue, item) : 큐의 rear에 데이터를 삽입 하고, 큐를 반환
- IsEmpty(stack) : 비었는지 검사
- Delete(queue) : 큐의 front에 있는 item을 제거해서 반환
큐는 크게 "선형 큐 (Linear Queue)"와 "환형 큐 (Circular Queue)" 두가지 방식으로 구현됩니다.
두 가지 모두 구현 해보겠습니다.
2) 배열을 사용한 선형 큐의 구현
선형 큐는 위에서 설명한 것과 동일한 큐입니다.
직선의 원통을 생각하시면 됩니다.
밑에 그림을 보시면 이해하시기 편할 겁니다.
선형 큐 그림
선형 큐는 구현하기 매우 쉽지만 많은 문제가 있어 사용되지 않습니다.
문제는 무엇일까요?
선형 큐 그림
이와 같이 큐에 자리가 많이 남았음에도 불구하고, rear가 front 뒤에 남아있는 자리에 접근하기 힘듭니다.
그래도 한번 구현해보겠습니다.
항상 개념도 중요하지만 구현하면서 이전에 배웠던 개념을 복습하는 것이 큰 도움이 되는 것 같습니다.
2-1) 선형 큐 코드
선형 큐를 구현한 자료가 거의 없습니다.
제가 구현한 선형 큐의 목표는 정석은 아닙니다.
해당 코드의 목적은 "입력한 데이터 갯수 만큼 큐에 저장 가능하게하는 것"입니다.
즉, max_size가 없습니다.
(그림 5) 이런 식으로 저장된 큐를 다음(그림 6)과 같이 늘릴 수 있습니다.
(그림 7) 하지만 다음과 같이 앞의 데이터가 빠진 후에 빠진 자리에 데이터를 저장 할 수 없어 데이터 낭비가 심합니다.
8개념은 이렇게 마무리하고 코드 설명드리겠습니다.
#include <stdio.h> // 프로그램 최상단에 선언되어 있습니다.
#include <stdlib.h> // 함수는 실제로 선언된 순서대로 설명드립니다.
int *queue;
int front = 0;
int rear = 0;
2-2) 데이터 입력 함수 (스택에서 사용한 것과 동일합니다.)
int *InputData(void){
int *data;
int num;
printf("Insert number you want to push in stack:");
scanf("%d", &num);
printf("%d\n", num);
data = (int *)malloc(sizeof(int) * ((num)+1));
printf("Insert data you want to push in stack\n");
for(int i = 0; i < (num +1); i++){
if(i == 0){
printf("data[%d] = the number of data array\n", i);
data[0] = num;
}
else{
printf("data[%d] = ",i);
scanf("%d", &data[i]);
}
}
printf("\n");
for(int i = 0; i < (num +1); i++)
printf("data[%d] = %d\n", i, data[i]);
printf("Input process is complete.\n\n");
return data;
}
2-3) Add 함수
큐의 내부에 데이터를 저장합니다.
앞에서 입력 받은 배열을 저장해야하기 때문에 큐의 크기를 동적할당 받습니다.
rear가 1 씩 늘어나면서 그 자리에 데이터를 저장합니다.
void Add(int *val){ // val로 데이터를 받고 넣을거야 // 환형 말고 그냥으로
int num;
int *queue_temp; // 이전 큐를 저장할 임시 배열을 만들어줍니다.
queue_temp = queue;
num = val[0]; // 받을 데이터의 수
free(queue); // 이전에 동적 할당 받은 메모리를 반환해줍니다.
queue = (int *)malloc(sizeof(int) * (num+(rear-front+1)));
// 크기는 받아 올 데이터 갯수 (num) + 이전 큐에 저장된 데이터의 갯수 (rear-front+1)입니다.
puts("\nTransplant starts.");
for(int i = front; i <= rear; i++){ // front 부터 rear 까지만 데이터가 저장되어있기 때문에 그 부분만 옮겨줍니다.
queue[i] = queue_temp[i];
printf("queue[%d] = %d\n",i,queue[i]);
}
puts("Transplant is complete\n");
for(int i = 0; i < num; i++){ // rear는 -1이 초기값이므로 하나 증가시키고 val에 저장된 데이터를 받습니다.
queue[++rear] = val[i+1];
}
}
2-4) Delete 함수
원하는 갯수 만큼 저장된 큐를 출력합니다.
큐는 front 부터 (일찍 삽입한 데이터 부터) 출력됩니다.
void Delete(int num){
int *deleted_queue; // 출력할 큐를 저장할 포인터를 선언합니다.
if(front == rear + 1){ // 이전에 말했던 rear+1이 front와 같을 때 큐는 비어있습니다.
puts("Queue is empty\n");
}
else{
deleted_queue = (int *)malloc(sizeof(int) * num); // 출력할 데이터 수만큼 delete_queue에 메모리를 동적할당 합니다.
for(int i = 0; i < num; i++){
if(front == rear + 1){
puts("Queue is empty\n");
break;
}
deleted_queue[front] = queue[front];
printf("Deleted_queue[%d] = %d\n", (front),deleted_queue[front]);
front++; // 데이터를 출력한 후, front가 그 데이터 다음에 위치하도록 합니다.
}
}
}
2-5) 전체 코드 및 실행 결과
전체 코드
#include <stdio.h>
#include <stdlib.h>
int *queue;
int rear = -1;
int front = 0;
int *InputData(void){ // 넣고싶은 데이터 갯수를 입력받고, 배열을 그만큼 동적할당 받아서 배열을 반환해준다.
int *data;
int *num;
int a;
num = &a;
printf("Insert number you want to push in stack:");
scanf("%d", &a);
printf("%d\n", *num);
data = (int *)malloc(sizeof(int) * ((*num)+1)); // malloc : 할당된 메모리의 '주소'가 void* 형으로 리턴된다.
printf("Insert data you want to push in stack\n");
for(int i = 0; i < (*num+1); i++){
if(i == 0){
printf("data[%d] = the number of data array\n", i);
data[0] = *num;
}
else{
printf("data[%d] = ",i);
scanf("%d", &data[i]);
}
}
printf("\n");
for(int i = 0; i < (*num+1); i++)
printf("data[%d] = %d\n", i, data[i]);
printf("Input process is complete.\n");
return data;
}
void Add(int *val){ // val로 데이터를 받고 넣을거야 // 환형 말고 그냥으로
int num;
int *queue_temp;
queue_temp = queue;
num = val[0]; // 받을 데이터의 수
free(queue);
queue = (int *)malloc(sizeof(int) * (num+(rear+1)));
puts("\nTransplant starts.");
for(int i = front; i <= rear; i++){
queue[i] = queue_temp[i];
printf("queue[%d] = %d\n",i,queue[i]);
}
puts("Transplant is complete\n");
for(int i = 0; i < num; i++){
queue[++rear] = val[i+1];
}
}
void Delete(int num){
int *deleted_queue;
if(front == rear + 1){
puts("Queue is empty\n");
}
else{
deleted_queue = (int *)malloc(sizeof(int) * num);
for(int i = 0; i < num; i++){
if(front == rear + 1){
puts("Queue is empty\n");
break;
}
deleted_queue[front] = queue[front];
printf("Deleted_queue[%d] = %d\n", (front),deleted_queue[front]);
front++;
}
}
}
void PrintQueue(void){
if(front == rear+1){
printf("Queue is empty.\n");
}
else{
int num = front;
while(num != rear+1){
printf("Queue[%d] = %d.\n", num, queue[num]);
num++;
}
}
printf("\n");
}
int main(void){
Add(InputData());
PrintQueue();
Add(InputData());
PrintQueue();
Delete(4);
Delete(2);
Add(InputData());
PrintQueue();
return 0;
}
실행결과
데이터를 넣고 (4개 -> 3개, 총 7개), 큐에 저장된 데이터가 잘 출력되는 것을 확인할 수 있습니다.
사용자가 원하는 갯수만큼의 데이터 (4개 -> 2개)를 큐에서 잘 빼낸 것을 확인할 수 있습니다.
이전 큐에 남은 데이터 (queue[6] == 23)에 추가로 사용자가 원하는 데이터 3개를 큐에 저장한 것을 확인할 수 있습니다.
다음 게시물에선 연결 리스트에 대해 설멸드리겠습니다.
'Programming > C' 카테고리의 다른 글
| [자료구조 C 언어] C 프로그래밍 자료구조 - 6 - 1 : 연결리스트 (Linked List) (추가, 삽입, 삭제, 검색, 뒤집기 등) (0) | 2020.03.05 |
|---|---|
| [자료구조 C 언어] C 프로그래밍 자료구조 - 6 : 연결리스트 (Linked List) (추가, 삽입, 삭제, 검색, 뒤집기 등) (0) | 2020.03.05 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 4 : 배열을 사용한 스택 (Stack) (0) | 2020.03.04 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 3 (추가) : 희소 행렬 (1) | 2020.02.27 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 3 : 순서 리스트, 다항식의 표현 (0) | 2020.02.27 |