15강: 환형 큐(Circular Queue)

강의

큐의 활용

• 자료를 생성하는 작업과 이용하는 작업이 비동기적으로(asychronously) 일어나는 경우
• 자료를 생성하는 작업과 이용하는 작업이 양쪽 여러 곳에서 일어나는 경우

• 자료를 처리하여 새로운 자료를 생성하고, 그 자료를 또 처리해야 하는 경우

 

 

"환형 큐"는 정해진 개수의 저장 공간을 빙 돌려가며 이용하는 자료구조 입니다.

나오는 부분을 front, 넣는 부분을 rear로 지정합니다.

큐가 가득 차면 더 이상 원소를 넣을 수 없기 때문에 길이를 기억해 두어야 합니다.

 

 

자료구조 구현

• 배열 : python의 리스트 매소드 이용
• 연결 리스트 : 양방향 연결 리스트 이용

 

 

연산

• size() : 원소의 수
• isEmpty() : 비어있는지 판단
• isFull() : 꽉 차 있는지 판단
• enqueue() : 원소 추가
• dequeue() : 반환 및 제거
• peek() : 반환

 

 

15강 실습: 환형 큐 구현

⭐ 단순히 인덱스를 더해가기만 하는 것이 아니라 나머지를 이용하여 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