[알고리즘 강의] 파트15. 환형 큐(Circular Queues)

큐(Queue)의 활용

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

 

 

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

 

 

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

 

 

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

 

 

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

 

 

환형 큐 (Circular Queue)

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

- 큐가 가득 차면? -> 더이상 원소를 넣을 수 없음 (큐 길이를 기억하고 있어야)

- rear: 데이터를 집어 넣는 부분 (포인터)

- front: 데이터를 꺼내는 부분 (포인터)

 

 

Q.enqueue(A)
Q.enqueue(B)
Q.enqueue(C)
r1 = Q.dequeue() # A
Q.enqueue(D)
r2 = Q.dequeue() # B

 

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

연산의 정의

- size(): 현재 큐에 들어 있는 데이터 원소의 수를 구함

- isEmpty(): 현재 큐가 비어 있는지를 판단

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

- enqueue(x): 데이터 원소 x를 큐에 추가

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

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

 

실습 과제 - 배열로 구현한 환형 큐

핵심: 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

 

* 프로그래머스의 '어서와! 자료구조와 알고리즘은 처음이지?' 강의를 듣고 정리하였습니다.