Skip to content

Instantly share code, notes, and snippets.

@james4388
Created July 13, 2022 21:50
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save james4388/f594c07d708014bac060c4e562991ccf to your computer and use it in GitHub Desktop.
Save james4388/f594c07d708014bac060c4e562991ccf to your computer and use it in GitHub Desktop.
Deque implementation in TS
interface Queue<T> {
append(item: T);
appendLeft(item: T);
count(): number;
peak(): T;
peakLeft(): T;
pop(): T;
popLeft(): T;
clear();
[Symbol.iterator]();
}
export class IndexError extends Error {}
/**
* Double ended queue
* when maxLength is set this will behave like a sliding window eg: pop item from
* opposite side to maintain size.
* Note this implement is not thread safe but totally safe with Nodejs (single threaded)
*/
export class Deque<T> implements Queue<T> {
private queue = new Map<number, T>();
private left = 0;
private right = 0;
constructor(iterables?: T[], private readonly maxLength: number = null) {
if (iterables) {
for (const item of iterables) {
this.append(item);
}
}
}
append = (item: T) => {
if (this.maxLength !== null && this.count() >= this.maxLength) {
this.popLeft();
}
this.queue.set(this.right, item);
this.right += 1;
}
appendLeft = (item: T) => {
if (this.maxLength !== null && this.count() >= this.maxLength) {
this.pop();
}
this.left -= 1;
this.queue.set(this.left, item);
}
count = (): number => {
return this.right - this.left;
}
peak = (): T => {
if (this.count() < 1) {
throw new IndexError('Queue is empty');
}
return this.queue.get(this.right - 1);
}
peakLeft = (): T => {
if (this.count() < 1) {
throw new IndexError('Queue is empty');
}
return this.queue.get(this.left);
}
pop = (): T => {
if (this.count() < 1) {
throw new IndexError('Queue is empty');
}
this.right -= 1;
const value = this.queue.get(this.right);
this.queue.delete(this.right);
return value;
}
popLeft = (): T => {
if (this.count() < 1) {
throw new IndexError('Queue is empty');
}
const value = this.queue.get(this.left);
this.queue.delete(this.left);
this.left += 1;
return value;
}
clear = () => {
this.queue.clear();
this.left = 0;
this.right = 0;
}
*[Symbol.iterator]() {
for (let index = this.left; index < this.right; index += 1) {
yield this.queue.get(index);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment