C#으로 알아보는 원형 큐(Circular Queue)

원형 큐(Circular Queue)란?

원형 큐란, 큐의 일종으로 큐와 동일하게 FIFO(선입선출, First In, First Out)의 구조를 가지면서 선형이 아닌 원형으로 데이터를 저장하는 큐를 말한다.

 

기존 큐의 문제점인 선형으로 데이터를 쌓기 때문에 Dequeue 하는 과정에서 데이터를 꺼내오고 그다음 인덱스의 데이터들을 한 칸씩 모두 이동해야 하기 때문에 O(n)만큼의 시간 복잡도를 요구한다.

 

• 기존 큐가 선형의 구조를 가지고 있었다면 원형 큐는 원형의 구조를 가짐
• 기존 큐는 데이터 출력 시 O(n)의 시간 복잡도를 가짐
• 원형 큐는 데이터 출력 시 O(1)의 시간 복잡도를 가짐

 

원형 큐의 구성 요소

• front는 큐의 앞단을 의미
• rear는 큐의 뒷단을 의미
• 데이터 삽입시 rear가 증가한다.
• 데이터 출력시 front가 증가한다.

 

데이터 넣기(Enqueue)

큐에 데이터를 넣기 위해서는 rear의 다음 위치를 계산해야 한다.

rear에 1을 더하고 큐의 크기(queueSize)로 나눈 나머지 값이 rear의 다음 위치이다.

 

큐의 크기로 나눈 나머지 값을 사용하는 이유는 큐가 원형이기 때문에 큐의 마지막 위치에 오면 큐의 시작 위치인 0부터 다시 처리하기 위함이다.

 

rear = (rear + 1) % queueSize;
queue[rear] = data;

 

그런데 rear의 다음 위치가 만약 front와 같다면 더 이상 큐에 데이터를 넣을 수 없는 포화 상태를 의미한다.

 

front == (rear + 1) % queueSize; // 큐 포화 상태

 

 

데이터 빼기(Dequeue)

큐에서 데이터를 빼기 위해서는 front의 다음 위치를 계산해야 한다. (rear와 계산이 동일하다.)

front에 1을 더하고 큐의 크기(queueSize)로 나눈 나머지 값이 front의 다음 위치이다.

 

front = (front + 1) % queueSize;
data = queue[front];
queue[front] = null;

 

데이터를 가져오기 전에 front와 rear의 위치가 같으면 큐는 데이터가 없는 공백 상태이다.

 

front == rear // empty

 

 

예제 코드

using System;

public partial class Program
{
    static void Main(string[] args)
    {
        var q = new MyCircularQueue(5);

        Console.WriteLine(q.IsEmpty());

        q.Enqeue(1);
        q.Enqeue(2);
        q.Enqeue(3);
        q.Enqeue(4);

        Console.WriteLine(q.IsFull());

        Console.WriteLine(q.Dequeue());
        Console.WriteLine(q.Dequeue());
        Console.WriteLine(q.Dequeue());

        Console.WriteLine(q.IsEmpty());

        q.Enqeue(1);
        q.Enqeue(2);
        q.Enqeue(3);

        Console.WriteLine(q.Dequeue());
    }

    class MyCircularQueue
    {
        private int?[] q;
        private int front;
        private int rear;

        public MyCircularQueue(int size)
        {
            q = new int?[size];
            front = 0;
            rear = 0;
        }

        public void Enqeue(int item)
        {
            front = (front + 1) % q.Length;
            q[front] = item;
        }

        public int? Dequeue()
        {
            rear = (rear + 1) % q.Length;
            var result = q[rear];
            q[rear] = null;

            return result;
        }

        public bool IsFull()
        {
            return rear == (front + 1) % q.Length;
        }

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

 

참고 사이트

JavaScript Circular Queue - 원형 큐/환상 큐 만들기, Data Structures