큐
큐
- 큐는 선입선출,FIFO(First - in, First - out) 구조의 자료구조이다. 즉, 먼저 들어간 데이터가 먼저 나오는 형태의 구조이다. 현실세계의 예로 들면 줄 서서 대중교통을 이용하는 것과 같다.
큐의 ADT(Abstract Data Type)
-
- enqueue : add (occurs at rear)
- 큐에 데이터를 넣는 연산. 넣는 데이터는 큐 중의 가장 뒤의 데이터가 되게 넣는다.
: rear가 가리키는 위치를 하나 이동시킨 다음, rear의 위치에 데이터를 저장한다.
-
- dequeue : delete ( occurs at front)
- 큐에 데이터를 꺼내는 연산. 큐에서 가장 앞선 데이터(가장 먼저 넣은)를 꺼낸다.
: front가 가리키는 위치를 하나 이동시킨 다음, front의 위치에 맞는 데이터를 반환 및 소멸시킨다.
-
- peek
- 큐에서 가장 앞선 데이터(가장 먼저 넣은)를 반환하되 큐에서 삭제하지 않는 연산.
-
- isQEmpty
- 큐가 비었는지 확인하는 연산. 비었으면 TRUE(1)을, 비어있지 않았으면 FALSE(0)을 반환한다.
-
- isQFull
- 큐가 꽉찼는지 확인하는 연산. 비었으면 TRUE(1)을, 비어있지 않았으면 FALSE(0)을 반환한다.
큐의 배열 기반 구현
다음을 염두하며 큐를 배열로 구현하자.
-
enqueue : add (occurs at rear) : rear가 가리키는 위치를 하나 이동시킨 다음, rear의 위치에 데이터를 저장한다.
-
dequeue : delete ( occurs at front) : front가 가리키는 위치를 하나 이동시킨 다음, front의 위치에 맞는 데이터를 반환 및 소멸시킨다.
#include <stdio.h>
## define SIZE 5
int queue[SIZE]={-1,};
int front = -1;
int rear = -1;
void enqueue(int data){
if(rear == SIZE -1){
printf("------queue is full------\n");
return;
}
queue[++rear] = data;
}
int dequeue(){
if(front == rear){
printf("------queue is empty------\n");
return -1;
}
int data = queue[++front];
queue[front] = -1;
}
void printQueue(){
int i;
printf("Order : first - in\n");
for(i= front+1; i<=rear; i++){
printf("%d ", queue[i]);
}
printf("\n");
}
int main(){
int i;
for(i=0;i<5;i++){
enqueue(i);
}
printQueue();
for(i=0;i<5;i++){
dequeue(i);
}
printQueue();
printf("rear : %d \n", rear);
enqueue(10);
return 0;
}
// 실행 결과
// Order : first - in
// 0 1 2 3 4
// Order : first - in
//
// rear : 4
// ------queue is full------
=> 큐를 배열로 구현하면 이정도 일 것이다. 하지만 여기에는 치명적인 단점이 있다.
=> 처음에 enqueue를 다섯번 호출하여 큐의 상태가 모두 가득차게 하였다. 이후 dequeue를 다섯번 호출하여 큐가 모두 비워지게 하였다. 따라서 큐는 비었으므로 다시 데이터를 넣을 수 있지만 그럼에도 큐에 데이터를 넣을 수 없다. 왜냐하면 enqueue를 호출했을 때 rear의 값이 4로 큐의 끝지점을 가리키고 있어 가득찼다고 인식하여 넣을 수 없고 rear를 1 증가시켜 넣는다 해도 그 위치는 큐의 바깥이라 그럴 수 없기 때문이다.
그러면 이러한 상황에 큐의 사이즈를 늘려서 enqueue를 호출할까? 가능한 얘기이고 스택의 경우 사이즈를 2배 늘려서 사용하므로 나쁘지 않은 생각인것 같다. 하지만 이렇게 사이즈를 늘리는 경우는 dequeue해서 앞의 index의 칸들이 비어있는 경우, 이 칸들은 낭비할 수 밖에 없다. 큐의 사이즈는 점차 커지지만 정작 모든 칸들을 사용할 수없는 문제가 발생한다. 이를 해결하기 위해 원형 큐가 등장했다.