Data Structure/자료구조

[자료구조] 큐와 원형 큐(순환 큐)

lumana 2024. 3. 27. 01:33

큐(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

현재글[자료구조] 큐와 원형 큐(순환 큐)

Brute force Study

배움을 나누는 공간 https://github.com/DawnGlow

Today :
Yesterday :

일	월	화	수	목	금	토
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

Brute force Study

[자료구조] 큐와 원형 큐(순환 큐)

큐(Queue)

큐의 ADT

순환 큐(원형 큐)

공백 상태와 포화 상태

원형 큐의 구조체

원형 큐 생성

원형 큐 제거

노드 삽입 연산

노드 제거 연산

공백 상태 확인

포화 상태 확인

원형 큐 사이즈 확인

예제 프로그램

'Data Structure > 자료구조' 카테고리의 다른 글

'Data Structure/자료구조'의 다른글

티스토리툴바

[자료구조] 큐와 원형 큐(순환 큐)

큐(Queue)

큐의 ADT

순환 큐(원형 큐)

공백 상태와 포화 상태

원형 큐의 구조체

원형 큐 생성

원형 큐 제거

노드 삽입 연산

노드 제거 연산

공백 상태 확인

포화 상태 확인

원형 큐 사이즈 확인

예제 프로그램

'Data Structure > 자료구조' 카테고리의 다른 글

'Data Structure/자료구조'의 다른글

관련글

티스토리툴바