Design Circular Deque

Design a double-ended queue (deque) that supports insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, and isFull.

Example 1

MyCircularDeque(3), insertLast(1)→true, insertLast(2)→true, insertFront(3)→true, insertFront(4)→false, getRear()→2, isFull()→true, deleteLast()→true, insertFront(4)→true, getFront()→4

Solution Approach

Similar to circular queue but with front insertion (head = (head-1+cap)%cap).

Array, head=0, tail=0, size=0.
insertFront: head = (head-1+cap)%cap; arr[head]=val; size++.
insertLast: arr[tail]=val; tail=(tail+1)%cap; size++.
deleteFront: head=(head+1)%cap; size--.
deleteLast: tail=(tail-1+cap)%cap; size--.

Java

class MyCircularDeque {
    int[] q; int head, tail, size, cap;
    public MyCircularDeque(int k) { q=new int[k]; cap=k; }
    public boolean insertFront(int val) {
        if (isFull()) return false;
        head=(head-1+cap)%cap; q[head]=val; size++; return true;
    }
    public boolean insertLast(int val) {
        if (isFull()) return false;
        q[tail]=val; tail=(tail+1)%cap; size++; return true;
    }
    public boolean deleteFront() {
        if (isEmpty()) return false;
        head=(head+1)%cap; size--; return true;
    }
    public boolean deleteLast() {
        if (isEmpty()) return false;
        tail=(tail-1+cap)%cap; size--; return true;
    }
    public int getFront() { return isEmpty()?-1:q[head]; }
    public int getRear() { return isEmpty()?-1:q[(tail-1+cap)%cap]; }
    public boolean isEmpty() { return size==0; }
    public boolean isFull() { return size==cap; }
}

Time Complexity: All operations O(1)
Space Complexity: O(K)