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

원형 큐란?

• 원형 큐(Circle Queue)는 큐의 한 형태이다.
• 큐를 배열로 구현을 하게 될 경우, 데이터를 삭제하게 되면 삭제한 부분은 더 이상 사용할 수 없다.
• 이 경우 삭제를 배열 끝까지 하게 되면 그 큐는 더 이상 사용할 수 없게 된다.
• 이때 사용하는 것이 바로 원형 큐이다.

원형 큐의 특징

• 원형 큐의 경우, 일반적으로 배열로 구현한다.
• 원형 큐는 배열의 앞과 끝을 이어 배열에 끝에 도달했다면 다시 처음으로 되돌아오는 큐를 의미한다.
• 배열의 앞을 가리키는 변수(front)와 배열의 끝을 가리키는 변수(rear)를 통해 데이터를 삽입하고 삭제한다.
  • 데이터를 삽입할 때마다 rear가 한 칸 증가한다.
  • 데이터를 삭제하면 front가 한 칸 증가한다.
  • 만일 rear가 배열의 끝에 도달했는데, 배열의 시작이 비어있다면 rear의 인덱스는 0을 가리킨다.
• 원형 큐는 큐의 특성을 지니고있어 선입선출을 유지한다.
• 원형 큐의 연산은 삽입, 삭제, 맨 앞의 값 읽기, 원형 큐가 꽉 차있는지, 원형 큐가 비어있는지 확인이 있다.

시간복잡도

1. 삽입(Enqueue)
   • 원형 큐에 값을 넣고 rear의 값을 1 증가한다.
   • 따라서 시간복잡도는 O(1)이다.
2. 삭제(Dequeue)
   • 원형 큐의 값을 제거하고 front의 값을 1 증가한다.
   • 따라서 시간복잡도는 O(1)이다.
3. 맨 앞의 값 읽기(Peek)
   • 원형 큐의 rear에 해당하는 값을 읽어온다.
   • 따라서 시간복잡도는 O(1)이다.
4. 배열이 꽉 차있는지(IsFull)
   • rear와 front의 위치를 통해 배열이 꽉 차있는지 확인한다.
   • 따라서 시간복잡도는 O(1)이다.
5. 배열이 비어있는지(IsEmpty)
   • rear와 front의 위치를 통해 배열이 비어있는지 확인한다.
   • 따라서 시간복잡도는 O(1)이다.

원형 큐의 장단점

1. 장점
   • 큐를 활용하기에 선입선출 구조이며, 배열로 구현된 큐처럼 공간을 낭비하지 않아도 된다.
   • front와 rear를 활용해 인덱스만을 관리해주면 되기에 비교적 구현이 쉽다.
2. 단점
   • 배열로 구현하기 때문에 크기가 고정되어 있어, 너무 크게 선언을 하게 되면 메모리를 낭비하게 된다.
   • front와 rear를 통해 배열이 비어있는지, 꽉차있는지에 대한 추가적인 구현이 필요하다.

예제

package QueueExample

class CircleQueue(size: Int) {
    private val queueSize: Int
    private var circleQueue = emptyArray<Int>()

    private var rear: Int = -1
    private var front: Int = -1

    init {
        queueSize = size;
        circleQueue = Array(queueSize) { -1 }
    }

    fun isEmpty(): Boolean {
        return rear == front && circleQueue[rear] == -1
    }

    fun isFull(): Boolean {
        if(rear == front -1 && circleQueue[front] == -1)
            return false

        return rear == front - 1 || (front == -1 && rear == queueSize - 1) || (rear == front && front != -1 && circleQueue[front] != -1)
    }

    fun enqueue(element: Int): Boolean {
        return if(isFull())
            false
        else
        {
            rear = if(rear + 1 == queueSize) 0 else rear + 1
            circleQueue[rear] = element
            true
        }

    }

    fun dequeue(): Int {
        return if(isEmpty())
            -1
        else
        {
            front = if(front + 1 == queueSize) 0 else front + 1
            var data = circleQueue[front]
            circleQueue[front] = -1
            data
        }
    }
}

fun main() {
    var circleQueue = CircleQueue(5)
    circleQueue.enqueue(1)
    circleQueue.enqueue(2)
    println(circleQueue.isFull())
    circleQueue.enqueue(3)
    circleQueue.enqueue(4)
    circleQueue.enqueue(5)
    println(circleQueue.isFull())

    println("원형 큐에서 꺼낸 값 : ${circleQueue.dequeue()}")
    println("원형 큐에서 꺼낸 값 : ${circleQueue.dequeue()}")
    println("원형 큐에서 꺼낸 값 : ${circleQueue.dequeue()}")
    println(circleQueue.isEmpty())
    println("원형 큐에서 꺼낸 값 : ${circleQueue.dequeue()}")
    println("원형 큐에서 꺼낸 값 : ${circleQueue.dequeue()}")
    println(circleQueue.isEmpty())
}