원형 큐(Circular Queue)는 일반적인 큐의 한계를 극복하기 위해 설계된 자료 구조이다. 일반적인 큐는 배열을 사용하여 구현할 때, 요소를 추가하거나 제거할 때마다 배열의 앞쪽 요소들을 이동시켜야 하는 문제가 발생할 수 있다. 이러한 문제를 해결하기 위해 원형 큐는 배열의 처음과 끝이 연결된 형태를 사용하여, 공간을 효율적으로 사용할 수 있다.
원형 큐의 특성
- 고정된 크기: 원형 큐는 고정된 크기의 배열을 사용하여 구현된다.
- Front와 Rear 포인터: 큐의 앞과 뒤를 가리키는 두 개의 포인터가 있다. front는 큐의 앞쪽 요소를 가리키고, rear는 큐의 마지막 요소를 가리킨다.
- 원형 배열: 배열의 마지막 인덱스 다음에는 배열의 첫 번째 인덱스가 온다. 즉, 배열이 끝나면 다시 처음으로 돌아간다.
원형 큐의 주요 연산
- Enqueue: 큐의 뒤쪽에 새로운 요소를 추가한다.
- Dequeue: 큐의 앞쪽에서 요소를 제거하고 반환한다.
- isFull: 큐가 가득 찼는지 확인한다.
- isEmpty: 큐가 비어 있는지 확인한다.
- 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 |