641. Design Circular Deque

Medium

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.

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.

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 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