[Leetcode] 641. Design Circular Deque

Leetcode 641. Design Circular Deque

https://leetcode.com/problems/design-circular-deque/

Design Circular Deque - LeetCode

Solution

class MyCircularDeque:
 
    def __init__(self, k: int):
        self.q = [None] * (k+1)
        self.max = k+1
        self.front = 0
        self.rear = 0
 
    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False
        else:
            self.q[self.front] = value
            self.front = (self.front - 1 + self.max) % self.max
            return True
 
    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False
        else:
            self.rear = (self.rear + 1) % self.max
            self.q[self.rear] = value
            return True
 
    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False
        else:
            self.q[(self.front + 1) % self.max] = None
            self.front = (self.front + 1) % self.max
            return True
 
    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        else:
            self.q[self.rear] = None
            self.rear = (self.rear - 1 + self.max) % self.max
            return True
 
    def getFront(self) -> int:
        if self.isEmpty():
            return -1
        else:
            return self.q[(self.front + 1) % self.max]
 
    def getRear(self) -> int:
        if self.isEmpty():
            return -1
        else:
            return self.q[self.rear]
 
    def isEmpty(self) -> bool:
        return self.front == self.rear
 
    def isFull(self) -> bool:
        return self.front == (self.rear + 1) % self.max
 
 
# 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()

원형 큐에서 몇가지 코드만 추가하면 된다.

큐는 선입 후출이지만, 덱은 front와 rear모두에서 삽입과 삭제가 가능하다.

주의할 점은, index를 감소시키는 insertFront() 와 deleteLast()에서

self.front = (self.front - 1 + self.max) % self.max

이렇게 + self.max를 해줘야 한다는 것이다. self.front의 인덱스가 0이면 front가 음수가 되기 때문이다.