[자료구조] 원형 큐 (Circular Queue)

원형 큐 (Circular Queue)

---

기본적으로 Queue의 규칙을 따라 FIFO구조로 데이터가 push, pop되며, 고정 크기 배열을 원처럼 순환시켜 사용하는 큐로 인덱스가 배열 끝에 도달하면 다시 앞(0)으로 돌아간다. 고정 배열을 사용하기 때문에 연속된 메모리 공간에 할당되어 캐시 친화적이다. 원형큐는 STL에서 지원하지 않기 때문에 직접 구현하거나 boost::circular_buffer를 사용하여야 한다. 삽입과 삭제 연산은 항상 heal, tail위치에서 이루어지기 때문에 모든 연산의 시간 복잡도는 O(1)이다.

원형 큐와 비슷한 개념으로 링 버퍼(Ring Buffer)가 있다. Ring Buffer는 고정 크기 배열을 순환해서 쓰는 버퍼로 원형큐와 구조적으로 동일하지만, 데이터를 덮어 쓰느냐에 대한 관점에서 차이가 있다. 원형 큐는 포화검사를 통해 큐가 가득 차있다면 push에 실패해 데이터를 덮어쓰지 않는다. 링 버퍼는 덮어쓰는 모드를 지원하여 가장 오래된 데이터를 자동으로 지우고, 새 데이터를 넣을 수 있다. (두 가지 모두 지원함) 링 버퍼는 주로 버퍼링/ 스트리밍/ 실시간 처리에서 많이 사용하여 대부분 덮어쓰기 모드로 사용되고있다.

 

원형 큐의 멤버

 

원형 큐에 들어가야 할 필수 멤버는 데이터를 저장할 buffer와 배열 고정 szie, 현재 요소 개수인 count 그리고 큐의 핵심인 읽을 위치와 쓸 위치가 필요하다.

template<typename T>
class CircularQueue 
{
    std::vector<T> bufuffer;     // 고정 크기 배열 (bufuffer[capacity)
    size_t head = 0;             // 읽을 위치 index
    size_t tail = 0;             // 쓸 위치 index
    size_t count= 0;             // 현재 요소 개수 (one-slot 방식으로 공백/포화 검사를 할거라면 없어도 된다)
    size_t capacity;             // 고정 배열 size
}

 

 

push, pop

 

원형 큐는 FIFO 자료구조이기 때문에 push는 맨 뒤에, pop은 맨 앞에서 이루어진다.

 bool push(const T& value) 
 {
      if (full()) return false;
      buf[tail] = value;
      tail = (tail + 1) % capacity;
      ++cnt;
      return true;
  }

bool emplace(T&& value) { return push(std::forward<T>(value)); }

bool pop() 
{
    if (empty()) return false;
    // optional: buf[head].~T(); if using manual storage
    head = (head + 1) % capacity;
    --cnt;
    return true;
}

 

 

공백검사, 포화검사

 

원형 큐의 공백 검사와 포화 검사는 두 가지 방식을 통해 구현할 수 있다. 현재 큐에 있는 요소 개수(count)를 통해 검사하는 방식과 큐의 마지막 한 자리를 비우고(one-sloat) head와 tail의 비교 검사로 구현하는 방식이다. count를 통해 검사를 할 경우 count 멤버변수를 따로 관리해야하기 때문에 미미한 오버헤드가 있다는 단점이 있지만 정말 미미하고 요소 개수를 관리하는것이 직관적이기 때문에 이 방식을 많이 사용한다. head tail의 비교로 검사를 할 경우는 count를 따로 사용하지 않아도 된다는 장점이 있지만 한 칸을 비워두어야 하기 때문에 capacity-1 만큼의 공간만 사용할 수 있다는 단점이 있다.  

 

1. Count 방식을 통한 공백/ 포화 검사

bool empty() const { return cnt == 0; }
bool full()  const { return cnt == capacity; }

 

2. 한 칸 비워두기(One-slot)를 통한 공백/ 포화 검사

bool empty() const { return head == tail; }
bool full()  const { return (tail + 1) % capacity == head; }  // 마지막 자리 희생