[프로그래머스 강의] 15강 환형 큐

---

'어서와! 자료구조와 알고리즘은 처음이지?'

---

큐의 활용

1. 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비 동기적으로(asynchronously) 일어나는 경우

2. 자료를 생성하는 작업이 여러 곳에서 일어나는 경우 

3. 자료를 이용하는 작업이 여러 곳에서 일어나는 경우

4. 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우

5. 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우

환형 큐

정해진 개수의 저장공간을 빙 돌려가며 이용하는 큐

환형 큐의 추상적 자료구조 구현

연산의 정의

1. size() - 현재 큐에 들어있는 데이터 원소의 수를 구한다.

2. isEmpty() - 현재 큐가 비어 있는지를 판단한다.

3. isFull() - 큐에 데이터 원소가 꽉 차 있는지를 판단한다.

4. enqueue(item) - 데이터 원소 item을 큐에 추가한다.

5. dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 제거한다(또한 반환).

6. peek() - 큐의 맨 앞에 저장된 데이터 원소를 반환한다(제거하지 않음).

 

[ 문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