[리트코드] Design Circular Queue(python)

리트코드, Design Circular Queue_원형 큐 구현하기

 

TL;DR

• 원형 큐(Circular Queue)에 대해서 이해하고 있는지

문제 분석

1. First In, First Out(FIFO) 특징을 갖고 있는, 큐의 마지막이 큐의 처음과 연결되어 있는 '링 버퍼' 구조를 갖고 있는 원형 큐를 구현하여라.
2. MyCircularQueue(k) : 큐의 길이가 k인 원형 큐를 생성한다.
3. Front() : 큐의 가장 앞에 있는 원소를 가져온다. 만약 큐가 비어있다면 -1을 반환한다.
4. Rear() : 큐의 가장 뒤에 있는 원소를 가져온다. 만약 큐가 비어있다면 -1을 반환한다.
5. enQueue(value) : value를 큐에 삽입한다. 성공적으로 실행되었을 경우 True를 반환한다.
6. deQueue() : 원형 큐로부터 원소를 제거한다. 성공적으로 실행되었을 경우 True를 반환한다.
7. imEmpty() : 원형 큐가 비어있는지 아닌지를 반환한다.
8. isFull() : 원형 큐가 가득 차 있는지 아닌지를 반환한다.

 

- 5 : enQueue()의 경우 원형 큐의 가장 뒤에 원소를 삽입한다. 단, 원형 큐가 가득 차 있다면 실행할 수 없다. 이미 원형 큐가 가득 차있기 때문이다. 이 때는 False를 반환하며, 아무 동작이 일어나지 않는다.

- 6 : deQueue()의 경우 원형 큐의 가장 앞에 있는 원소를 반환해야 한다. 원형 큐가 비어 있을 경우에는 뺄 수 있는 원소가 없으므로 False를 반환하며, 아무 동작이 일어나지 않는다.

- 7 : 원형 큐가 비어 있을 경우는 원형 큐의 가장 앞과 뒤를 나타내는 일종의 포인터인 front와 rear가 같은 위치에 있고, 해당 위치에 원소가 비어있어야 한다.(원소가 존재하면 안된다.)

- 8 : 원형 큐가 가득 차 있을 경우는, 원형 큐의 가장 앞과 뒤를 나타내는 일종의 포인터인 front와 rear가 같은 위치에 있고, 해당 위치에 원소가 비어있지 않아야 한다.(원소를 담고 있어야 한다.)

풀이

class MyCircularQueue:

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

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

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

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

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

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

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

 

- init

    - q : 원형 큐가 되는 k 길이의 리스트를 선언한다. 원소는 아무 것도 없는 None을 담도록 한다. 0으로 하지 않는 이유는 입력으로 0이 주어질 수 있기 때문이다.

    - max_len : 원형 큐의 최대 길이인 k를 할당한다. 원형 큐를 front와 rear 두 포인터가 돌며 조회할 때, 최대 길이를 넘지 않도록 하는데 사용된다.

    - front, rear : 각각 큐의 가장 앞과 뒤를 가르키는 포인터이다.

 

- enQueue : 원형 큐의 삽입이 될 때는 rear 포인터를 이동시킨다. rear 포인터에 원소가 없다면 해당 위치에 원소를 삽입하고, rear를 다음 위치로 이동시킨다. 이 때, max_len으로 나눈 나머지를 할당하여, 원형 큐의 최대 크기를 벗어나지 않도록 한다.

- deQueue : 원형 큐에서 원소를 제거할 때는 front 포인터를 이동시킨다. front 포인터에 원소가 있다면 해당 위치의 원소를 제거하고, front를 다음 위치로 이동시킨다. 이 때도 마찬가지로, max_len으로 나눈 나머지가 되도록 하여 원형 큐를 벗어나지 않도록 한다.

- Front : 원형 큐의 가장 앞의 원소를 반환한다. front 위치에 원소가 존재하지 않다면 -1을, 존재한다면 해당 원소를 반환한다.

- Rear : 원형 큐의 가장 뒤의 원소를 반환한다. 이 때, 주의해야할 점은 enQueue 연산에서 원형 큐의 삽입이 일어난 이후 rear가 1 증가한다는 것이다. 실제 원형 큐의 가장 마지막에 삽입된 원소는 rear - 1 위치에 존재해야 하므로, 해당 부분을 조건에 명시해야 한다.

- isEmpty & isFull : 문제 분석에서 적은 것과 같이 front와 rear가 같을 때, 그리고 empty는 원소가 없을 때, full은 원소가 있을 때를 확인하여 반환하면 된다.