641. Design Circular Deque

Description

The MyCircularDeque class implements a double-ended queue (deque) with a fixed size. It allows elements to be inserted or removed from both ends of the queue. The deque has the following operations:

• Insert an element at the front.
• Insert an element at the rear.
• Delete an element from the front.
• Delete an element from the rear.
• Retrieve the element at the front.
• Retrieve the element at the rear.
• Check if the deque is empty.
• Check if the deque is full.

Intuition

A deque is a useful data structure when there is a need for efficient insertions and deletions from both ends. By keeping the structure as a fixed-size circular array, operations such as insertions and deletions can be performed in constant time. The MyCircularDeque class mimics this behavior by using a dynamic list and maintaining the maximum size.

Approach

1. Initialization: The deque is initialized with a given capacity k. Internally, a list is used to store the elements, and the size n keeps track of the maximum allowed elements.
2. Insert Operations: The insertFront and insertLast methods check if the deque has space for more elements, and if so, insert elements at the respective ends (front or rear) using list operations.
3. Delete Operations: The deleteFront and deleteLast methods remove elements from the respective ends if the deque is not empty.
4. Access Operations: The getFront and getRear methods retrieve the elements at the respective ends without removing them.
5. Check Methods: The isEmpty method checks if the deque is empty, and the isFull method checks if the deque is full.

Complexity

• Time Complexity: - insertFront, insertLast, deleteFront, deleteLast: O(1) (since list insertions and deletions at the front and end are constant time). - getFront, getRear, isEmpty, isFull: O(1).
• Space Complexity: O(k), where k is the maximum size of the deque. The deque requires space proportional to the number of elements it can hold.

Code

C++

class MyCircularDeque {
public:
    vector dq;
    int n;

    MyCircularDeque(int k) {
        n = k;
    }

    bool insertFront(int value) {
        if (dq.size() < n) {
            dq.insert(dq.begin(), value);
            return true;
        }
        return false;
    }

    bool insertLast(int value) {
        if (dq.size() < n) {
            dq.push_back(value);
            return true;
        }
        return false;
    }

    bool deleteFront() {
        if (!dq.empty()) {
            dq.erase(dq.begin());
            return true;
        }
        return false;
    }

    bool deleteLast() {
        if (!dq.empty()) {
            dq.pop_back();
            return true;
        }
        return false;
    }

    int getFront() {
        return dq.empty() ? -1 : dq.front();
    }

    int getRear() {
        return dq.empty() ? -1 : dq.back();
    }

    bool isEmpty() {
        return dq.empty();
    }

    bool isFull() {
        return dq.size() == n;
    }
};

Python

class MyCircularDeque:

    def __init__(self, k: int):
        self.dq = []
        self.n = k

    def insertFront(self, value: int) -> bool:
        if len(self.dq) < self.n:
            self.dq.insert(0, value)
            return True
        return False

    def insertLast(self, value: int) -> bool:
        if len(self.dq) < self.n:
            self.dq.append(value)
            return True
        return False

    def deleteFront(self) -> bool:
        if len(self.dq) > 0:
            self.dq.pop(0)
            return True
        return False

    def deleteLast(self) -> bool:
        if len(self.dq) > 0:
            self.dq.pop()
            return True
        return False

    def getFront(self) -> int:
        return self.dq[0] if len(self.dq) > 0 else -1

    def getRear(self) -> int:
        return self.dq[-1] if len(self.dq) > 0 else -1

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

    def isFull(self) -> bool:
        return len(self.dq) == self.n

Java

class MyCircularDeque {
    private LinkedList dq;
    private int n;

    public MyCircularDeque(int k) {
        dq = new LinkedList<>();
        n = k;
    }

    public boolean insertFront(int value) {
        if (dq.size() < n) {
            dq.addFirst(value);
            return true;
        }
        return false;
    }

    public boolean insertLast(int value) {
        if (dq.size() < n) {
            dq.addLast(value);
            return true;
        }
        return false;
    }

    public boolean deleteFront() {
        if (!dq.isEmpty()) {
            dq.removeFirst();
            return true;
        }
        return false;
    }

    public boolean deleteLast() {
        if (!dq.isEmpty()) {
            dq.removeLast();
            return true;
        }
        return false;
    }

    public int getFront() {
        return dq.isEmpty() ? -1 : dq.getFirst();
    }

    public int getRear() {
        return dq.isEmpty() ? -1 : dq.getLast();
    }

    public boolean isEmpty() {
        return dq.isEmpty();
    }

    public boolean isFull() {
        return dq.size() == n;
    }
}

JavaScript

class MyCircularDeque {
    constructor(k) {
        this.dq = [];
        this.n = k;
    }

    insertFront(value) {
        if (this.dq.length < this.n) {
            this.dq.unshift(value);
            return true;
        }
        return false;
    }

    insertLast(value) {
        if (this.dq.length < this.n) {
            this.dq.push(value);
            return true;
        }
        return false;
    }

    deleteFront() {
        if (this.dq.length > 0) {
            this.dq.shift();
            return true;
        }
        return false;
    }

    deleteLast() {
        if (this.dq.length > 0) {
            this.dq.pop();
            return true;
        }
        return false;
    }

    getFront() {
        return this.dq.length > 0 ? this.dq[0] : -1;
    }

    getRear() {
        return this.dq.length > 0 ? this.dq[this.dq.length - 1] : -1;
    }

    isEmpty() {
        return this.dq.length === 0;
    }

    isFull() {
        return this.dq.length === this.n;
    }
}

/** 
 * Your MyCircularDeque object will be instantiated and called as such:
 * var obj = new MyCircularDeque(k)
 * var param_1 = obj.insertFront(value)
 * var param_2 = obj.insertLast(value)
 * var param_3 = obj.deleteFront()
 * var param_4 = obj.deleteLast()
 * var param_5 = obj.getFront()
 * var param_6 = obj.getRear()
 * var param_7 = obj.isEmpty()
 * var param_8 = obj.isFull()
 */