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.

Example

Solution

''' 로컬에서 구현할때 class ListNode 선언해야됨 
class ListNode:
    def __init__(self, item):
        self.val = item
        self.next = None
'''

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.k = 최대길이, self.len = 현재 길이
        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:
        """
        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.
        """
        return self.head.right.val if self.len else -1

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

    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


obj = MyCircularDeque(6)
obj.insertFront(1)
obj.insertFront(2)
obj.insertFront(3)
print(obj.getFront())	# 3
print(obj.getRear())	# 1


obj.insertLast(0)
obj.insertLast(4)
obj.insertLast(5)
print(obj.getFront())	# 3
print(obj.getRear())	# 5
print(obj.isEmpty())	# False
print(obj.isFull())	# True

obj.deleteFront()	
print(obj.getFront())	# 2

obj.deleteLast()
print(obj.getRear())	# 4

print(obj.isEmpty())	# False
print(obj.isFull())	# False

• _add & _del (내부 메소드 그림으로 설명)
  

• 원형으로 구현하는 이유는 꼬리쪽으로 요소를 채우다가 공간이 다차게되면 tail과 head를 연결하여 앞쪽의 빈 공간을 활용하기 위해서인데,
  이중 연결 리스트로 구현 하면 이 장점을 살릴 수가 없다 왜냐하면 연결리스트는 애초에 빈공간이 없어서입니다.

• 그래서 원형의 이점을 살리기 위해서는 배열로 풀이 해야된다.(풀이를 위해서 연결리스트로 구현)

• 그리고 데크의 연산은 맨 처음과 맨 마지막 값을 추출할 뿐이라 다음 값을 추출하는지 등의 연산은 존재 않아서, 서로 연결되어 있을 필요 또한 없습니다.

• tail과 head는 서로 이중 연결리스트로 연결되어 있으며, 단순히 풀이를 위해서 구현되어있을 뿐입니다.

---

파이썬 알고리즘 인터뷰를 참조하였습니다.