[LeetCode] 622. Design Circular Queue(Python/순환 큐)

순환 큐(Circular Queue)

• 기존의 선형 자료구조를 갖는 일반 큐(Normal Queue)를 보완하기 위한 큐
• 데이터를 꺼낸 후 빈 공간에 다시 데이터를 삽입하는 것이 불가능해 공간 낭비가 심한 일반 큐의 단점을 보완하기 위해 설계
• 기존의 큐와 같이 FIFO 데이터 삽입 구조를 가짐
• 원형으로 연결하여 공간이 남으면 지속적으로 데이터를 삽입할 수 있도록 함

순환 큐의 동작 원리

• front : 가장 먼저 들어온 데이터
• rear : 가장 나중에 들어온 데이터
• enQueue : rear을 1 증가시키고 rear의 위치에 데이터를 삽입한다. 하지만 공간이 꽉 차 있다면(rear + 1 == front) 에러 발생
• deQueue : queue[front]의 데이터를 출력하고 front를 1증가시킨다. 하지만 공간이 비어 있다면(rear == front == -1) 에러 발생
• isEmpty() : 공간이 비어 있을 때
• isFull() : 공간이 꽉 차 있을 때

풀이

순환 큐에 대한 개념은 이곳을 참조

• front와 rear는 가리키는 값이 비어 있는 경우 -1을 출력
• enQueue
  • 공간이 꽉 차 있는 경우 false 리턴
  • 만약 비어 있었다면(front == -1) front 값 1 증가
• deQueue
  • 공간이 비어 있다면 false 리턴
  • 만약 꺼낸 데이터가 마지막 값이라면 이 값을 끝으로 공간이 비게 되므로 front와 rear 둘 다 -1로 초기화

class MyCircularQueue:

    def __init__(self, k: int):
        self.Q = [-1]*k
        self.front = self.rear = -1
        self.N = k

    def enQueue(self, value: int) -> bool:
        if self.isFull(): # no space to save data
            return False
        if self.rear == -1:
            self.front = 0
        self.rear = (self.rear+1)%self.N
        self.Q[self.rear] = value
        return True

    def deQueue(self) -> bool:
        if self.isEmpty(): # if queue has data to delete
            return False

        self.Q[self.front] = None
        if self.front == self.rear:
            self.front = self.rear = -1
        else: self.front = (self.front+1)%self.N
        return True

    def Front(self) -> int:
        return self.Q[self.front] if self.front != -1 else -1

    def Rear(self) -> int:
        return self.Q[self.rear] if self.rear != -1 else -1

    def isEmpty(self) -> bool:
        return self.front == -1 and self.rear == -1
        
    def isFull(self) -> bool:
        return (self.rear+1)%self.N == self.front


# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()

😇 풀이 개선(교재)

class MyCircularQueue:

    def __init__(self, k: int):
        self.cQ = [None]*k
        self.f = self.r = 0
        self.maxlen = k

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False

        self.cQ[self.r] = value
        self.r = (self.r+1)%self.maxlen
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        
        self.cQ[self.f] = None
        self.f = (self.f+1)%self.maxlen
        return True

    def Front(self) -> int:
        return -1 if self.cQ[self.f] is None else self.cQ[self.f]

    def Rear(self) -> int:
        return -1 if self.cQ[self.r-1] is None else self.cQ[self.r-1]

    def isEmpty(self) -> bool:
        return self.r == self.f and self.cQ[self.f] is None

    def isFull(self) -> bool:
        return self.r == self.f and self.cQ[self.f] is not None


# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()