큐(Queue)
이전에 살펴본 스택과는 다르게, 큐는 선입선출(FIFO)의 구조를 가집니다.
1부터 5까지 차례대로 들어온 것이며, deQueue 연산을 하게 되면 1이 출력될 것입니다.
- Queue의 가능한 연산 종류
- createQueue : 큐를 생성한다. 맨 앞을 나타내는 front, 끝을 나타내는 rear는 초기에 인덱스 -1이다.
- enQueue : 큐에 요소를 추가한다. rear + 1을 하고 그 자리에 요소를 추가한다.
- deQueue : 큐에서 맨 앞의 요소를 빼낸다. front + 1을 하고 그 자리에 있던 요소를 출력한다.
- isFull : 큐가 꽉 찼는지 확인한다. rear = n - 1, 즉 rear가 마지막 인덱스를 가리키면 꽉 찬 것이다.
- isEmpty : 큐가 비었는지 확인한다. front = rear이면 큐가 비었다고 판단한다.
- QPeek : 큐에서 맨 앞의 요소를 빼내지 않고 값을 확인한다.
위 그림은 선형 큐를 나타낸 모양인데, 선형 큐에는 단점이 존재합니다.
- 선형 큐에서 삽입 및 삭제를 반복하다 보면, rear가 맨 마지막 인덱스를 가리키고, 앞에는 비어 있을 수 있지만 이를 꽉 찼다고 인식합니다.
이는 실제 데이터는 삭제 때마다 한 칸 앞으로 이동시키지 않았고, 인덱스 단위로 큐의 연산을 진행했기 때문입니다.
그래서 생겨난 아이디어가 원형 큐 입니다. 코딩에서는 1차원 배열을 활용하지만 처음과 끝이 원형처럼 이어져 있다고 가정합니다.
원형 큐의 구현
- 별도의 isEmpty, isFull 함수를 구현하지 않고, 큐에 삽입 및 삭제 시 큐가 꽉 찼는지, 비었는지 확인할 수 있도록 하였습니다.
- 원형 큐에도 일차원 배열을 사용합니다.
- 초기 front와 rear는 맨 처음 인덱스에 위치합니다.
- enQueue 연산 시 rear + 1 하여 데이터를 새로 넣습니다. 그런데 rear + 1이 front와 같으면 꽉 차 있다고 판단해야 합니다.
- 따라서 front가 가리키는 곳은 데이터가 없다고 가정해야 합니다.
- 데이터 추가 시 rear가 1칸 움직입니다. 단, (rear + 1) % (일차원 배열의 크기) 만큼 움직입니다.
- 하단의 코드는 큐의 크기 n을 데이터가 들어갈 크기로 보았습니다.
- 따라서 큐에 사용할 일차원 배열의 크기는 n+1 이 되도록 선언해야 할 것입니다.
- 데이터 삭제 시 front가 1칸 움직입니다. front도 (front + 1) % (일차원 배열의 크기) 만큼 움직입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int count = 0;
int n;
int front = 0, rear = 0;
int* queue;
void enQueue(int data) {
if ((rear + 1) % (n+1) == front) {
printf("큐가 꽉 찼습니다.\n");
return;
}
rear = (rear + 1) % (n + 1);
queue[rear % (n+1)] = data;
}
int deQueue() {
int data;
if (front == rear) {
printf("큐가 비었습니다.\n");
return 0;
}
data = queue[(front + 1) % (n+1)];
front = (front + 1) % (n+1);
}
void printQueue() {
int idx=0;
idx = (front + 1) % (n+1);
do{
if (front == rear) {
printf("큐가 비었습니다.\n");
break;
}
else if (idx > rear)
break;
printf("%d ", queue[idx++ % (n + 1)]);
} while (1);
}
int main() {
printf("원형 큐의 크기 입력 : ");
scanf("%d", &n);
queue = (int*)malloc(sizeof(int) * (n + 1));
while (1) {
int menu, data;
printf("\n1. 삽입 , 2. 삭제, 3. 출력, 4. 종료\n");
scanf("%d", &menu);
switch (menu)
{
case 1:
printf("삽입할 데이터 입력 : ");
scanf("%d", &data);
enQueue(data);
break;
case 2:
deQueue();
break;
case 3:
printQueue();
break;
case 4:
exit(1);
break;
}
}
}