[DATA STRUCTURE] 07. 환형 큐(Circular Queue)

아래의 코드는 C++로 구현된 환형 큐(Circular Queue)다.

일반 큐와 유사하지만 고정된 크기의 버퍼를 사용해 데이터를 순환하면서 자료를 저장하는 구조를 띠고 있으며

구현에 사용되는 std::vector 대신 일반적인 C 스타일 배열을 사용할 수도 있었지만, STL이 제공하는 편의성 때문에 

C 스타일 배열을 사용하지 않았다.

 

#pragma once
#include <vector>

template <class T>
class CircularQueue {
private:

    std::vector<T> buffer;
    int front;  // 큐의 시작 인덱스
    int rear;   // 큐의 끝 인덱스
    int capacity;

public:

    CircularQueue(int size) {

        capacity = size;
        buffer.resize(size);
        front = rear = -1;
    }

    bool isEmpty() const {

        return front == -1;
    }

    bool isFull() const {

        return (front == 0 && rear == capacity - 1) || (rear == front - 1);
    }

    void enqueue(const T& item) {

        if (isFull()) {

            return;
        }

        if (isEmpty()) {

            front = rear = 0;

        } else {

            rear = (rear + 1) % capacity;
        }

        buffer[rear] = item;
    }

    void dequeue() {

        if (isEmpty()) {

            return;
        }

        if (front == rear) {

            front = rear = -1;
        
        } else {
            
            front = (front + 1) % capacity;
        }
    }

    T frontValue() const {

        if (isEmpty()) {

            return T();  // 기본값 반환
        }

        return buffer[front];
    }

    int size() const {

        if (isEmpty()) {

            return 0;
        }

        if (rear >= front) {

            return rear - front + 1;

        } else {

            return capacity - (front - rear) + 1;
        }
    }
};

 

 

 

장점

 

1. 메모리 효율성 : 환형 큐는 크기가 고정되어 있을 때 메모리를 효율적으로 활용하며,

메모리 할당 및 해제에 대한 오버헤드가 없다.

 

2. 논리적 순환 : 데이터가 환형 큐에서는 논리적으로 순환되므로,

처음과 끝의 경계를 넘어가는 경우에도 데이터의 연속성을 유지할 수 있다.

 

3. 데이터 회전 : 환형 큐에서는 데이터가 계속해서 회전하며, 가장 오래된 데이터가 먼저 제거된다.

 

4. 큐의 크기 고정 : 크기가 고정되어 있기 때문에 큐가 가득 차면 빈 공간을 재활용할 수 있어

메모리 관리를 간단하게 할 수 있다.

 

 

단점

 

1. 구현의 복잡성 : 환형 큐는 인덱스 순환 및 비어있는 상태와 가득 찬 상태를 관리해야 하므로 구현이 복잡할 수 있다.

 

2. 크기 제한 : 환형 큐는 크기가 고정되어 있으므로 큐가 가득 찬 경우에는 추가 데이터를 수용할 수 없다.

고로 크기 조절이 필요한 경우에는 큐를 재설정해야 한다.