37. Design Circular Queue

문제

원형큐의 길이 k를 인수로 받아 원형 큐(=Ring buffer) 클래스를 구현하시오.

 

해결 방식

class MyCircularQueue:
    def __init__(self, k: int):
        self.max_length = k
        self.current_length = 0
        self.queue = [None] * k 
        self.front_index = -1 
        self.rear_index = -1 

    def enQueue(self, value: int) -> bool:
         # 1) 큐에 자리 있는지 확인
        if self.isFull():
            return False
        
        # 2) max_length가 3인 원형 큐가 [ , 2, 3]이 된 경우
        # front_index는 1, rear_index는 2.
        # 0으로 rear_index를 업데이트해서 요소를 삽입해야 함. 
        # => 모듈러를 사용해야 사용할 rear_index를 구할 수 있음.
        self.rear_index = (self.rear_index + 1) % self.max_length

        # 3) 큐에 요소 넣기
        self.queue[self.rear_index] = value

        # 4) current_length 업데이트
        self.current_length += 1

        # 5) 최초로 요소를 넣은 경우 front_index 업데이트 
        if self.current_length == 1:
            self.front_index = 0

        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        
        self.front_index = (self.front_index + 1) % self.max_length
        self.current_length -= 1
        if self.isEmpty():
            self.front_index = -1
            self.rear_index = -1
        
        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[self.front_index]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[self.rear_index]

    def isEmpty(self) -> bool:
        return self.current_length == 0

    def isFull(self) -> bool:
        return self.current_length == self.max_length

circularQueue = MyCircularQueue(3)

print(circularQueue.enQueue(1))
print(circularQueue.enQueue(2))
print(circularQueue.enQueue(3))
print(circularQueue.deQueue())
print(circularQueue.enQueue(4))

print(circularQueue.queue) # [4, 2, 3]
print(circularQueue.front_index) # front 인덱스 반환(1)
print(circularQueue.rear_index) # tail 인덱스 반환(0)