Design Circular Deque
A deque, said "deck", is a queue you can add to and remove from at both ends . Build one inside a fixed block of k slots that never grows. Keep a head slot number and a count, exactly like a circular queue. Adding at the back writes to (head + count) % k. Adding at the front moves head one step backwards , wrapping from slot 0 round to the last slot, and writes there. Removing from the back is the easiest of all: lower the count by one and the value falls outside the live stretch. Nothing has to be copied or shifted, ever. This function takes a list of operation names and a matching list of arguments, and returns the list of results. Adding to a full deque returns false, and reading from an empty one returns -1.
Constraints
- 1 ≤ k ≤ 1000
- 0 ≤ value ≤ 1000
- At most 2000 operations in total
- Every operation must run in constant time
Example
Input
k = 3, operations = ['insertLast', 'insertLast', 'insertFront', 'insertFront', 'getRear', 'deleteLast', 'insertFront', 'getFront'], values = [[1], [2], [3], [4], [], [], [4], []]Output
[true, true, true, false, 2, true, true, 4]Explanation The fourth insert fails because the deque is full. Removing from the back frees a slot, so inserting 4 at the front succeeds and getFront returns 4.
In plain terms
- Deque
- Short for double ended queue. You can add and remove at the front and at the back, so it covers both queue and stack behaviour.
- Wrapping backwards
- Stepping from slot 0 to the last slot instead of going negative. The formula (head - 1 + k) % k does this by adding k first.
- Live stretch
- The run of slots holding real values right now: count slots starting at head, wrapping round the end. Anything outside it is leftover data that no longer counts.
One row of cells is the fixed buffer of k = 3 slots; head moves both ways around it
slot 0—
slot 1—
slot 2—
Statusinit
Three empty slots. head is 0 and the count is 0.
What happens in this step
size = 3, head = 0, count = 0 buffer = [empty, empty, empty] Both ends of the deque are worked out from head and count. No value ever changes slot once it has been written.
Step 1 of 8
Steps to visualize
- The three cells are the whole storage. Values are never copied between slots.
- Adding at the back writes to (head + count) % 3.
- Adding at the front first steps head backwards with (head - 1 + 3) % 3, then writes there.
- Removing from the back only lowers the count, so the last slot simply drops out of the live stretch.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
slot 0—
slot 1—
slot 2—
Statusinit
Three empty slots. head is 0 and the count is 0.
What happens in this step
size = 3, head = 0, count = 0 buffer = [empty, empty, empty] Both ends of the deque are worked out from head and count. No value ever changes slot once it has been written.
Step 1 of 8
Solution
function circularDeque(k, operations, values) {
class CircularDeque {
constructor(size) {
this.buffer = new Array(size).fill(null);
this.size = size;
this.head = 0;
this.count = 0;
}
insertFront(value) {
if (this.count === this.size) {
return false;
}
this.head = (this.head - 1 + this.size) % this.size;
this.buffer[this.head] = value;
this.count++;
return true;
}
insertLast(value) {
if (this.count === this.size) {
return false;
}
this.buffer[(this.head + this.count) % this.size] = value;
this.count++;
return true;
}
deleteFront() {
if (this.count === 0) {
return false;
}
this.head = (this.head + 1) % this.size;
this.count--;
return true;
}
deleteLast() {
if (this.count === 0) {
return false;
}
this.count--;
return true;
}
getFront() {
return this.count === 0 ? -1 : this.buffer[this.head];
}
getRear() {
const last = (this.head + this.count - 1) % this.size;
return this.count === 0 ? -1 : this.buffer[last];
}
}
const deque = new CircularDeque(k);
const output = [];
for (let i = 0; i < operations.length; i++) {
const name = operations[i];
const arg = values[i];
if (name === 'insertFront') {
output.push(deque.insertFront(arg[0]));
} else if (name === 'insertLast') {
output.push(deque.insertLast(arg[0]));
} else if (name === 'deleteFront') {
output.push(deque.deleteFront());
} else if (name === 'deleteLast') {
output.push(deque.deleteLast());
} else if (name === 'getFront') {
output.push(deque.getFront());
} else {
output.push(deque.getRear());
}
}
return output;
}- Time
- O(1) per operation
- Space
- O(k)
Test cases
| Input | Expected | Covers |
|---|---|---|
k = 3, operations = ['insertLast', 'insertLast', 'insertFront', 'insertFront', 'getRear', 'deleteLast', 'insertFront', 'getFront'], values = [[1], [2], [3], [4], [], [], [4], []] | [true, true, true, false, 2, true, true, 4] | example from the docstring, both ends plus a full deque |
k = 1, operations = ['insertFront', 'getFront', 'getRear', 'deleteFront', 'getFront'], values = [[9], [], [], [], []] | [true, 9, 9, true, -1] | a single slot is both the front and the back |
k = 2, operations = ['deleteFront', 'deleteLast', 'getFront'], values = [[], [], []] | [false, false, -1] | removing and reading from an empty deque, the degenerate case |
k = 2, operations = ['insertFront', 'insertFront', 'insertFront', 'getFront', 'getRear'], values = [[1], [2], [3], [], []] | [true, true, false, 2, 1] | repeated front inserts wrap head backwards and then hit the capacity limit |
k = 3, operations = ['insertLast', 'insertLast', 'insertLast', 'deleteFront', 'getFront', 'getRear'], values = [[1], [2], [3], [], [], []] | [true, true, true, true, 2, 3] | using only one end behaves exactly like an ordinary queue |
k = 4, operations = ['insertFront', 'insertLast', 'getFront', 'getRear'], values = [[-5], [7], [], []] | [true, true, -5, 7] | a front insert wraps to the last slot while a back insert lands at slot 0 |