Problem

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.

Examples

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

Solution

Video explanation

Here is the video explaining the methods in detail. Please check it out:

Method 1 - Using Array

Code

Java
public class MyCircularDeque {
    private int[] deque;
    private int front, rear, size;

    public MyCircularDeque(int k) {
        deque = new int[k];
        front = k - 1;
        rear = 0;
        size = 0;
    }

    public boolean insertFront(int value) {
        if (isFull()) {
            return false;
        }
        deque[front] = value;
        front = (front - 1 + deque.length) % deque.length;
        size++;
        return true;
    }

    public boolean insertLast(int value) {
        if (isFull()) {
            return false;
        }
        deque[rear] = value;
        rear = (rear + 1) % deque.length;
        size++;
        return true;
    }

    public boolean deleteFront() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % deque.length;
        size--;
        return true;
    }

    public boolean deleteLast() {
        if (isEmpty()) {
            return false;
        }
        rear = (rear - 1 + deque.length) % deque.length;
        size--;
        return true;
    }

    public int getFront() {
        if (isEmpty()) {
            return -1;
        }
        return deque[(front + 1) % deque.length];
    }

    public int getRear() {
        if (isEmpty()) {
            return -1;
        }
        return deque[(rear - 1 + deque.length) % deque.length];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == deque.length;
    }
}
Python
class MyCircularDeque:

    def __init__(self, k: int):
        self.deque = [0] * k
        self.front = k - 1
        self.rear = 0
        self.size = 0

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

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

    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % len(self.deque)
        self.size -= 1
        return True

    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        self.rear = (self.rear - 1 + len(self.deque)) % len(self.deque)
        self.size -= 1
        return True

    def getFront(self) -> int:
        if self.isEmpty():
            return -1
        return self.deque[(self.front + 1) % len(self.deque)]

    def getRear(self) -> int:
        if self.isEmpty():
            return -1
        return self.deque[(self.rear - 1 + len(self.deque)) % len(self.deque)]

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

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

Complexity

  • ⏰ Time complexity: O(1), - All operations (insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, and isFull) are O(1) because they involve a fixed amount of work regardless of the size of the deque.
  • 🧺 Space complexity: O(k), where k is the size of the deque. This space is used to store the elements in the circular array.

Method 2 - Using Double Linked List

Code

Java
class DoubleListNode {
    DoubleListNode pre;
    DoubleListNode next;
    int val;
    public DoubleListNode(int val) {
        this.val = val;
    }
}

class MyCircularDeque {
    int size;
    int k;
    DoubleListNode head;
    DoubleListNode tail;
    /** Initialize your data structure here. Set the size of the deque to be k. */
    public MyCircularDeque(int k) {
        head = new DoubleListNode(-1);
        tail = new DoubleListNode(-1);
        head.pre = tail;
        tail.next = head;
        this.k = k;
        this.size = 0;
    }
    
    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    public boolean insertFront(int value) {
        if (size == k)
            return false;
        DoubleListNode node = new DoubleListNode(value);
        node.next = head;
        node.pre = head.pre;
        head.pre.next = node;
        head.pre = node;
        size++;
        return true;
    }
    
    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    public boolean insertLast(int value) {
        if (size == k)
            return false;
        DoubleListNode node = new DoubleListNode(value);
        node.next = tail.next;
        tail.next.pre = node;
        tail.next = node;
        node.pre = tail;
        size++;
        return true;
    }
    
    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    public boolean deleteFront() {
        if (size == 0)
            return false;
        head.pre.pre.next = head;
        head.pre = head.pre.pre;
        size--;
        return true;
    }
    
    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    public boolean deleteLast() {
        if (size == 0)
            return false;
        tail.next.next.pre = tail;
        tail.next = tail.next.next;
        size--;
        return true;
    }
    
    /** Get the front item from the deque. */
    public int getFront() {
        return head.pre.val;
    }
    
    /** Get the last item from the deque. */
    public int getRear() {
        return tail.next.val;
    }
    
    /** Checks whether the circular deque is empty or not. */
    public boolean isEmpty() {
        return size == 0;
    }
    
    /** Checks whether the circular deque is full or not. */
    public boolean isFull() {
        return size == k;
    }
}
Python
class DoubleListNode:
    def __init__(self, val):
        self.pre = None
        self.next = None
        self.val = val


class MyCircularDeque:
    def __init__(self, k: int):
        self.head = DoubleListNode(-1)
        self.tail = DoubleListNode(-1)
        self.head.pre = self.tail
        self.tail.next = self.head
        self.k = k
        self.size = 0

    def insertFront(self, value: int) -> bool:
        if self.size == self.k:
            return False
        node = DoubleListNode(value)
        node.next = self.head
        node.pre = self.head.pre
        self.head.pre.next = node
        self.head.pre = node
        self.size += 1
        return True

    def insertLast(self, value: int) -> bool:
        if self.size == self.k:
            return False
        node = DoubleListNode(value)
        node.next = self.tail.next
        self.tail.next.pre = node
        self.tail.next = node
        node.pre = self.tail
        self.size += 1
        return True

    def deleteFront(self) -> bool:
        if self.size == 0:
            return False
        self.head.pre.pre.next = self.head
        self.head.pre = self.head.pre.pre
        self.size -= 1
        return True

    def deleteLast(self) -> bool:
        if self.size == 0:
            return False
        self.tail.next.next.pre = self.tail
        self.tail.next = self.tail.next.next
        self.size -= 1
        return True

    def getFront(self) -> int:
        if self.size == 0:
            return -1
        return self.head.pre.val

    def getRear(self) -> int:
        if self.size == 0:
            return -1
        return self.tail.next.val

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

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

Complexity

  • ⏰ Time complexity: O(1), - All operations (insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, and isFull) are O(1) because they involve a fixed amount of work regardless of the size of the deque.
  • 🧺 Space complexity: O(k), where k is the size of the deque. This space is used to store the elements in the circular array.