Design a double-ended queue (deque) that supports insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, and isFull.
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
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--.
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)