Circular Queue

특징

• 이전 Queue의 한계점에서 언급한 배열 요소의 위치를 변환해야한다는 단점을 해소하기 위해 고안됨
• 시작과 끝점이 연결된 것처럼 작동해 이전처럼 배열 요소들을 앞으로 당기는 등의 조치가 필요없어짐

기존 Queue와의 차이점

• front와 rear의 시작 값이 -1이 아닌 0
• front는 동일하게 값이 저장된 위치 1칸 앞을 가리키고, rear는 마지막 값이 있는 위치를 가리킴
• 아무 값도 없는 빈 상태에서는 front와 rear의 값이 동일함
• 가득 찬 상태에서는 front % 배열 최대 크기 == (rear + 1) % 배열 최대 크기가 성립

예시

총 5칸이 있고 비어있는 상태
front : 0
rear : 0
□ □ □ □ □

배열에 값이 가득 찬 상태
front : 0
rear : 4
□ ■ ■ ■ ■

결과 확인
0 % 5 == (4 + 1) % 0 
둘 다 0이므로 같은 것이 확인됨

• 앞의 1칸을 비워둠으로써 빈 상태와 가득 찬 상태를 구분
  모든 칸을 다 채우면 front와 rear가 가리키는 지점이 같아져 빈 상태와 가득 찬 상태를 구분할 수 없음

구현

template <typename T>
class CircularQueue : public Queue<T>
{
private:
public:
    bool IsFull()
    {
        return (this->rear + 1) % this->maxSize == this->front % this->maxSize;
    }

    void Enqueue(T value)
    {
        if (this->IsFull())
        {
            throw "Circular Queue is full";
        }

        this->rear = (this->rear + 1) % this->maxSize;
        this->arr[this->rear] = value;
    }

    T Dequeue()
    {
        if (this->IsEmpty())
        {
            throw "Circular Queue is empty";
        }

        this->front = (this->front + 1) % this->maxSize;
        return this->arr[this->front];
    }

    void Display()
    {
        if (this->IsEmpty())
        {
            throw "Circular Queue is empty";
        }

        int i = (this->front + 1) % this->maxSize;
        while (i != (this->rear + 1) % this->maxSize)
        {
            cout << this->arr[i] << " ";
            i = (i + 1) % this->maxSize;
        }
        cout << endl;
    }
};

• 기존 Queue를 상속받아 달라지는 부분을 새로 작성하는 방식으로 구현

IsFull()

    bool IsFull()
    {
        return (this->rear + 1) % this->maxSize == this->front % this->maxSize;
    }

• 비어 있는지 여부를 확인하기 위한 1칸이 있으므로 해당 위치를 통해 Queue가 가득 차 있는지 확인할 수 있음

Enqueue(T value)

    void Enqueue(T value)
    {
        if (this->IsFull())
        {
            throw "Circular Queue is full";
        }

        this->rear = (this->rear + 1) % this->maxSize;
        this->arr[this->rear] = value;
    }

• rear부분에 값을 추가하는데 만약 끝까지 maxSize에 도달해 0으로 되돌아 가야할 수 있으므로 rear에 1을 더하고 이를 maxSize 나눈 나머지 값에 입력받은 값을 저장

  	front : 2
  	rear : 4
  	□ □ □ ■ ■
  
  	새로운 값을 추가
  	front : 2
  	rear : 0 = (4 + 1) % 5
  	■ □ □ ■ ■

Dequeue()

    T Dequeue()
    {
        if (this->IsEmpty())
        {
            throw "Circular Queue is empty";
        }

        this->front = (this->front + 1) % this->maxSize;
        return this->arr[this->front];
    }

• front는 값이 저장된 곳보다 1칸 앞에 위치하므로 한칸 뒤의 값을 가져와 반환

  	front : 4
  	rear : 1
  	■ ■ □ □ ■
  
  	값을 하나 Dequeue
  	front : 0 = (4 + 1) % 5
  	rear : 1
  	■ ■ □ □ □

Display()

    void Display()
    {
        if (this->IsEmpty())
        {
            throw "Circular Queue is empty";
        }

        int i = (this->front + 1) % this->maxSize;
        while (i != (this->rear + 1) % this->maxSize)
        {
            cout << this->arr[i] << " ";
            i = (i + 1) % this->maxSize;
        }
        cout << endl;
    }

• Dequeue()에서와 동일하게 데이터가 저장된 시작 지점을 찾아 i에 저장
• 이후 해당 값이 rear 값과 같을 동안 출력을 반복