[파이썬 알고리즘 인터뷰][스택/큐] 원형 큐 디자인

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

원형 큐 디자인

 

책에서 구현된 코드

class MyCircularQueue:

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

    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

    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

 

기억해야할 기법

• head와 rear 위치
  • rear를 head의 뒤부터 시작
• full과 empty
  • head와 rear 위치 + rear의 값으로 full/empty 판단

 

내가 구현한 코드

class MyCircularQueue:

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

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

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

    def Front(self) -> int:
        return self.arr[self.front]

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

    def isEmpty(self) -> bool:
        return (self.rear + 1) % self.size == self.front and self.arr[self.rear] == -1

    def isFull(self) -> bool:
        return (self.rear + 1) % self.size == self.front and self.arr[self.rear] != -1

• 내가 구현한 알고리즘

• 책에서 구현한 알고리즘