[leetcode-641] Design Circular Deque

LeetCode-641

Design Circular Deque : Design your implementation of the circular double-ended queue (deque).

note : Returns -1 if the deque is empty.

MyAnswer

        :::python

class MyCircularDeque:
    def init(self, k: int):
        self.maxsize = k
        self.deq = collections.deque(maxlen=k)
        self.deq_size = 0
    def insertFront(self, value: int) -> bool:
        if self.deq_size < self.maxsize:
            self.deq.insert(0,value)
            self.deq_size += 1
            return True
        else:
            return False
    def insertLast(self, value: int) -> bool:
        if self.deq_size < self.maxsize:
            self.deq.append(value)
            self.deq_size += 1
            return True
        else:
            return False
    def deleteFront(self) -> bool:
        if self.deq_size > 0:
            self.deq.popleft()
            self.deq_size -= 1
            return True
        else:
            return False
    def deleteLast(self) -> bool:
        if self.deq_size > 0:
            self.deq.pop()
            self.deq_size -= 1
            return True
        else:
            return False
    def getFront(self) -> int:
        if self.deq_size > 0:
            return self.deq[0]
        else:
            return -1
    def getRear(self) -> int:
        if self.deq_size > 0:
            return self.deq[-1]
        else:
            return -1
    def isEmpty(self) -> bool:
        if self.deq_size==0:
            return True
        else:
            return False
    def isFull(self) -> bool:
        if self.deq_size==self.maxsize:
            return True
        else:
            return False
# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()

Result : 61ms Memory: 14.7mb

## Design Circular Deque

Design Circular Deque는 원형 덱 자료구조를 디자인하는 문제입니다. 이를 구현하기 위해서는 원형 큐를 구현하는 방법이 필요합니다.

CircularDeque 클래스는 다음과 같은 기능을 제공해야 합니다.

• CircularDeque(k) : 길이가 k인 원형 덱을 생성합니다.
• insertFront() : 덱의 맨 앞에 요소를 추가합니다. 성공하면 True를 반환합니다.
• insertLast() : 덱의 맨 뒤에 요소를 추가합니다. 성공하면 True를 반환합니다.
• deleteFront() : 덱 맨 앞의 요소를 삭제합니다. 성공하면 True를 반환합니다.
• deleteLast() : 덱 맨 뒤의 요소를 삭제합니다. 성공하면 True를 반환합니다.
• getFront() : 덱 맨 앞의 요소를 반환합니다. 비어있다면 -1을 반환합니다.
• getRear() : 덱 맨 뒤의 요소를 반환합니다. 비어있다면 -1을 반환합니다.
• isEmpty() : 덱이 비어있는지 확인합니다. 비어있다면 True를 반환합니다.
• isFull() : 덱이 가득 차 있는지 확인합니다. 가득 차있다면 True를 반환합니다.

이러한 기능을 위해서는 CircularDeque 클래스 내부에 다음과 같은 변수들이 필요합니다.

• self.queue: 저장소
• self.front: 현재 맨 앞의 인덱스
• self.rear: 현재 맨 뒤의 인덱스
• self.length: 저장소의 길이

또한 insertFront()와 insertLast(), deleteFront()와 deleteLast() 메서드는 서로 대칭적인 기능을 수행합니다. 따라서 insert()와 delete()라는 하나의 함수로 묶어서 구현할 수 있습니다.