15강: 환형 큐(Circular Queue)

유태형·2022년 3월 10일

알고리즘 파이썬 프로그래머스

15강 요약

환형 큐란?

환형 큐의 메서드

문제

GitHub

알고리즘 - Python

목록 보기

11/16

15강 요약

큐는 입력방향과 출력방향이 동일하기 때문에 스택과 다르게 자료의 크기가 커지거나, 오래 사용 될수록 O(n)이 커지는 단점이 존재한다. 이를 해결하기 위해 원형으로 큐를 이용하는것이 환형 큐(Circular Queue)이다.

환형 큐란?

정해진 개수의 저장공간을 빙 돌아가며 이용하는 큐이다.
이전엔 단순히 넣고 빼고 정렬하고를 하며 O(n)의 복잡도를 가졌다. 하지만 환형 큐에선 front로 데이터를 빼는, rear로 데이터를 입력하는 위치를 가진다. 입력과 출력을 따로 관리함으로써 항상 정렬을 하지 않아도 된다.

환형 큐의 메서드

size() - 현재 큐에 들어 있는 원소의 수
isEmpty() - 현재 큐가 비어 있는지
isFull() - 큐에 데이터 원소가 꽉 차 있는지를 판단
enqueue(x) - 데이터 원소 x를 큐에 추가
dequeue() - 큐에 맨앞에 저장된 데이터 원소 제거
peek() - 큐의 맨 앞에 저장된 데이터 원소 반환

환형 큐는 크기도 정해져 있기때문에 꽉 찼는지 여부도 확인해야 하므로 isFull()이 추가 되었다.

	def __init__(self, n):
        self.maxCount = n #큐의 크기
        self.data = [None] * n
        self.count = 0
        self.front = -1 #출력
        self.rear = -1 #입력
        
	def isFull(self): #꽉 찼는지 여부
        return self.count == self.maxCount

self.maxCount : 큐의 크기르 저장한다.
self.front : 큐의 출력 인덱스
self.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

원형을 생각해보면 한바퀴를 돌면 제자리로 돌아와야 한다. 즉 마지막 인덱스에서 +1칸 움직이면 첫 인덱스로 돌아와야한다.