원형 큐에 대해

원형 큐를 사용하는 이유

 

  배열의 크기가 선형 큐를 사용하여 데이터를 관리하는 경우, 한번 배열을 가득 채우고 값을 1번 이상 제거한 상태라면 큐 배열의 선입선출 특성상 배열의 마지막 인덱스의 값이 비워질 때 까지 배열에 새로운 값을 추가할 수 없다. 이러한 문제를 해결하기 위해 배열의 값들이 가진 인덱스를 인위적으로 앞으로 당겨 배열을 사용해야하며한다. 이러한 비효율적 배열 사용을 방지하기 위해 원형 큐를 사용한다.

 

 

원형 큐의 원리

 

 원형 큐는 선형 큐의 단점을 보완하기 위해 큐 배의 각각의 요소를 탐색할 수있는 포인터를 사용하는데, 바로 rear와 front이다. 이 포인터들의 역할은 아래 이미지를 보면 명확하다.

<파이썬 알고리즘 인터뷰> &nbsp;p.260, 책만, 2020

 rear와 front가 0번 인덱스에 위치하고 있으며 배열에 값이 입력될 때는 rear의 위치에 값을 입력시킨 후 rear의 위치 값에 +1연산을 한다. 반면에, front는 배열의 값을 제거한 후 위치 값에 +1 연산을 진행한다. 또한, 배열의 크기보다 많은 값이 들어올 경우를 대비하여 마지막 인덱스를 항상 공백으로 유지하여 큐 배열이 가득 찬 상태를 판별한다. 이렇게 큐 배열을 사용한다면 앞서 말한 값의 입출력의 문제점을 상당부분 해소할 수 있다.

 

 

원형 큐의 구현

 

 원형 큐의 rear와 front는 값이 추가되고 제거되면서 무한히 증가할 수 있는 특성을 가진다. 그러므로 값이 늘어남에 따라 2번째 반복부터는 배열의 인덱스 번호와 포인터간의 값의 차이를 갖게 되는데, 이 차이를 상쇄하기 위해 front와 rear값을 큐 배열의 크기만큼 나눠서 그 나머지를 사용하여 큐 배열을 제어한다. 위 이미지를 기준으로 rear나 front를 배열의 크기인 5로 %연산을 한다면 실제 값이 증가하더라도 배열에 사용되는 값은 항상 같은 값을 유지한다. rear가 원형 큐를 한바퀴 돌아 값이 5가 되어도 % 연산 후에는 0으로 원형 큐를 같은 값으로 탐색 할 수 있다.

 또한 앞서 말한대로, 원형 큐에 값이 들어가기 전에는 rear == front 이고 값이 0인 상태이며, rear가 배열의 마지막 번호를 값으로 갖게 되면 한바퀴를 다 돌았다고 판단할 수 있다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _230218
{
    class Program
    {
        public static object[] arr;
        public static int front;
        public static int rear;

        static void Main(string[] args)
        {
            arr = new object[10];

            //배열이 공백이라면 인덱스를 -1로 지정하여 공백 확인
            front = -1;
            rear = -1;
        }

        public static void Enqueue(object item)
        {
            // 배열이 가득 찼는지 확인
            if ((rear + 1) % arr.Length == front) throw new ApplicationException("Full.");
            else
            {                
                if (front == -1) front++;

                rear = (rear + 1) % arr.Length; 
                arr[rear] = item;
            }
        }

        public static object Dequeue()
        {
            // 배열이 공백인지 확인
            if (front == -1 && rear == -1) throw new ApplicationException("Empty");
            else
            {
                var data = arr[front];

                if (front == rear)
                {
                    front = -1;
                    rear = -1;
                }
                else front = (front + 1) % arr.Length;

                return data;
            }            
        }
    }
}

참조 https://smilejsu.tistory.com/1972

원형배열로 구현한 Queue