Design Circular Deque
Medium · Stack & Strings · Array · Linked List · Design · Queue
Problem
Implement a fixed-capacity double-ended queue stored in a ring buffer: elements can be added and removed at both ends, and the slots wrap around so that space freed at one end can be reused at the other. Do not use a built-in deque type.
Implement MyCircularDeque:
- MyCircularDeque(k) creates a deque that holds at most k elements.
- insertFront(value) / insertLast(value) add value at the front / back; return True on success, False if the deque is full.
- deleteFront() / deleteLast() remove the front / back element; return True on success, False if the deque is empty.
- getFront() / getRear() return the front / back element, or -1 if the deque is empty.
- isEmpty() and isFull() report the deque's state.
Tests replay a call sequence: the first entry names the class and its constructor arguments, each later entry is a method with its arguments.
Examples
Input: ops = ["MyCircularDeque","insertLast","insertFront","insertFront","getFront","getRear","deleteLast","getRear"], args = [[2],[3],[9],[4],[],[],[],[]] Output: [None, True, True, False, 9, 3, True, 9]
The deque holds 9, 3 and rejects a third element. After 3 is deleted from the back, 9 is at both ends.
Input: ops = ["MyCircularDeque","deleteFront","insertFront","isFull"], args = [[1],[],[5],[]] Output: [None, False, True, True]
Deleting from an empty deque fails; one insert fills a deque of capacity 1.
Constraints
- 1 <= k <= 1000
- 0 <= value <= 1000
- At most 2000 calls are made in total
Approaches
- Baseline: a list that shifts at the front — time O(k) for front calls, O(1) otherwise, space O(k)
Follow-up
What if a full buffer should make room instead of refusing, dropping its oldest element, as a log of the last k events does? See the use case "A ring buffer that overwrites its oldest value". And if elements may also be added and removed in the middle, two deques kept balanced do it in O(1) per call: see "A queue open at the front, middle and back".
Related problems
Start free on Cariara · Coding problems · System design studio
