Medium difficulty · Algorithm · Topics: queue, design, deque, circular-array
A deque (double-ended queue, pronounced "deck") lets you insert and remove elements at both ends in O(1). It generalizes both the stack and the queue: use only one end and it is a stack; insert at the back and remove from the front and it is a queue. This implementation stores the elements in a circular array of fixed capacity.
A normal array queue wastes space because its indices only move right. If the array is treated as a ring, where the slot after the last one is the first again, the elements can live anywhere in the ring and both ends can move freely. Index arithmetic with % capacity does the wrapping: stepping right is (i + 1) % cap, stepping left is (i - 1 + cap) % cap.
The invariant: the deque holds count elements in the slots front, front + 1, ..., front + count - 1 (all modulo capacity). The back element is therefore at (front + count - 1) % cap.
capacity empty slots, front = 0, count = 0.falsexrear = (front + count) % capcountfalse. Move front one slot left (with wrap-around), store x there, increase count.items[front], clear it, move front one slot right, decrease count.rear = (front + count - 1) % cap, decrease count.count === 0. isFull: count === capacity.Test case 0 uses capacity = 4. Logical order is written front first.
| Operation | front | items | Logical order | Result |
|---|---|---|---|---|
pushBack(1) | 0 | [1, null, null, null] | 1 | true |
pushBack(2) | 0 | [1, 2, null, null] | 1, 2 | true |
pushFront(3) | 3 | [1, 2, null, 3] | 3, 1, 2 | true (front wraps to 3) |
pushFront(4) | 2 | [1, 2, 4, 3] | 4, 3, 1, 2 | true |
isFull() | 2 | unchanged | true | |
pushBack(5) | 2 | unchanged | false | |
peekFront() / peekBack() | 2 | unchanged | 4 / 2 | |
popFront() | 3 | [1, 2, null, 3] | 3, 1, 2 | 4 |
popBack() | 3 | [1, null, null, 3] | 3, 1 | 2 |
popFront() | 0 | [1, null, null, null] | 1 | 3 |
popBack() | 0 | [null, null, null, null] | empty | 1 |
popBack() | 0 | unchanged | empty | null |
isEmpty() | 0 | unchanged | true |
| Operation | Time | Why |
|---|---|---|
| pushFront, pushBack, popFront, popBack | O(1) | index arithmetic only; no shifting |
| peekFront, peekBack, isEmpty, isFull | O(1) | one slot or one counter |
| Space | O(capacity) | one fixed array |
(front - 1) % cap gives a negative index in JavaScript; add cap first.front and the back index look the same in both cases. Keeping a count (as here) removes the ambiguity.pushBack/popFront indices reach cap.front + count instead of front + count - 1 when you want the last element.front and rear are computed before each access to this.items, so their chips show on the cells being read or written. After pushFront(3), front jumps from 0 to the last cell: that is the wrap-around.count goes up on every push and down on every pop and decides isFull / isEmpty.Input
["Deque", "pushBack", "pushBack", "pushFront", "pushFront", "isFull", "pushBack", "peekFront", "peekBack", "popFront", "popBack", "popFront", "popBack", "popBack", "isEmpty"]
[[4], [1], [2], [3], [4], [], [5], [], [], [], [], [], [], [], []]
Output
[null, true, true, true, true, true, false, 4, 2, 4, 2, 3, 1, null, true]
class Deque {
constructor(capacity) {
this.items = new Array(capacity).fill(null); // circular storage
this.front = 0; // index of the first element
this.count = 0; // number of stored elements
}
// Insert at the back: the slot just after the last element.
pushBack(x) {
if (this.isFull()) {
return false;
}
const rear = (this.front + this.count) % this.items.length;
this.items[rear] = x;
this.count++;
return true;
}
// Insert at the front: step front one slot to the left (wrapping around).
pushFront(x) {
if (this.isFull()) {
return false;
}
const front = (this.front - 1 + this.items.length) % this.items.length;
this.front = front;
this.items[front] = x;
this.count++;
return true;
}
popFront() {
if (this.isEmpty()) {
return null;
}
const front = this.front;
const value = this.items[front];
this.items[front] = null;
this.front = (front + 1) % this.items.length;
this.count--;
return value;
}
popBack() {
if (this.isEmpty()) {
return null;
}
const rear = (this.front + this.count - 1) % this.items.length;
const value = this.items[rear];
this.items[rear] = null;
this.count--;
return value;
}
peekFront() {
if (this.isEmpty()) {
return null;
}
const front = this.front;
return this.items[front];
}
peekBack() {
if (this.isEmpty()) {
return null;
}
const rear = (this.front + this.count - 1) % this.items.length;
return this.items[rear];
}
isEmpty() {
return this.count === 0;
}
isFull() {
return this.count === this.items.length;
}
}