[LeetCode] 622. design_circular_queue (Medium) 2023/5/10

문제 제목	정답률	난이도
622. design_circular_queue	51.5%	Medium

Design Circular Queue - LeetCode

 

 

문제요약

원형 큐를 만들어라

원형큐가 보통의 큐와 다른 점은 제일 뒤의 주소가 제일 앞의 주소와 연결되어 있다는 것이다(보통 크기가 고정되어 있다)

일반 큐와 다르게 앞쪽과 연결되어 있어 앞부분의 주소를 재사용할 수 있어 메모리 사용량에 있어 유리하다

• def __init__(self, k: int):    k 크기의 원형큐를 선언
• def enQueue(self, value: int) -> bool:    value 값을 원형큐에 삽입하는 함수

• def deQueue(self) -> bool:    원형큐의 front 인덱스의 값을 삭제하는 함수 (큐이니까 FIFO)

• def Front(self) -> int:    원형큐의 front 인덱스의 값을 반환하는 함수

• def Rear(self) -> int:    원형큐의 rear 인덱스의 값을 반환하는 함수

• def isEmpty(self) -> bool:    원형큐가 비었는지 판단하는 함수

• def isFull(self) -> bool:    원형큐에 자리가 없는지 판단하는 함수

 

 

풀이 1

원형 큐는 리스트와, front, rear 인덱스를 이용하여 구현할 수 있다.

front 인덱스는 원형 큐에서 제일 먼저 삽입된 값을 가리키고, rear는 원형 큐에서 제일 나중에 삽입된 값을 가리킨다.

 

구현 순서는 구현하기 용이한것부터 한다

모든 함수를 구현할 때,

• 일반적인 경우
• rear, front의 인덱스가 제일 끝자리(len(원형큐)-1)에 있는 경우를 나누어 생각하자(해당 인덱스의 다음 인덱스는 0이기 때문이다)

__init__

front, rear

isEmpty, isFull

enQueue, deQueue

 

 

구현 (82ms)

class MyCircularQueue:

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

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        if self.isEmpty()!=True:
            if self.rear!=(len(self.circularqueue)-1):
                self.rear+=1
            else:
                self.rear=0
        self.circularqueue[self.rear]=value
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.circularqueue[self.front]=None
        if self.front!=self.rear:
            if self.front==(len(self.circularqueue)-1):
                self.front=0
            else:
                self.front+=1
        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        else:
            return self.circularqueue[self.front]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        else:
            return self.circularqueue[self.rear]

    def isEmpty(self) -> bool:
        return (self.circularqueue[self.front]==None)
        
    def isFull(self) -> bool:
        if self.rear==(len(self.circularqueue)-1):
            return self.front==0 and self.circularqueue[self.front]!=None
        else:
            return self.rear==(self.front-1)