원형 큐 circular queue

 원형 큐는 고정된 크기의 버퍼에서 데이터를 순환하여 저장하는 자료구조이다. 큐의 시작과 끝이 연결되어 있어 데이터가 채워진 후에는 다시 처음으로 돌아가게 된다.

 

 

■ 사용 & 장점 

 

- 운영 체제의 프로세스 스케줄링

 

프로세스 스케줄러는 원형 큐를 사용하여 대기 중인 프로세스를 관리할 수 있다. 새로운 프로세스는 큐의 끝에 추가되고, CPU가 사용 가능해지면 큐에서 가장 앞에 있는 프로세스가 실행된다.

- 네트워크 패킷 처리: 네트워크 라우터나 스위치에서 데이터 패킷을 처리할 때, 원형 큐를 사용하여 대기 중인 패킷을 관리할 수 있다. 패킷은 큐에 추가되고, 라우터가 패킷을 전송할 수 있을 때 큐에서 가장 앞에 있는 패킷이 처리된다.

- 메모리 관리: 운영 체제는 메모리 할당과 해제를 관리하기 위해 원형 큐를 사용할 수 있다. 새로운 메모리 블록이 할당되면 큐에 추가되고, 해제될 때 큐에서 가장 앞에 있는 블록이 해제된다.

- 데이터 버퍼링: 데이터를 처리하거나 전송할 때 발생하는 데이터 버퍼링에도 원형 큐가 사용될 수 있다. 데이터는 버퍼에 추가되고, 처리가 가능해지면 가장 오래된 데이터가 제거된다.

- 멀티 스레딩 환경에서의 작업 스케줄링: 원형 큐는 멀티 스레딩 환경에서 작업 스케줄링에 사용될 수 있다. 각 스레드는 큐에 작업을 추가하고, 스케줄러는 큐에서 다음으로 실행될 작업을 선택할 수 있다.

- 원형 큐는 배열을 사용하여 구현되며, 큐의 처음과 끝이 연결되어 있기 때문에 배열의 끝에 도달했을 때 큐가 가득 차 있는지를 확인하고 추가로 공간을 확보하기 위해 배열을 이동할 필요가 없어 공간을 효율적으로 활용할 수 있다.

- 원형 큐는 선형 큐에 비해 구현이 간단한다. 큐의 원형 구조를 유지하면서 요소를 추가하거나 제거할 때 발생하는 인덱스 조정에 대한 복잡성이 줄어든다.

- 삽입과 삭제가 배열의 끝 부분에서 발생하므로, 요소를 삽입하거나 삭제하는 데에 O(1) 시간이 걸린다. 이는 선형 큐와 비교했을 때 빠른 작업 처리를 가능하게 한다.

- 원형 큐는 배열을 사용하여 구현되기 때문에 메모리 상에 연속적으로 배치되어 있다. 이는 캐시 효율성 측면에서 성능이 향상될 수 있다.

 

 

 

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 5 // 큐의 최대 크기

int queue[MAX_SIZE]; // 큐를 저장할 배열
int front = -1; // 큐의 시작 인덱스
int rear = -1; // 큐의 끝 인덱스

// 큐가 비어있는지 확인하는 함수
bool isEmpty() {
    return (front == -1 && rear == -1);
}

// 큐가 가득 차 있는지 확인하는 함수
bool isFull() {
    return ((rear + 1) % MAX_SIZE == front);
}

// 큐에 데이터를 추가하는 함수
void enqueue(int data) {
    if (isFull()) {
        printf("Queue is full. Cannot enqueue.\n");
        return;
    }
    else if (isEmpty()) {
        front = rear = 0; // 큐가 비어있다면 front와 rear를 0으로 설정
    }
    else {
        rear = (rear + 1) % MAX_SIZE; // rear를 다음 위치로 이동 (원형 큐의 특성)
    }
    queue[rear] = data; // rear 위치에 데이터를 추가
}

// 큐에서 데이터를 제거하고 반환하는 함수
int dequeue() {
    int data;
    if (isEmpty()) {
        printf("Queue is empty. Cannot dequeue.\n");
        return -1; //제거할 데이터가 없다는 의미를 반환
    }
    else if (front == rear) { // 큐에 데이터가 하나만 남았을 경우 front와 rear를 초기화
        data = queue[front];
        front = rear = -1;
    }
    else {
        data = queue[front]; // front 위치의 데이터를 반환
        front = (front + 1) % MAX_SIZE; // front를 다음 위치로 이동 (원형 큐의 특성)
    }
    return data;
}

// 현재 큐의 상태를 출력하는 함수
void display() { 
    if (isEmpty()) {
        printf("Queue is empty.\n");
        return; //큐가 비었다면 종료
    }
    printf("Queue: "); //비어있지 않다면
    int i = front;
    do {
        printf("%d ", queue[i]);
        i = (i + 1) % MAX_SIZE;
    } while (i != (rear + 1) % MAX_SIZE);
    printf("\n");
}

int main() {
    // 큐에 데이터 추가
    enqueue(1);
    enqueue(2);
    enqueue(3);
    enqueue(4);
    enqueue(5);

    // 큐가 가득 찬 상태에서 추가 시도
    enqueue(6);

    // 큐에서 데이터 제거하고 출력
    printf("Dequeued item: %d\n", dequeue());
    printf("Dequeued item: %d\n", dequeue());

    // 큐에 데이터 추가
    enqueue(6);
    enqueue(7);

    // 현재 큐의 상태 출력
    display();

    return 0;
}