Python Algorithm Q26

Q26 Design Circular Deque

---

Q

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

Implement the MyCircularDeque 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.

Sample Input

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.

1. My Solution =~ Given Solution

class Node():
    def __init__(self, val = None, prev = None, next = None): #값, 전 주소, 다음 주소
        self.val = val
        self.prev = prev
        self.next = next

class MyCircularDeque:

    def __init__(self, k: int):
        self.head, self.tail = Node(), Node()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.maxlen = k
        self.cnt = 0

    def _add(self, node: Node(), new_node: Node()):
        a = node.next
        node.next = new_node
        new_node.prev, new_node.next = node, a
        a.prev = new_node

    def _del(self, node: Node()):
        prev, next = node.prev, node.next
        node.next.prev = prev
        node.prev.next = next

    def insertFront(self, value: int) -> bool:
        if self.cnt == self.maxlen:
            return False
        else:
            self.cnt += 1
            self._add(self.head,Node(value))
            return True

    def insertLast(self, value: int) -> bool:
        if self.cnt == self.maxlen:
            return False
        else:
            self.cnt += 1
            self._add(self.tail.prev, Node(value))
            return True

    def deleteFront(self) -> bool:
        if self.cnt == 0:
            return False
        else:
            self.cnt -= 1
            self._del(self.head.next)
            return True

    def deleteLast(self) -> bool:
        if self.cnt == 0:
            return False
        else:
            self.cnt -= 1
            self._del(self.tail.prev)
            return True

    def getFront(self) -> int:
        if self.isEmpty():
            return -1
        else:
            return self.head.next.val

    def getRear(self) -> int:
        if self.isEmpty():
            return -1
        else:
            return self.tail.prev.val

    def isEmpty(self) -> bool:
        if self.cnt == 0:
            return True
        else:
            return False        

    def isFull(self) -> bool:
        if self.cnt == self.maxlen:
            return True
        else:
            return False

In this problem, the term “circular” is not that important. Just performing the functions provided is our goal. Let’s focus on the variables of init function.

• self.head, self.tail = Node(), Node() : create main head and tail node.
• self.head.next, self.tail.prev = self.tail, self.head : connecting head and tail.
• self.maxlen = k : saving max length.
• self.cnt = 0 : for counting.

The concept of this type is “INSERT” between head and tail. At ANY CASE, head and tail do not change. They are just sign for the start and the end. Therefore, adding nodes to the deque is done by INSERTION. That’s why I define _add and _del function just like insertion. Understanding this concept, the problem is not hard at all. You can easily follow my codes without any description.

*tips : adding underscore(“_”) to the function name is the promise that those functions will used only inside the class(object).

Overall Review

At first, this question looks so intricated. Implementing deque with double-linked list… Looks not that easy. Even I considered making all nodes at initialization then pushing values afterward… However devising to use fixed HEAD and TAIL is really brilliant. Just let them exist both sides, the question easily solved!!