[leetcode] 641. Design Circular Deque

Design your implementation of the circular double-ended queue (deque).

Implement the MyC

 

ircularDeque class:

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

 

Example 1:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

Explanation
MyCircularDeque myCircularDeque = new MyCircularDeque(3);
myCircularDeque.insertLast(1);  // return True
myCircularDeque.insertLast(2);  // return True
myCircularDeque.insertFront(3); // return True
myCircularDeque.insertFront(4); // return False, the queue is full.
myCircularDeque.getRear();      // return 2
myCircularDeque.isFull();       // return True
myCircularDeque.deleteLast();   // return True
myCircularDeque.insertFront(4); // return True
myCircularDeque.getFront();     // return 4

 

Constraints:

• 1 <= k <= 1000
• 0 <= value <= 1000
• At most 2000 calls will be made to insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull.

 

class MyCircularDeque(object):
    def __init__(self, k):
        """
        :type 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 

    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):
        """
        :type value: int
        :rtype: bool
        """
        if self.len == self.k:
            return False 
        self.len += 1 
        self._add(self.head, ListNode(value))
        return True 
        

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

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

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

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

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

    def isEmpty(self):
        """
        :rtype: bool
        """
        return self.len == 0
        

    def isFull(self):
        """
        :rtype: 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()