배열로 만든 선형 큐는 데이터가 나오는 Front가 마지막의 인덱스에 도달할 경우 앞에 데이터를 넣을 수 있지만, 큐가 가득 찼다고 판단합니다.
ㅁㅁㅁㅁFront
이런 문제를 해결하기 위해서 배열의 처음과 끝을 연결하면, Rear가 배열의 앞으로 변경되어 데이터를 넣을 수 있습니다.
또한 미리 할당한 메모리만 사용하기 때문에 관리가 간편하며, 동적 할당과 해제에 필요한 오버헤드가 없어집니다.
원형 큐 구조체
데이터를 저장하고 관리하기 위한 노드 구조체를 만듭니다.
|
1
2
3
4
5
|
// 노드 구조체
typedef struct Node
{
ElementType Data;
} Node;
|
배열을 사용한 원형 큐이기 때문에 연결 리스트처럼 다음 노드를 가리킬 포인터가 필요없습니다.
이제 노드를 만들었고 원형 큐 구조체를 만들어봅시다.
|
1
2
3
4
5
6
7
|
typedef struct CircularQueue
{
int Capacity;
int Front;
int Rear;
Node* Nodes;
} CircularQueue;
|
큐의 용량과 데이터를 빼줄 맨 앞의 위치인 전단과, 데이터를 넣어줄 맨 뒤의 위치인 후단을 가지고 있습니다.
물론 노드들의 배열도 가지고 있습니다.
원형 큐 연산
구현한 원형 큐에 사용할 연산 함수입니다.
우리가 지금까지 구현했던 방식으로는 Rear의 위치에 새 데이터를 넣고 Rear를 1증가 시킵니다.
다음 그림처럼 문제가 발생하게 됩니다.
큐가 꽉찬 경우(Full)에는 전단과 후단이 같게 됩니다. 그럼 초기의 큐가 빈 상태인 경우도 Rear와 Front의 상태입니다.
즉, 큐가 빈 상태과 꽉찬 상태의 경우 Front와 Rear가 같은 곳을 가리키고 있기 때문에 두 상황을 구분할 수 없습니다.
문제를 해결하기 위한 방법으로 큐의 용량을 1 증가 시킵니다.
넣을 수 있는 용량보다 1 증가 시키면 가득 찬 상태는 전단과 후단이 같은 곳을 가리키지 않고, 전단보다 1 작은 곳을 가리키게 됩니다.
이러면 빈 상태와 가득 찬 상태를 구분할 수 있습니다.
1. 원형 큐 - 생성
배열 스택을 만들었던 것을 기억하나요?
사용할 큐의 용량을 전달 받아서 자유 저장소에 원형 큐와 노드 배열을 할당하고 초기화합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// CQ 생성
void CQ_CreateQueue(CircularQueue** Queue, int Capacity)
{
// 원형 큐를 자유 저장소에 할당
(*Queue) = (CircularQueue*)malloc(sizeof(CircularQueue));
// 노드 배열을 자유 저장소에 할당 - 더미 노드 추가
(*Queue)->Nodes = (Node*)malloc(sizeof(Node)* (Capacity+1));
// 원형 큐 초기화
(*Queue)->Capacity = Capacity;
(*Queue)->Front = 0;
(*Queue)->Rear = 0;
}
|
생성된 원형 큐의 Front와 Rear가 배열의 첫 인덱스를 가리킬 수 있도록 0으로 초기화합니다.
2. 원형 큐 - 소멸
자유저장소에 동적으로 할당했던 원형 큐와 노드 배열을 소멸시키는 연산입니다.
free() 함수를 사용해서 할당된 메모리를 해제합니다.
|
1
2
3
4
5
6
7
|
// CQ 소멸
void CQ_DestroyQueue(CircularQueue* Queue)
{
// 노드 배열을 자유 저장소에서 해제
free(Queue->Nodes);
free(Queue);
}
|
메모리가 누수되지 않도록, 먼저 할당된 노드 배열을 자유저장소에서 해제한 다음에 원형 큐를 해제합니다.
3. 원형 큐 - 데이터 삽입(Enqueue)
생성된 원형 큐에 데이터를 추가하는 Enqueue 연산입니다.
해당 연산은 Data를 전달받아서 Rear의 위치에 넣어주는 연산입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
// CQ 데이터 삽입
void CQ_Enqueue(CircularQueue* Queue, ElementType Data)
{
int Position = 0;
// Rear가 Capacity에 도달하면 배열의 인덱스 처음
if (Queue->Rear == Queue->Capacity)
{
Position = Queue->Rear;
Queue->Rear = 0;
}
// Rear가 Capacity에 도달하지 않았다면 Rear를 증가
else
{
Position = Queue->Rear++;
}
Queue->Nodes[Position].Data = Data;
}
|
큐의 Capacity와 Rear가 같은 곳을 가리키는 경우가 있습니다.
할당한 노드 배열의 마지막을 Rear가 가리키는 경우로 뒤에 데이터를 넣을 수 없지만, 앞에 데이터를 넣을 수 있습니다.
배열의 0번부터 데이터를 넣을 수 있도록 값을 변경해줍니다.
4. 원형 큐 - 데이터 삭제(Dequeue)
생성된 원형 큐에 데이터를 삭제하는 Dequeue 연산입니다.
해당 연산은 Front의 위치에 제거해주는 연산입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
// CQ 데이터 삭제
ElementType CQ_Dequeue(CircularQueue* Queue)
{
int Position = Queue->Front;
// Front가 Capacity에 도달하면 배열의 인덱스 처음으로 변경
if (Queue->Front == Queue->Capacity)
{
Queue->Front = 0;
}
// Front가 Capacity에 도달하지 않았다면 Front를 증가
else
{
Queue->Front++;
}
// Front에 있는 데이터 반환
return Queue->Nodes[Position].Data;
}
|
데이터를 추가하는 연산처럼 Front와 Capacity가 같게 되면 노드 배열의 첫 인덱스로 이동합니다.
5. 원형 큐 - 크기
생성된 원형 큐에 들어 있는 데이터의 총 개수입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
// CQ 크기 반환
int CQ_GetSize(CircularQueue* Queue)
{
if(Queue->Front <= Queue->Rear)
{
return Queue->Rear - Queue->Front;
}
// 배열에서 Rear가 Front보다 앞에 있는 경우
else
{
return Queue->Capacity - (Queue->Front - Queue->Rear) + 1;
}
}
|
배열에서 Front가 앞에 있고 Rear가 뒤에 있는 경우는 간단하게 데이터의 개수를 구합니다.
Rear가 Front보다 앞에 있는 경우는 총 용량에서 Front - Rear를 빼준 값에 1을 더합니다.(더미 노드 계산)
6. 원형 큐 - 비여있는지 확인
생성된 원형 큐가 비어있는지 확인하는 연산입니다.
|
1
2
3
4
5
|
// CQ 비여있는지 확인
int CQ_IsEmpty(CircularQueue* Queue)
{
return (Queue->Front == Queue->Rear);
}
|
비여있는 경우는 노드 배열에서 인덱스와 상관없이 Front와 Rear가 같은 곳을 가리키고 있습니다.
7. 원형 큐 - 가득차있는지 확인
생성된 원형 큐가 가득차 있는지 확인하는 연산입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// CQ 가득차있는지 확인
int CQ_IsFull(CircularQueue* Queue)
{
// 배열에서 Rear가 Front보다 뒤에 있는 경우
if (Queue->Front < Queue->Rear)
{
return (Queue->Rear - Queue->Front) == Queue->Capacity;
}
// 배열에서 Rear가 Front보다 앞에 있는 경우
else
{
return (Queue->Rear + 1) == Queue->Front;
}
}
|
데이터를 삽입하거나 삭제하는 연산처럼 Rear가 Front 보다 앞에 있는 경우를 생각합니다.
Rear가 앞에 잇는 경우는 더미 노드로 인해서 Rear값보다 1 큰 곳이 Front입니다.
댓글