[알고리즘][스택 & 큐] - 6. 원형 큐 디자인

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/design-circular-queue/

원형 큐를 디자인 하라.

---

[원형 큐란?]

• 원형 큐 = 환형 큐
• FIFO(선입선출) 구조
• 그러나 처음 위치와 마지막 위치가 연결된다.
  • 이때문에 Ring Buffer라고 부른다.
• 기존의 큐는 요소가 꽉 차게 되면 더 이상 요소를 추가할 수 없었다. 심지어는 앞에 요소가 남아도 충분한 공간이 있어도 추가할 수 없다. 
  
  • 이때 충분한 공간이 남게 돼도 그 쪽으로 추가할 수 있는 방법이 동그랗게 연결해서 앞쪽으로 추가할 수 있도록 재활용 가능한 구조로 바꾼 것이 원형 큐이다. 

https://media.vlpt.us/images/ny_/post/f935c7bc-1a91-4782-ae6c-b3b271aa136e/image.png

• 요소 시작점과 끝점을 따라 투 포인터가 움직인다.
  • enQueue()를 하면 front 포인터가 앞으로 이동한다.
  • deQueue()를 하면 rear 포인터가 뒤로 이동한다.
• 이때 rear 포인터와 front 포인터가 같은 위치에서 서로 만나게 된다면, 그때는 정말로 여유 공간이 하나도 없다는 이야기가 된다

 

 

[배열을 이용한 풀이]

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:
        #뺄 값이 없으면 false를 돌려준다.
        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

• enqueue() dequeue()가 될 때 포인터 p1, p2 모두 +1 이 되는 이유는 값을 뺄 때도 p1 포인터가 한 칸이 뒤로 밀려야 하고 값을 넣어줄 때도 p2 포인터가 한 칸 밀려야 하기 때문이다.
• 비어있는 것은 두 개의 포인터가 같은 위치에 있고 p1 포인터가 None 일때는 아무것도 없다는 뜻이기 때문에 true를 보내준다. 
• 가득 차 있다는 것은 두 개의 포인터가 같은 위치에 있고, p1 포인터가 None이 아니면 가득 차 있다는 뜻으로 true를 보내준다. (가득 안 찼으면 false)