원형 큐(Circular Queue)

원형 큐(Circular Queue)는 일반적인 큐의 한계를 극복하기 위해 설계된 자료 구조이다. 일반적인 큐는 배열을 사용하여 구현할 때, 요소를 추가하거나 제거할 때마다 배열의 앞쪽 요소들을 이동시켜야 하는 문제가 발생할 수 있다. 이러한 문제를 해결하기 위해 원형 큐는 배열의 처음과 끝이 연결된 형태를 사용하여, 공간을 효율적으로 사용할 수 있다.

원형 큐의 특성

1. 고정된 크기: 원형 큐는 고정된 크기의 배열을 사용하여 구현된다.
2. Front와 Rear 포인터: 큐의 앞과 뒤를 가리키는 두 개의 포인터가 있다. front는 큐의 앞쪽 요소를 가리키고, rear는 큐의 마지막 요소를 가리킨다.
3. 원형 배열: 배열의 마지막 인덱스 다음에는 배열의 첫 번째 인덱스가 온다. 즉, 배열이 끝나면 다시 처음으로 돌아간다.

원형 큐의 주요 연산

1. Enqueue: 큐의 뒤쪽에 새로운 요소를 추가한다.
2. Dequeue: 큐의 앞쪽에서 요소를 제거하고 반환한다.
3. isFull: 큐가 가득 찼는지 확인한다.
4. isEmpty: 큐가 비어 있는지 확인한다.
5. Peek/Front: 큐의 앞쪽 요소를 제거하지 않고 반환한다.

원형 큐의 동작 원리

• Enqueue 연산: rear 포인터를 이동시키고, 새로운 요소를 추가한다. 만약 rear 포인터가 배열의 끝에 도달하면, 배열의 처음으로 돌아간다.
• Dequeue 연산: front 포인터를 이동시키고, 앞쪽 요소를 제거한다. 만약 front 포인터가 배열의 끝에 도달하면, 배열의 처음으로 돌아간다.
• isFull 연산: rear 포인터가 한 칸 이동한 위치가 front 포인터와 같으면 큐가 가득 찬 상태이다.
• isEmpty 연산: front 포인터와 rear 포인터가 같은 위치에 있으면 큐가 비어 있는 상태이다.

원형 큐의 시각적 예시

Initial State:
[None, None, None, None, None]
 Front
 Rear

Enqueue 1:
[1, None, None, None, None]
 Front
  Rear

Enqueue 2:
[1, 2, None, None, None]
 Front
   Rear

Dequeue (returns 1):
[None, 2, None, None, None]
       Front
   Rear

Enqueue 3:
[None, 2, 3, None, None]
       Front
       Rear

Enqueue 4:
[None, 2, 3, 4, None]
       Front
         Rear

Enqueue 5:
[None, 2, 3, 4, 5]
       Front
           Rear

Dequeue (returns 2):
[None, None, 3, 4, 5]
           Front
           Rear

Enqueue 6 (wrap around):
[6, None, 3, 4, 5]
 Front
 Rear

원형 큐 구현 코드

class CircularQueue:
    def __init__(self, size: int):
        self._size = size
        self._values = [None for _ in range(self._size)]
        self._front_pointer = -1
        self._rear_pointer = -1

    def isFull(self) -> bool:
        if (self._rear_pointer + 1) % self._size == self._front_pointer:
            return True
        else:
            return False

    def isEmpty(self) -> bool:
        if self._front_pointer == -1:
            return True
        else:
            return False

    def enqueue(self, value):
        if self.isFull():
            print("Queue is Full")
            return
        if self.isEmpty():
            self._front_pointer = 0
        self._rear_pointer = (self._rear_pointer + 1) % self._size
        self._values[self._rear_pointer] = value

    def dequeue(self):
        if self.isEmpty():
            print("Queue is Empty")
            return None
        result = self._values[self._front_pointer]
        self._values[self._front_pointer] = None

        if self._front_pointer == self._rear_pointer:
            self._front_pointer = self._rear_pointer = -1
        else:
            self._front_pointer = (self._front_pointer + 1) % self._size
        return result

    def front(self):
        if self.isEmpty():
            print("Queue is Empty")
            return None
        return self._values[self._front_pointer]

    def display(self):
        if self.isEmpty():
            print("Queue is Empty")
        else:
            print("Queue: ", end='')
            i = self._front_pointer
            while True:
                print(self._values[i], end=' ')
                if i == self._rear_pointer:
                    break
                i = (i + 1) % self._size
            print()

cq = CircularQueue(5)
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.enqueue(40)
cq.display()  # Queue: 10 20 30 40
print(cq.dequeue())  # 10
cq.display()  # Queue: 20 30 40
cq.enqueue(50)
cq.enqueue(60)
cq.display()  # Queue: 20 30 40 50 60
cq.enqueue(70)  # Queue is Full
print(cq.front())  # 20

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms