원형 큐(Queue)는 FIFO 구조를 가지고 있는 점에서 기존 큐(Queue)와 동일하다
마지막 위치가 시작 위치와 연결되는 점이 다른 점이다.
기존의 큐는 공간이 꽉 차게 되면 더 이상 요소를 채울 수 없다.
기존 큐는 앞쪽 값들이 빠져서 충분한 공간이 생기는 것처럼 보여도 해당 위치로 추가할 수 없다.
원형 큐는 앞쪽 요소들이 빠지더라도 원형으로 이뤄져 있기 때문에 앞쪽에 추가 할 수 있다.
즉, 재활용이 가능한 자료구조이다.
원형 큐 삽입 삭제 원리
출처 : 파이썬 알고리즘 인터뷰 p.260
마지막 위치와 시작 위치를 연결하도록 원형 구조를 세팅하고, 값의 시작점과 끝점을 따라 투 포인터가 움직인다.
위 그림을 참고하면, enQueue() 를 통해 rear 포인터를 이동시키고, deQueue 를 통해 front 포인터를 이동시킨다.
이 로직을 통해 투 포인터가 돌면서 이동하게 된다.
만약 rear 포인터와 front 포인터가 만나게 되면 해당 원형 큐 구조에 여유 공간이 없다는 의미이므로 공간 부족 에러를 발생해야 한다.
원형 큐 구현 풀이
배열을 사용하여 구현한다.
rear 포인터와 front 포인터를 구분한다
현재 포인터의 위치를 전체 큐 값의 개수에 따라 제한한다.
속도 : 52ms
class MyCircularQueue(object):
def __init__(self, k: int):
self.q = [None] * k # 원형 큐 정의 (배열 활용)
self.maxlen = k # 최대 길이 정의
self.fp = 0 # front pointer
self.rp = 0 # rear pointer
def enQueue(self, value: int) -> bool:
# 값을 추가할 때는 rear pointer 활용한다
# rear 포인터 위치에 있는 큐 값이 없으면 입력된 value를 넣어준다
if self.q[self.rp] is None:
self.q[self.rp] = value
# 입력해준 후 rear 포인터이 값을 업데이트 한다
self.rp = (self.rp + 1) % self.maxlen
return True
else:
return False
def deQueue(self) -> bool:
"""
원형 큐의 첫 번째 값이 제거되도록 기능 구현
"""
# 값을 삭제할 때는 front pointer를 활용한다.
# front pointer의 값이 아무것도 없으면 삭제할 값이 없다는 의미
if self.q[self.fp] is None:
return False
# 값이 있으면, 그 값을 삭제하되 출력(반환)되지 않도록 세팅 필요
else:
self.q[self.fp] = None
# front pointer를 업데이트한다.
self.fp = (self.fp + 1) % self.maxlen
return True
def Front(self) -> int:
"""
원형큐의 맨 앞에 있는 값을 반환
값이 없을 경우 -1 반환
"""
return -1 if self.q[self.fp] is None else self.q[self.fp]
def Rear(self):
"""
:rtype: int
원형 큐의 맨 뒤에 있는 값을 반환
값이 없을 경우 -1 반환
"""
# rear pointer 에서 1을 빼준 위치에서 값을 가져와야 한다.
return -1 if self.q[self.rp - 1] is None else self.q[self.rp - 1]
def isEmpty(self):
"""
:rtype: bool
값이 비어 있을 경우 True, 아닐 경우 False
포인터의 위치가 같은데 front pointer의 값이 없다면 해당 원형 큐의 값을 아무것도 없는 비어있는 상태라는 의미
"""
return self.fp == self.rp and self.q[self.fp] is None
def isFull(self):
"""
:rtype: bool
값이 모두 채워져 있는 경우를 아래와 같은 로직으로 판단
우선 포인터의 위치가 같아야 하며, 그럴 때 front pointer의 값이 채워져 있어야 한다.
"""
return self.fp == self.rp and self.q[self.fp] is not None
