LeetCode 641. Design Circular Deque

파이썬 알고리즘 인터뷰 문제 26번(리트코드 641번) Design Circular Deque
https://leetcode.com/problems/design-circular-deque/

나의 풀이(Stack)

class MyCircularDeque:

    def __init__(self, k: int):
        self.dq = [None] * k
        self.size = k
        self.p1 = k - 1
        self.p2 = 0

    def insertFront(self, value: int) -> bool:
        if self.dq[self.p1] is None:
            self.dq[self.p1] = value
            self.p1 = (self.p1 - 1) % self.size
            return True
        return False

    def insertLast(self, value: int) -> bool:
        if self.dq[self.p2] is None:
            self.dq[self.p2] = value
            self.p2 = (self.p2 + 1) % self.size
            return True
        return False

    def deleteFront(self) -> bool:
        if self.dq[(self.p1 + 1) % self.size] is not None:
            self.p1 = (self.p1 + 1) % self.size
            self.dq[self.p1] = None
            return True
        return False

    def deleteLast(self) -> bool:
        if self.dq[(self.p2 - 1) % self.size] is not None:
            self.p2 = (self.p2 - 1) % self.size
            self.dq[self.p2] = None
            return True
        return False

    def getFront(self) -> int:
        if self.dq[(self.p1 + 1) % self.size] is not None:
            return self.dq[(self.p1 + 1) % self.size]
        return -1

    def getRear(self) -> int:
        if self.dq[(self.p2 - 1) % self.size] is not None:
            return self.dq[(self.p2 - 1) % self.size]
        return -1

    def isEmpty(self) -> bool:
        return (self.p1 - self.p2 + 1) % self.size == 0 and self.dq[(self.p1 + 1) % self.size] is None

    def isFull(self) -> bool:
        return (self.p1 - self.p2 + 1) % self.size == 0 and self.dq[(self.p1 + 1) % self.size] is not None
        

# 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()

다른 풀이(Double Linked List)

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 = ListNode(None)
        self.tail = ListNode(None)
        self.k = k
        self.len = 0
        self.head.right = self.tail
        self.tail.left = self.head
    
    def _add(self, node: ListNode, new: ListNode):
        nxt = node.right
        node.right = new
        new.left = node
        new.right = nxt
        nxt.left = new
    
    def _del(self, node: ListNode):
        nxt = node.right.right
        node.right = nxt
        nxt.left = node

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

    def insertLast(self, value: int) -> bool:
        if self.k == self.len:
            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:
        if self.len == 0:
            return -1
        return self.head.right.val

    def getRear(self) -> int:
        if self.len == 0:
            return -1
        return self.tail.left.val

    def isEmpty(self) -> bool:
        return self.len == 0

    def isFull(self) -> bool:
        return self.len == self.k
        

# 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()