❗️[LEET CODE] 641. Design Circular Deque

# Problem

Design your implementation of the circular double-ended queue (deque). Your implementation should support following operations: MyCircularDeque(k): Constructor, set the size of the deque to be k. insertFront(): Adds an item at the front of Deque. Return true if the operation is successful. insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful. deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful. deleteLast(): Deletes an item from the rear of Deque. Return true if the operation is successful. getFront(): Gets the front item from the Deque. If the deque is empty, return -1. getRear(): Gets the last item from Deque. If the deque is empty, return -1. isEmpty(): Checks whether Deque is empty or not.  isFull(): Checks whether Deque is full or not. Note: All values will be in the range of [0, 1000]. The number of operations will be in the range of [1, 1000]. Please do not use the built-in Deque library.

 

# My Answer

class MyCircularDeque:

    def __init__(self, k: int):
        """
        Initialize your data structure here. Set the size of the deque to be k.
        """
        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):
        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.len ==self.k:
            return False
        self.len+=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.len ==self.k:
            return False
        self.len+=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.len==0:
            return False
        self.len-=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.len==0:
            return False
        self.len-=1
        self._del(self.tail.left.left)
        return True

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

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

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

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

 

# Solution 1 - 이중 연결 리스트를 이용한 데크 구현

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


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.len == self.k:
            return False
        self.len += 1
        self._add(self.head, ListNode(value))
        return True

    def insertLast(self, value: int) -> bool:
        if self.len == self.k:
            return False
        self.len += 1
        self._add(self.tail.left, ListNode(value))
        return True

    def deleteFront(self) -> bool:
        if self.len == 0:
            return False
        self.len -= 1
        self._del(self.head)
        return True

    def deleteLast(self) -> bool:
        if self.len == 0:
            return False
        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

head와 tail에는 값이 들어가지 않고 포인터 역할

새로운 값이 들어오면 head/tail에 연결해주면 된다

 

---

# 우선순위 큐

어떤 특정 조건에 따라 우선순위가 가장 높은 요소가 추출되는 자료형

ex) 최댓값이 우선순위에 따라 추출

 

정렬 알고리즘을 사용하여 우선순위 큐 만들기

n개의 요소를 정렬하는 데 S(n)의 시간

새 요소 삽입, 삭제 O(S(n))

정렬했을 때 최댓값을 가져오는데 O(1)

대개 정렬은 O(nlogn)의 시간이 걸리기 때문에 O(S(n)) = O(nlogn)

보통 단순 정렬보다 힙 정렬 등의 좀 더 효율적인 방법 사용

 

최단 경로를 탐색하는 다익스트라 알고리즘 등에 사용

 

파이썬 queue 모듈의 PriorityQueue 클래스 사용 - 내부적으로 heapq사용 (거의 동일)

priorityqueue클래스는 멀티 스레드에도 안전한 스레드 세이프 클래스

멀티 스레드 구현 아니면 heapq 사용

 

# 파이썬은 왜 느린가

GIL(Global Interpreter Lock) -하나의 스레드가 자원을 독점하는 형태

초기에 GIL로 파이썬 객체에 대한 접근을 제한하는 형태로 설계

지금은 극복하기 위한 다양한 시도 중