15강 요약
큐는 입력방향과 출력방향이 동일하기 때문에 스택과 다르게 자료의 크기가 커지거나, 오래 사용 될수록 O(n)이 커지는 단점이 존재한다. 이를 해결하기 위해 원형으로 큐를 이용하는것이 환형 큐(Circular Queue)이다.
환형 큐란?
정해진 개수의 저장공간을 빙 돌아가며 이용하는 큐이다.
이전엔 단순히 넣고 빼고 정렬하고를 하며 O(n)의 복잡도를 가졌다. 하지만 환형 큐에선 front로 데이터를 빼는, rear로 데이터를 입력하는 위치를 가진다. 입력과 출력을 따로 관리함으로써 항상 정렬을 하지 않아도 된다.
환형 큐의 메서드
size() - 현재 큐에 들어 있는 원소의 수
isEmpty() - 현재 큐가 비어 있는지
isFull() - 큐에 데이터 원소가 꽉 차 있는지를 판단
enqueue(x) - 데이터 원소 x를 큐에 추가
dequeue() - 큐에 맨앞에 저장된 데이터 원소 제거
peek() - 큐의 맨 앞에 저장된 데이터 원소 반환
환형 큐는 크기도 정해져 있기때문에 꽉 찼는지 여부도 확인해야 하므로 isFull()이 추가 되었다.
def __init__(self, n):
self.maxCount = n #큐의 크기
self.data = [None] * n
self.count = 0
self.front = -1 #출력
self.rear = -1 #입력
def isFull(self): #꽉 찼는지 여부
return self.count == self.maxCountself.maxCount : 큐의 크기르 저장한다.
self.front : 큐의 출력 인덱스
self.rear : 큐의 입력 인덱스
문제
class CircularQueue:
def __init__(self, n):
self.maxCount = n
self.data = [None] * n
self.count = 0
self.front = -1
self.rear = -1
def size(self):
return self.count
def isEmpty(self):
return self.count == 0
def isFull(self):
return self.count == self.maxCount
def enqueue(self, x):
if self.isFull():
raise IndexError('Queue full')
self.rear = (self.rear+1)%self.maxCount
self.data[self.rear] = x
self.count += 1
def dequeue(self):
if self.isEmpty():
raise IndexError('Queue empty')
self.front = (self.front+1)%self.maxCount
x = self.data[self.front]
self.count -= 1
return x
def peek(self):
if self.isEmpty():
raise IndexError('Queue empty')
return self.data[(self.front+1)%self.maxCount]
def solution(x):
return 0
원형을 생각해보면 한바퀴를 돌면 제자리로 돌아와야 한다. 즉 마지막 인덱스에서 +1칸 움직이면 첫 인덱스로 돌아와야한다.
따라서
front와rear가 1칸 움직일때마다%self.maxCount로 큐의 크기만큼 나누어 줌으로써 마지막 인덱스의 다음 인덱스는 항상 첫 인덱스가 될 수 있도록 한다.
GitHub
