641. Design Circular Deque

deQueue 구현 문제

 

deQueue는 이중 연결리스트로 많이 구현한다. (left, right)

앞, 뒤로 추가 가능하다. 

head와 tail은 제일 앞에 ListNode와 맨 뒤의 ListNode를 가르키고 있다. 

 

만약 제일 앞에 새로운 값을 추가하려면, 

head를 새로운 ListNode를 가르키게 하고, 이전 값을 연결해주면 된다. 

 

head, tail에서 add를 공통으로 하기 위해서 오른쪽에 추가하는걸 기준으로 _add함수를 만들었다.

del 역시 공통으로 사용하기 위해서 오른쪽 자식을 삭제하는걸 기준으로 잡았다. 

 

add, del시에 tail에서는 어느 부분을 가르켜야되는지 손으로 그려보면 잘 알 수 있다. 

class MyCircularDeque:
    def __init__(self, k: int):
        self.k, self.cur = k, 0
        self.head, self.tail = ListNode(None), ListNode(None)
        #처음에는 아무것도 없으니 head와 tail을 서로 연결 시켜줌
        self.head.right, self.tail.left = self.tail, self.head
        
    def _add(self, node:ListNode, new:ListNode):
        before = node.right
        node.right = new
        new.left, new.right = node, before
        before.left = new

    def _del(self, node:ListNode):
        # head, tail은 마지막 ListNode를 알려주기만할뿐...
        # 지울때는 head,tail을 현재것의 한칸 더 옆으로 옮기면 된다.
        # a - b - c - tail일때 b-tail을 직접 연결하는 것
        
        n = node.right.right
        node.right = n
        n.left = node
    def insertFront(self, value: int) -> bool:
        """
        Adds an item at the front of Deque. Return true if the operation is successful.
        """
        if self.cur == self.k:
            return False

        self.cur += 1
        self._add(self.head, ListNode(value))
        return True

    def insertLast(self, value: int) -> bool:
        """
        Adds an item at the rear of Deque. Return true if the operation is successful.
        """
        if self.cur == self.k:
            return False

        self.cur += 1
        #항상 오른쪽을 기준으로 추가하는 것
        self._add(self.tail.left, ListNode(value))
        return True



    def deleteFront(self) -> bool:
        """
        Deletes an item from the front of Deque. Return true if the operation is successful.
        """
        if self.cur == 0:
            return False

        self.cur -= 1
        self._del(self.head)
        return True
    def deleteLast(self) -> bool:
        """
        Deletes an item from the rear of Deque. Return true if the operation is successful.
        """
        if self.cur == 0:
            return False
        self.cur -= 1
        self._del(self.tail.left.left)
        return True

    def getFront(self) -> int:
        """
        Get the front item from the deque.
        """
        return self.head.right.val if self.cur else -1

    def getRear(self) -> int:
        """
        Get the last item from the deque.
        """
        return self.tail.left.val if self.cur else -1

    def isEmpty(self) -> bool:
        """
        Checks whether the circular deque is empty or not.
        """
        return self.cur == 0

    def isFull(self) -> bool:
        """
        Checks whether the circular deque is full or not.
        """
        return self.cur == self.k