[파이썬 알고리즘 인터뷰] 26. 원형 데크 디자인

 

 이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.

 

 출처 : 파이썬 알고리즘 인터뷰

 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브

 

---

26. 원형 데크 디자인

leetcode 641. Design Circular Deque 문제입니다.

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

 

 

풀이

 이중 연결 리스트를 이용한 풀이입니다.

 

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

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

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

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

    def deleteLast(self):
        if self.len == 0:
            return False
        self.len -= 1
        self._del(self.tail.left.left)
        return True

    def getFront(self):
        return self.head.right.val if self.len else -1

    def getRear(self):
        return self.tail.left.val if self.len else -1

    def isEmpty(self):
        return self.len == 0

    def isFull(self):
        return self.len == self.k