큐와 환형 규

큐

• 큐의 동작방식은 선입 선출(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 번째에 위치해있는 것이였다.

 

아래의 그림을 참고하면 도움이 된다.