큐(Queue)
큐의 ADT
- 큐의 개념
- 입력과 출력 창구가 따로 존재하고, 제일 먼저 들어간 데이터가 제일 먼저 나옴(FIFO)
- 큐의 핵심 기능 : 삽입과 제거
- 전단 : 큐의 가장 앞 요소, 제거 연산이 일어나는 곳
- 후단 : 큐의 가장 마지막 요소, 삽입 연산이 일어나는 곳
순환 큐(원형 큐)
- 큐를 배열로 구현하는 경우 전단을 제거한 후 요소를 이동하는데 비용이 매우 큼
- 큐의 전단과 후단을 가리키는 변수를 도입
- 삽입과 제거를 거치다 보면 큐의 용량이 줄어듬
- 순환 큐 : 배열의 끝과 시작을 연결함
- 배열의 마지막 요소가 후단인 경우 삽입 연산을 진행하면 배열의 첫 번째 요소가 후단이 된다
- 전단의 경우도 마찬가지
- 삽입이 이루어질 때 후단이 전단을 만나면 큐는 가득 찬 상태가 된다
- 전단과 후단이 만나있는 경우, 공백 상태화 포화 상태를 구별해야 함
- 시작과 끝을 연결함으로써 효율적인 삽입 / 삭제 연산이 가능해짐
공백 상태와 포화 상태
- 순환 큐가 제대로 동작하려면 큐가 공백 상태인지, 포화 상태인지 구분해야 함
- 공백 상태와 포화 상태 모두 전단과 후단이 같은 위치이 있기 때문
- 이를 해결하기 위해서 큐를 생성할 때 실제 용량보다 1만큼 더 크게 만든다
- 공백일 경우 전단과 후단의 위치가 같고, 포화 상태인 경우 후단이 전단보다 1 작은 값을 가진다
원형 큐의 구조체
- 노드는 데이터 값을 담고 있음
- 큐 구조체는 큐의 용량, 전단 위치, 후단 위치, 순환 큐 요소의 배열에 대한 포인터를 가지고 있음
typedef struct _Node
{
int data;
} Node;
typedef struct _CircleQueue
{
int capacity; // 큐의 용량
int front; // 전단 위치
int rear; // 후단 위치
Node* node; // 요소 데이터
} CircularQueue;- 실제로는 Nodes를 메모리에 할당할 때 'Capacity + 1' 만큼 크기를 할당한다
- 남은 한개 노드는 상태를 구분하기 위해 더미 노드로 사용함
- Rear가 실제 후단보다 1 더 큰 값을 갖는 다는 사실에 주의하자
원형 큐 생성
- 순환 큐에 대한 포인터, 큐의 용량을 결정하는 capacity를 매개변수로 받음
- Node의 크기 * (capacity + 1) 크기로 메모리에 할당
void CreateQueue(CircularQueue** queue, int capacity)
{
(*queue) = (CircularQueue*)malloc(sizeof(CircularQueue));
// capacity + 1만큼 노드를 메모리에 생성
(*queue)->node = (Node*)malloc(sizeof(Node) * (capacity + 1));
(*queue)->capacity = capacity;
(*queue)->front = 0;
(*queue)->rear = 0;
}원형 큐 제거
- 배열을 메모리에서 제거한 후 순환 큐 구조체를 제거
void DestroyQueue(CircularQueue* queue)
{
// 원형 큐가 가리키는 노드 소멸
free(queue->node);
// 원형 큐 소멸
free(queue);
}노드 삽입 연산
- 삽입 연산에서는 Rear(후단)을 다루는 것이 중요함
- Rear의 값이 Capacity + 1과 같다면 포화상태가 되므로 Rear와 Position을 0으로 지정한다
- 그렇지 않은 경우에는 Rear의 위치를 Position에 저장한 후 Rear의 값을 1 증가시킨다
- Position 은 후단, 즉 삽입하는 값이 담겨야 하는 위치, Rear는 후단 위치에 1을 더한 값
void Enqueue(CircularQueue* queue, int data)
{
// 후단 위치를 가리킬 변수
int position = 0;
// 후단이 큐 끝에 도달한 경우
if(queue->rear == queue->capacity) {
position = queue->rear;
queue->rear = 0;
}
// 큐가 가득 차지 않았을 때
else {
// 현재 위치 1씩 증가
position = queue->rear;
queue->rear++;
}
queue->node[position].data = data;
}노드 제거 연산
- 노드 제거의 경우 Front(전단)을 잘 관리해야 함
- Position은 전단의 위치를 저장 (데이터를 반환할 때 사용할 변수)
- Front의 값이 Capacity와 같을 때, Front의 값을 0으로 초기화
int Dequeue(CircularQueue* queue)
{
// 전단 위치를 가리킬 변수
int position = queue->front;
// 전단이 큐 끝에 도달한 경우
if(queue->front == queue->capacity) {
queue->front;
}
else {
queue->front++;
}
return queue->node[position].data;
}공백 상태 확인
- Front와 Rear가 같은지 확인
int IsEmpty(CircularQueue* queue)
{
return (queue->front == queue->rear);
}포화 상태 확인
- 전단이 후단 앞에 있는 경우
- 후단과 전단의 차가 큐의 용량과 동일하면 포화 상태
- 전단이 후단과 같은 위치 또는 뒤에 있는 경우
- 후단 + 1 이 전단과 동일한 경우 포화 상태
int IsFull(CircularQueue* queue)
{
// 같을 경우 포화 상태
if(queue->front < queue->rear) {
return (queue->rear - queue->front) == queue->capacity;
}
// 같을 경우 포화 상태
else {
return (queue->rear + 1) == queue->front;
}
}원형 큐 사이즈 확인
- 후단이 전단보다 뒤에 있는 경우
- rear - front
- 후단이 전단보다 앞에 있을 경우
- capacity + 1 - front + rear
int GetSize(CircularQueue* queue)
{
// 후단이 전단보다 뒤에 있을 경우 그냥 빼서 리턴
if(queue->front <= queue->rear) {
return queue->rear - queue->front;
}
// 후단이 전단보다 앞에 있을 경우
else {
queue->rear + (queue->capacity - queue->front) + 1;
}
}예제 프로그램
#include <stdio.h>
#include <stdlib.h>
typedef struct _Node
{
int data;
} Node;
typedef struct _CircleQueue
{
int capacity; // 큐의 용량
int front; // 전단 위치
int rear; // 후단 위치
Node* node; // 요소 데이터
} CircularQueue;
void CreateQueue(CircularQueue** queue, int capacity);
void DestroyQueue(CircularQueue* queue);
void Enqueue(CircularQueue* queue, int data);
int Dequeue(CircularQueue* queue);
int IsEmpty(CircularQueue* queue);
int IsFull(CircularQueue* queue);
int GetSize(CircularQueue* queue);
int main()
{
int i;
CircularQueue* queue;
CreateQueue(&queue, 10);
Enqueue(queue, 1);
Enqueue(queue, 2);
Enqueue(queue, 3);
Enqueue(queue, 4);
for(i = 0; i < 3; i++) {
printf("Dequeue : %d ", Dequeue(queue));
printf("Front : %d Rear : %d\n", queue->front, queue->rear);
}
i = 100;
while(IsFull(queue) == 0) {
Enqueue(queue, i++);
}
printf("Capacity : %d, Size : %d\n\n", queue->capacity, GetSize(queue));
while(IsEmpty(queue) == 0) {
printf("Dequeue : %d ", Dequeue(queue));
printf("Front : %d Rear : %d\n", queue->front, queue->rear);
}
DestroyQueue(queue);
return 0;
}
void CreateQueue(CircularQueue** queue, int capacity)
{
(*queue) = (CircularQueue*)malloc(sizeof(CircularQueue));
// 크기 1만큼 +해서 메모리 생성
(*queue)->node = (Node*)malloc(sizeof(Node) * (capacity + 1));
(*queue)->capacity = capacity;
(*queue)->front = 0;
(*queue)->rear = 0;
}
void DestroyQueue(CircularQueue* queue)
{
// 원형 큐가 가리키는 노드 소멸
free(queue->node);
// 원형 큐 소멸
free(queue);
}
void Enqueue(CircularQueue* queue, int data)
{
// 현재 위치를 가리킬 변수
int position = 0;
// 큐가 가득 찼을 때
if(queue->rear == queue->capacity) {
position = queue->rear;
queue->rear = 0;
}
// 큐가 가득 차지 않았을 때
else {
// 현재 위치 1씩 증가
position = queue->rear++;
//queue->rear++;
}
queue->node[position].data = data;
}
int Dequeue(CircularQueue* queue)
{
int position = queue->front;
if(queue->front == queue->capacity) {
queue->front = 0;
}
else {
queue->front++;
}
return queue->node[position].data;
}
int IsEmpty(CircularQueue* queue)
{
return (queue->front == queue->rear);
}
int IsFull(CircularQueue* queue)
{
// 같을 경우 포화 상태
if(queue->front < queue->rear) {
return (queue->rear - queue->front) == queue->capacity;
}
// 같을 경우 포화 상태
else {
return (queue->rear + 1) == queue->front;
}
}
int GetSize(CircularQueue* queue)
{
// 전단이 후단보다 뒤에 있을 경우 그냥 빼서 리턴
if(queue->front <= queue->rear) {
return queue->rear - queue->front;
}
// 전단이 후단보다 앞에 있을 경우
else {
queue->rear + (queue->capacity - queue->front) + 1;
}
}참조) 박상현, 『이것이 자료구조+알고리즘이다 with C언어』, 한빛미디어(2022)
'Data Structure > 자료구조' 카테고리의 다른 글
| [자료구조] 덱(Dequeue, 데크) (0) | 2024.03.27 |
|---|---|
| [자료구조] 링크드 큐(Linked Queue) (0) | 2024.03.27 |
| [자료구조] 연결 리스트(linked list) 기반 스택 구현 (0) | 2024.03.26 |
| [자료구조] 배열 기반 스택 구현 (0) | 2024.03.26 |
| [자료구조] 환형 링크드 리스트 구현 (0) | 2024.03.26 |