# 641. Design Circular Deque

## Problem:

Design a circular deque that provides the following operations.

* `MyCircularDeque(int k)` Initializes the deque with a maximum size of `k`.
* `boolean insertFront()` Adds an item at the front of Deque. Returns `true` if the operation is successful, or `false` otherwise.
* `boolean insertLast()` Adds an item at the rear of Deque. Returns `true` if the operation is successful, or `false` otherwise.
* `boolean deleteFront()` Deletes an item from the front of Deque. Returns `true` if the operation is successful, or `false` otherwise.
* `boolean deleteLast()` Deletes an item from the rear of Deque. Returns `true` if the operation is successful, or `false` otherwise.
* `int getFront()` Returns the front item from the Deque. Returns `-1` if the deque is empty.
* `int getRear()` Returns the last item from Deque. Returns `-1` if the deque is empty.
* `boolean isEmpty()` Returns `true` if the deque is empty, or `false` otherwise.
* `boolean isFull()` Returns `true` if the deque is full, or `false` otherwise.

<https://leetcode.com/problems/design-circular-deque/>

## Solution:

### Array

> Solving this problem with an array leverages the benefits of a circular structure.

* `front_ptr` points to the first element in the deque.
* `rear_ptr` points to the position where the next element will be inserted at the end.

```python
class MyCircularDeque:

    def __init__(self, k: int):
        self.dq = [None] * k
        self.maxlen = k
        self.front_ptr = 0
        self.rear_ptr = 0
        self.size = 0

    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False
        self.front_ptr = (self.front_ptr - 1) % self.maxlen
        self.dq[self.front_ptr] = value
        self.size += 1
        return True

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

    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False
        self.dq[self.front_ptr] = None
        self.front_ptr = (self.front_ptr + 1) % self.maxlen
        self.size -= 1
        return True

    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        self.rear_ptr = (self.rear_ptr - 1) % self.maxlen
        self.dq[self.rear_ptr] = None
        self.size -= 1
        return True

    def getFront(self) -> int:
        return -1 if self.dq[self.front_ptr] is None else self.dq[self.front_ptr]

    def getRear(self) -> int:
        return -1 if self.dq[(self.rear_ptr - 1) % self.maxlen] is None else self.dq[(self.rear_ptr - 1) % self.maxlen]

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

    def isFull(self) -> bool:
        return self.size == self.maxlen


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

### Doubly Linked List

> They are simply implemented through a doubly linked list for the sake of the solution. However, in reality, Python's deque implementation is based on a doubly linked list.

1. The reason for implementing in a **circular** fashion is with the intent to connect the tail and head to utilize the empty space at the front when the space gets filled from the back. However, since linked lists inherently don't have the concept of "empty space", the circular structure is meaningless.
2. The operations of a deque only extract values from the very beginning and the very end. There's no operation to extract the value following the very end, so there's also no need for them to be interconnected.

Note: Based on the PEP 8 naming convention, the method name was set to \_*add()* and *\_del() with a single underscore (\_*) at the beginning to signify that it is used internally.

<pre class="language-python"><code class="lang-python">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
    
    # Insert a new node in doubly linked list
    def _add(self, node: ListNode, new: ListNode):
        n = node.right
        node.right = new
        new.right, new.left = n, node
        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.eln += 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 <a data-footnote-ref href="#user-content-fn-1">self.head.right.val if self.len else -1</a>

    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
</code></pre>

[^1]: If the length (or size) of the data structure is **non-zero**, return the value of the right child of the head node; otherwise, return `-1`.
