DSA problem
Design Circular Deque
Design a double-ended queue (deque) with a fixed capacity, backed by a circular array. A circular deque generalizes the circular queue by allowing inserts and removes at both ends in O(1). It is the natural data structure when you need bounded buffering with bidirectional access, such as sliding-window monotonic queues or producer/consumer rings with steal-from-tail semantics.
Implement MyCircularDeque with these operations: MyCircularDeque(k) constructs an empty deque with capacity k. insertFront(value) and insertLast(value) add to the respective end and return whether the insert succeeded. deleteFront() and deleteLast() remove from the respective end and return whether the delete succeeded. getFront() and getRear() return the element at the respective end or -1 if the deque is empty. isEmpty() and isFull() test the current state.
The implementation mirrors the circular queue but applies modular arithmetic to both ends. We keep an array of length k, indices head and tail where head is the index of the front and tail is one past the rear, plus an explicit size counter. insertFront moves head backward (wrapping) and writes there; insertLast writes at tail then moves tail forward. deleteFront advances head; deleteLast retreats tail. Because subtraction can produce a negative index, every backward step uses (idx - 1 + capacity) % capacity to stay non-negative.
All eight operations are O(1) in both time and space, making this the canonical bounded deque implementation used in everything from sliding-window algorithms to OS schedulers' work-stealing queues.
Examples
["MyCircularDeque","insertLast","insertLast","insertFront","insertFront","getRear","isFull","deleteLast","insertFront","getFront"]
[[3],[1],[2],[3],[4],[],[],[],[4],[]][null,true,true,true,false,2,true,true,true,4]["MyCircularDeque","insertFront","deleteFront","isEmpty"]
[[2],[5],[],[]][null,true,true,true]["MyCircularDeque","getFront","getRear","isEmpty"]
[[4],[],[],[]][null,-1,-1,true]Constraints
- 1 <= k <= 1000
- 0 <= value <= 1000
- At most 2000 calls will be made to insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, and isFull.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.