큐
큐는 먼저 들어온 일부터 먼저 처리하는 자료구조 입니다.
선입 선출, First In First Out (FIFO) 라고 합니다.
큐의 기능
큐의 가장 앞 요소를 전단, 마지막 요소를 후단이라고 합니다.
(스택은 최상위 노드가 있는 입구에서만 삽입/제거가 수행됩니다. )
큐는 전단에서 Dequeue (제거) 되고, 후단에서만 Enqueue (삽입) 됩니다.
순환 큐
유의할 점은 큐가 비었는지 가득찼는지 구분을 위해 큐를 실제 용량보다 1 크게 만드는 것입니다.
용량이 7인 큐를 만든다고 하면,
구현할 때는 8인 큐를 만듭니다.
비었을 때는 전단과 후단이 같은 곳을 가리킵니다
큐가 꽉 찼을 때는 후단 바로 다음이 전단이 됩니다.
이렇게 후단과 전단 사이에 공간을 두어 큐의 상태를 구분합니다.
후단은 실제 데이터가 있는 칸의 바로 다음칸을 가리키고 있음을 유의해야 합니다.
후단 인덱스는 항상 빈 칸을 가리키고 있어야 합니다.
순환 큐 구현
노드와 큐 구조체를 선언합니다.
typedef struct Node {
int data;
};
typedef struct Cqueue {
int capacity;
int front;
int rear;
Node* nodeArray;
};
Cqueue구조체에서 nodeArray 포인터는 자유저장소에 존재하는 배열의 첫번째 칸을 가리킵니다.
공백과 포화를 구분하기 위해 실제 capacity + 1하기 위한 '더미 노드'를 하나 둡니다.
큐를 만들고 메모리 해제하는 함수
void CreateCqueue(Cqueue** cqueue, int capacity) {
(*cqueue) = (Cqueue*)malloc(sizeof(Cqueue));
(*cqueue)->capacity = capacity;
(*cqueue)->front = 0;
(*cqueue)->rear = 0;
(*cqueue)->nodeArray = (Node*)malloc(sizeof(Node) * (capacity + 1));
}
nodeArray 라는 이름의 배열은 사용자가 요구한 용량보다 1개 크게 만들어집니다. 더미 노드를 포함하기 때문입니다.
void FreeCqueue(Cqueue* cqueue) {
free(cqueue->nodeArray);
free(cqueue);
}
삽입(Enqueue)
뒤에서 삽입하니까 rear를 관리합니다.
rear는 항상 삽입'할' 타겟 인덱스를 가리키고 있습니다.
즉, 빈 공간을 가리키고 있다는 뜻입니다.
capacity + 1인 인덱스는 공백/포화를 구분할 더미노드의 위치입니다.
void Enqueue(Cqueue* cqueue, int data) {
int position = 0;
if (cqueue->capacity + 1 == cqueue->rear) {
position = cqueue->rear;
cqueue->rear = 0;
}
else {
position = cqueue->rear++;
}
cqueue->nodeArray[position].data = data;
}
제거(Dequeue)
앞에서 제거하니까 front를 관리합니다.
front와 capacity가 같은 상황은 전단이 배열 맨 끝에 와있다는 것입니다.
노드를 하나 제거 하면, 인덱스를 0으로 돌려놔야 합니다.
이 경우를 제외하면 front를 하나 감소시키면 됩니다.
int Dequeue(Cqueue* cqueue) {
int position = cqueue->front;
if (cqueue->front == cqueue->capacity ) {
cqueue->front = 0;
}else{
cqueue->front++;
}
return cqueue->nodeArray[position].data;
}
큐의 공백과 포화 확인하기
공백 : front 와 rear 가 같은 곳을 가리키고 있습니다.
int IsEmpty(Cqueue* cqueue) {
return (cqueue->front == cqueue->rear);
}
포화: rear의 바로 다음이 front 입니다. 또는 rear에서 front를 빼면 그 길이가 capacity가 됩니다.
int IsFull(Cqueue* cqueue) {
if (cqueue->front < cqueue->rear) {
return (cqueue->rear - cqueue->front == cqueue->capacity);
}
else {
return (cqueue->front == cqueue->rear + 1);
}
}
메인함수 - 삽입/제거 해보기
5개를 저장할 수 있는 배열을 만들고, 8번 삽입, 6번 제거해봤습니다.
삽입 전에 포화인지 검사하고 포화이면 탈출합니다.
제거 전에 비었는지 검사하고 비었으면 탈출합니다.
콘솔 결과
int main(void) {
int i = 0;
Cqueue* queue;
// 5개를 저장할 수 있는 배열
CreateCqueue(&queue, 5);
// 8번 삽입
for (int cnt = 1; cnt < 9; cnt++) {
if (!IsFull(queue)) {
printf("%d를 삽입.\n", cnt);
Enqueue(queue, cnt);
}
else {
printf("큐가 꽉 찼습니다.\n");
break;
}
}
// 6번 제거
for (int cnt = 1; cnt < 7; cnt++) {
if (!IsEmpty(queue)) {
printf("%d 를 제거.\n", Dequeue(queue));
}
else {
printf("큐가 비었습니다.\n");
break;
}
}
return 0;
}