파이썬 알고리즘 인터뷰 - 원형 큐 디자인

문제

원형 큐를 디자인하라.

초기 셋팅

class MyCircularQueue:

    def __init__(self, k: int):


    def enQueue(self, value: int) -> bool:


    def deQueue(self) -> bool:
    

    def Front(self) -> int:


    def Rear(self) -> int:


    def isEmpty(self) -> bool:


    def isFull(self) -> bool:

입력

["MyQueue","push","push","peek","pop","empty"]
[[],[1],[2],[],[],[]]

출력

[null,null,null,1,1,false]

작성한 코드

class MyCircularQueue:

    def __init__(self, k: int):
        self.q = [None]*k
        self.maxlen = k
        self.front = 0
        self.rear = 0

    def enQueue(self, value: int) -> bool:
        if self.q[self.rear] is None:
            self.q[self.rear] = value
            # rear값이 +1 이되고, 원형이 때문에 rear 값이 maxlen를 초과했을때,
            # 다시 처음 인덱스로 시작해야 하기 때문에 maxlen으로 나눈 나머지 값을 넣어야 한다.
            self.rear = (self.rear + 1) % self.maxlen
            return True
        else:
            return False

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


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

    def Rear(self) -> int:
        # rear 값은 enQueue할 때 현재 rear에서 값을 넣은 다음에 rear값을 +1 해주기 때문에,
        # rear 값을 -1 해줘야 마지막으로 들어간 데이터값을 확인할 수 있다.
        return -1 if self.q[self.rear - 1] is None else self.q[self.rear - 1]

    def isEmpty(self) -> bool:
        if self.front == self.rear and self.q[self.front] is None:
            return True
        return False

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

리트코드에서 확인

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

Design Circular Queue - LeetCode

회고

처음 접근하기가 어려워서 책에있는 코드를 살펴 보았다.

리스트를 k개 만큼 만들어서 데이터를 넣고, 2개의 포인트를 사용해서(rear, front) 원형 큐를 구현하는 방식이었다.

주석에 있는 내용은 처음에 봤을때 이해하지 못한 부분이고, 다시 지우고 풀어봐야겠다.