큐
- 큐의 동작방식은 선입 선출(FIFO)이다.
동작 방식
동작방식의 도식화는 아래와 같다.
- enqueue() : 후순위로 밀어 넣다. - 복잡도 O(1)
- dequeue() : 선순위를 빼낸다. - 복잡도 O(n)
- 배열에서의 dequeue()를 맨 앞의 원소를 빼면 다른 모든 원소를 한칸씩 이동해야하기 때문에 복잡도는 O(n)이다.
- → 따라서 이를 해결하기 위해 환형 큐를 이용한다.
사용처
큐는 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우에 사용한다.
나도 프로젝트를 이용하면서 많은 Message queue를 사용해본적이 있으며, 실제로 네트워크 강의를 들으면서 패킷이 전송이 큐(버퍼)를 통해 이루어지는 것을 학습했었다.
환형 큐
배열에서 dequeue()의 복잡도(O(n))을 줄이기 위해 환형큐를 사용할 경우, 원소를 앞으로 미룰 필요가 없어 복잡도가 O(1)로 향상 됨을 알 수 있다.
front와 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
enqueue()와 dequeue()에서 rear와 front에 +1을 해주는 것은 이해가 갔지만 peek()를 할 경우에 왜 +1을 해주는지 이해가 가지않았다.
이 코드는 빈칸 채우기이므로 로직을 변경할 수 없었기 때문에 rear와 front를 queue에 값을 넣기 시작하면 0으로 초기화 시기고 있지 않았다는게 문제이다. front 인덱스에 +1을 한뒤에 dequeue를 진행하기 때문에 front 인덱스에 해당하는 값에는 아무것도 없고, 가장 오래 큐에 들어온 원소의 값 front+1 번째에 위치해있는 것이였다.
아래의 그림을 참고하면 도움이 된다.