[LeetCode] #622. Design Circular Queue (python)

문제

https://leetcode.com/problems/design-circular-queue/

Design Circular Queue - LeetCode

원형 큐를 디자인하는 문제다. 

 

원형 큐란?

기존의 큐와 같은 구조를 갖지지만 마지막 위치와 시작 위치가 연결되기 때문에 원형 큐라고 부른다.

기존 큐는 deQueue로 공간이 생겨도 해당 공간을 다시 사용할 수 없었는데 원형 큐는 해당 공간을 재활용할 수 있다.

 

예시 입출력

Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

 

 

풀이

 

내 풀이

class MyCircularQueue:

    def __init__(self, k: int):
        self.q=[-1]*(k+1)
        self.rear=0
        self.front=0
        self.k=k+1

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        else:
            self.rear=(self.rear+1)%self.k
            self.q[self.rear]=value
            return True
        

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        else:
            self.q[(self.front+1)%self.k]=-1
            self.front=(self.front+1)%self.k
            return True

    def Front(self) -> int:
        return self.q[(self.front+1)%self.k]

    def Rear(self) -> int:
        return self.q[self.rear]

    def isEmpty(self) -> bool:
        return self.rear==self.front

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

원형 큐가 가득 찬 것을 rear+1==front로 판단하기 위해 빈 공간을 하나 더 잡아서 큐를 정의했다.

 

책 풀이

class MyCircularQueue:
    def __init__(self, k: int):
        self.q = [None] * k
        self.maxlen = k
        self.p1 = 0
        self.p2 = 0

    # enQueue(): 리어 포인터 이동
    def enQueue(self, value: int) -> bool:
        if self.q[self.p2] is None:
            self.q[self.p2] = value
            self.p2 = (self.p2 + 1) % self.maxlen
            return True
        else:
            return False

    # deQueue(): 프론트 포인터 이동
    def deQueue(self) -> bool:
        if self.q[self.p1] is None:
            return False
        else:
            self.q[self.p1] = None
            self.p1 = (self.p1 + 1) % self.maxlen
            return True

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

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

    def isEmpty(self) -> bool:
        return self.p1 == self.p2 and self.q[self.p1] is None

    def isFull(self) -> bool:
        return self.p1 == self.p2 and self.q[self.p1] is not None

책에서는 데이터를 삽입할 때 해당 공간이 비었는지 확인하고 데이터를 삽입한 후 해당 포인터를 증가시켰다. 대신 모듈러 연산을 해서 포인터가 maxlen 보다 커지지 않게 했다.

삭제할 때는 해당 위치에 None을 넣어서 삭제를 했다. 삭제를 한 후에 front 포인터인 p1포인터를 증가시켰다.

 

참고한 책 : 파이썬 알고리즘 인터뷰