본문 바로가기
Study/Algorithm

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

by 투말치 2022. 3. 9.

목차

반응형

문제

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

 

Design Circular Queue - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

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

 

원형 큐란?

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

기존 큐는 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포인터를 증가시켰다.

 

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

반응형