[LeetCode,Python] 641. 원형 데크 디자인(Design Circular Deque)

다음 연산을 제공하는 원형 데크를 디자인하라.

 

• MyCircularDeque(k): 생성자, 데크의 크기를 k로 설정합니다.
• insertFront(): 데크 앞에 항목을 추가합니다. 작업이 성공하면 true를 반환합니다.
• insertLast() : Deque 후방에 항목을 추가합니다. 작업이 성공하면 true를 반환합니다.
• deleteFront() : Deque 전면에서 항목을 삭제합니다. 작업이 성공하면 true를 반환합니다.
• deleteLast() : Deque 후면에서 항목을 삭제합니다. 작업이 성공하면 true를 반환합니다.
• getFront(): Deque에서 프런트 아이템을 가져옵니다. 데크가 비어 있으면 -1을 반환합니다.
• getRear(): Deque에서 마지막 항목을 가져옵니다. 데크가 비어 있으면 -1을 반환합니다.
• isEmpty(): Deque가 비어 있는지 여부를 확인합니다.
• isFull(): Deque가 가득 찼는지 여부를 확인합니다.

 

** 깔끔한 답안 **

 

 

class ListNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
class MyCircularDeque:
    def __init__(self, k: int):
        self.head, self.tail = ListNode(None), ListNode(None)
        self.k, self.len = k, 0
        self.head.right, self.tail.left = self.tail, self.head
 
    # 이중 연결 리스트에 신규 노드 삽입
    def _add(self, node: ListNode, new: ListNode):
        n = node.right
        node.right = new
        new.left, new.right = node, n
        n.left = new
 
    def _del(self, node: ListNode):
        n = node.right.right
        node.right = n
        n.left = node
 
    def insertFront(self, value: int) -> bool:
        if self.k == self.len:
            return False
        else:
            self.len += 1
            self._add(self.head, ListNode(value))
            return True
 
    def insertLast(self, value: int) -> bool:
        if self.k == self.len:
            return False
        else:
            self.len += 1
            self._add(self.tail.left, ListNode(value))
            return True
 
    def deleteFront(self) -> bool:
        if self.len == 0:
            return False
        else:
            self.len -= 1
            self._del(self.head)
            return True
 
    def deleteLast(self) -> bool:
        if self.len == 0:
            return False
        else:
            self.len -= 1
            self._del(self.tail.left.left)
            return True
 
    def getFront(self) -> int:
        return self.head.right.val if self.len else -1
 
    def getRear(self) -> int:
        return self.tail.left.val if self.len else -1
 
    def isEmpty(self) -> bool:
        return self.len == 0
 
    def isFull(self) -> bool:
        return self.len == self.k

 

해설:

 

이중 연결 리스트 클래스를 생성하고

이를 이용하여 데크를 구현하였다.

 

 

 

이 그림에서 next는 left, prev는 right로 이해하고 코드와 맞춰보면 된다.