원형 큐 (Circular Queue)

강성원·2024년 1월 11일

자료구조

기본기(알고리즘, 자료구조)

목록 보기

3/8

큐에 대한 포스트

원형 큐(Circular Queue)란?

원형 큐는 선형 큐를 보완하여 Rear를 다시 맨 앞으로 배치 시키거나
Front도 동일한 방법을 사용하여 계속 배열 내부를 돌고 돌며 공간을 사용할 수 있도록 한 개념이다.

원형 큐도 배열이지만 원형큐를 사용하면 이 사진과 같이 원을 빙글빙글 도는 느낌으로 사용한다.

완성된 코드는 맨 아래에 있다.

삽입(Enqueue) / 추출(Dequeue)

Rear와 Front 이동 방법

Rear와 Front는 1씩 증가시켜서 이동하면 장땡이다.
그렇다면 배열의 맨 끝으로 간 Rear와 Front를 다시 앞으로 당겨오는 방법은 무엇일까?

Rear = (Rear+1)%n;
(n == 배열 길이)

Rear(Front)가 맨 끝에 있을 때만이 아니라 그냥 Rear(Front)의 움직임을 위 수식으로 하면된다.

Rear의 위치가 2, 배열 전체 길이가 3이라고 가정하고 설명해보자. 위 수식에 대입해보면

Rear = (2+1)%3
Rear = 3%3

결국 Rear에는 0이 대입되고 배열의 0번째 칸으로 이동하게된다.

Front도 동일한 방법으로 무한으로 순회할 수 있다.

Enqueue를 위해 배열이 꽉 차있는지 확인

Front == (Rear+1)%배열길이

Front와 Rear의 한 칸 더 진행한 위치가 같을 때 꽉 차있는 것이다.

이 그림에서도 Rear가 한 칸 더 진행하면 Front와 같아진다. (원형 큐에서는 전체 길이보다 한 칸 덜 쓴다.)

삽입(Enqueue)

임의의 상황에서 삽입을 진행해본다.
삽입을 하기 위해서는 현재 큐가 꽉 차있는지 확인해야한다.
Front == (Rear+1)%배열길이

삽입 가능한 경우위 그림에서 Front == (Rear+1)%8 의 값이 false이니 꽉 차있지 않으므로 삽입을 진행했다.

삽입 불가능한 경우위 그림에서 Front == (Rear+1)%8 의 값이 true이니 꽉 차있으므로 삽입을 진행할 수 없다.

Dequeue를 위해 배열이 비어있는지 확인

Front == Rear

맨 처음에 원소가 없을 때 Front와 Rear가 같은 곳에 위치한다. 그러해서 Front와 Rear가 같으면 비어있는 것이다.

처음에는 같은 곳에서 시작한다.

추출(Dequeue)

추출을 하기 위해서는 현재 큐가 비어있는지 확인해야 한다.
Front == Rear

추출 가능한 경우이 그림에서는 Front == Rear의 값이 false라서 비어있지 않으므로 추출이 가능하다.

추출 불가능한 경우 이 그림에서는 Front == Rear의 값이 true라서 비어있으므로 추출이 불가능하다.

구현

주의 : 원형 큐는 전체 길이보다 1칸 덜 씁니다.

public class CircularQueue<T>
{
    private T[] values;
    private int length;
    private int front = 0;
    private int rear = 0;

    public CircularQueue(int length)
    {
        values = new T[length];
        this.length = length;
    }

    public void Enqueue(T data)// 요소 삽입
    {
        if (IsFull())
        {
            Console.WriteLine("꽉 참");
            return;
        }

        values[rear++] = data;
    }

    public T Dequeue()// 요소 추출
    {
        if (IsEmpty())
            throw new InvalidOperationException("큐가 비어있음");
        
        return values[front++];
    }

    public bool IsFull()
    { return front == (rear+1)% length; }

    public bool IsEmpty()
    { return front == rear; }

    public void Print()
    {
        int i = front;
        while(i != rear)
        {
            Console.Write(values[i] + " ");
            i = (i + 1) % length;
        }
    }
}