High-performance Deque (Double-Ended Queue) for DSA practice with O(1) operations
npm install arrayqequeA high-performance ArrayDeque (Double-Ended Queue) implementation in TypeScript, optimized for Data Structures and Algorithms practice. All operations are O(1) time complexity (amortized).
- ✅ O(1) Operations: All main operations run in constant time (amortized)
- ✅ Versatile: Use as Stack, Queue, or ArrayDeque
- ✅ Type-Safe: Full TypeScript support with generics
- ✅ Memory Efficient: Circular buffer with dynamic growth
- ✅ Well-Documented: JSDoc with time/space complexity annotations
- ✅ Iterable: Works with for...of loops and spread operator
- ✅ Zero Dependencies: Lightweight and standalone
``bash`
npm install arraydeque
`typescript
import { ArrayDeque } from 'arraydeque';
const deque = new ArrayDeque
// Use as Stack (LIFO)
deque.push(1);
deque.push(2);
console.log(deque.pop()); // 2
// Use as Queue (FIFO)
deque.enqueue(1);
deque.enqueue(2);
console.log(deque.dequeue()); // 1
// Use as ArrayDeque
deque.pushFront(1);
deque.pushBack(2);
console.log(deque.popFront()); // 1
console.log(deque.popBack()); // 2
`
`typescript`
new ArrayDeque
Creates a new deque with optional initial capacity (default: 16).
| Property | Type | Description | Time |
|----------|------|-------------|------|
| size | number | Number of elements | O(1) |
| Method | Description | Time |
|--------|-------------|------|
| push(value) | Add to back | O(1) amortized |pop()
| | Remove from back | O(1) |peek()
| | View back element | O(1) |top()
| | Alias for peek | O(1) |
| Method | Description | Time |
|--------|-------------|------|
| enqueue(value) | Add to back | O(1) amortized |dequeue()
| | Remove from front | O(1) |front()
| | View front element | O(1) |back()
| | View back element | O(1) |
| Method | Description | Time |
|--------|-------------|------|
| pushFront(value) | Add to front | O(1) amortized |pushBack(value)
| | Add to back | O(1) amortized |popFront()
| | Remove from front | O(1) |popBack()
| | Remove from back | O(1) |peekFront()
| | View front element | O(1) |peekBack()
| | View back element | O(1) |
| Method | Description | Time |
|--------|-------------|------|
| unshift(value) | Add to front | O(1) amortized |shift()
| | Remove from front | O(1) |at(index)
| | Access by index | O(1) |
| Method | Description | Time |
|--------|-------------|------|
| isEmpty() | Check if empty | O(1) |clear()
| | Remove all elements | O(1) |toArray()
| | Convert to array | O(n) |clone()
| | Create shallow copy | O(n) |toString()
| | String representation | O(n) |
`typescript
const bfs = (graph: Map
const deque = new ArrayDeque
const visited = new Set
deque.enqueue(start);
visited.add(start);
while (!deque.isEmpty()) {
const node = deque.dequeue()!;
console.log(node);
for (const neighbor of graph.get(node) || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
deque.enqueue(neighbor);
}
}
}
};
`
`typescript
const bfs01 = (graph: [number, number][][], start: number) => {
const deque = new ArrayDeque<[number, number]>();
const dist = new Map
deque.pushBack([start, 0]);
dist.set(start, 0);
while (!deque.isEmpty()) {
const [node, d] = deque.popFront()!;
if (d > dist.get(node)!) continue;
for (const [neighbor, weight] of graph[node] || []) {
const newDist = d + weight;
if (!dist.has(neighbor) || newDist < dist.get(neighbor)!) {
dist.set(neighbor, newDist);
if (weight === 0) {
deque.pushFront([neighbor, newDist]); // 0-weight edge
} else {
deque.pushBack([neighbor, newDist]); // 1-weight edge
}
}
}
}
return dist;
};
`
`typescript
const slidingWindowMaximum = (nums: number[], k: number): number[] => {
const deque = new ArrayDeque
const result: number[] = [];
for (let i = 0; i < nums.length; i++) {
// Remove indices outside window
while (!deque.isEmpty() && deque.peekFront()! < i - k + 1) {
deque.popFront();
}
// Remove smaller elements
while (!deque.isEmpty() && nums[deque.peekBack()!] < nums[i]) {
deque.popBack();
}
deque.pushBack(i);
if (i >= k - 1) {
result.push(nums[deque.peekFront()!]);
}
}
return result;
};
`
All main operations are O(1) amortized time complexity:
- Push/Pop (both ends): O(1) amortized
- Peek (both ends): O(1)
- Size/isEmpty: O(1)
- Random access via at(): O(1)
Space complexity: O(n) where n is the number of elements.
Unlike JavaScript's built-in array methods:
- Array.shift() is O(n) - our popFront() is O(1)Array.unshift()
- is O(n) - our pushFront()` is O(1)
This makes our ArrayDeque significantly faster for algorithms that require frequent front operations, such as BFS, sliding window problems, and 0-1 BFS.
MIT
Contributions are welcome! Please feel free to submit a Pull Request.