본문 바로가기

Data structure & Algorithms study

원형 큐(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

728x90

'Data structure & Algorithms study' 카테고리의 다른 글

이중 연결 리스트 (Doubly Linked List)  (0) 2024.06.11
단일 연결 리스트 (Singly Linked List)  (0) 2024.05.27
덱 (Deque)  (0) 2024.05.27
큐 (Queue)  (0) 2024.05.26
스택(Stack)  (0) 2024.05.23