프로그래머스 강의_15

환형 큐(Circular Queues)

큐 (Queue)의 활용

• 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 (asynchronously) 일어나는 경우
• 자료를 생성하는 작업이 여러 곳에서 일어나는 경우
• 양쪽 다 여러 곳에서 일어나는 경우
• 자료를 처리하여 새로운 자료를 생성하고 나중에 그 자료를 또 처리해야 하는 작업의 경우

환형 큐

• 정해진 갯수의 저장 공간을 빙 돌려가며 이용
• Q.enqueue(A)
• Q.enqueue(B)
• Q.enqueue(c)
• r1 = Q.dequeue() => A
• r1.enqueue(D)
• r2 = Q.dequeue() => B
• 데이터를 꺼내는 쪽은 front, 데이터를 넣는 쪽은 rear
• 큐가 가득차면? => 더이상 원소를 넣을 수 없음
  ==> 큐 길이를 기억하고 있어야 함. 물론 rear와 front가 만나면 넣을 수 없다는 것을 사용할 수 도 있다

연산의 정의

• size() : 현재 큐에 들어있는 데이터 원소의 수를 구함
• isEmpty() : 현재 큐가 비어있는지를 판단
• isFull() : 큐에 데이터 원소가 꽉 차 있는지를 판단
• enqueue(x) : 데이터 원소 x를 큐에 추가
• dequeue() : 큐의 맨 앞에 저장된 데이터 원소를 제거(또한, 반환)
• peek() : 큐의 맨 앞에 저장된 데이터 원소를 반환(제거하지 않음)

배열로 구현한 환형 큐

• 정해진 길이 n의 리스트를 확보해 두고
• A <-(rear), Q.enqueue(B) => B(rear)
• 계속해서 rear값이 바뀜
• Q.dequeue() => front => (A) 0번 인덱스에서 A는 있지만 큐에서는 유효한 데이터로 취급하지 않음
• Q.dequeue() => front => (B)
• ABCDEF 다 있는 것처럼 보이지만 A와 B는 무효한 데이터로 덮어쓸 수 있음.
• 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():
           # IndexError('Queue full')exception으로 처리
       self.rear = (self.rear + 1) % self.maxCount
       self.data[self.rear] = x
       self.count += 1
   ## 큐에서 데이터 원소 뽑아내기
   def dequeue(self):
       if self.size() == 0 :
           raise IndexError('Queue empty')
       self.front = (self.front+1) % self.maxCount
       x = self.data[self.front]
       self.count -= 1
       return x
   ## 큐의 맨 앞 원소 들여다보기
   def peek(self):
       ifself.isEmpty():
           raise IndexError('Queue empty')
       return self.data[(self.front+1) % self.maxCount]