Using Linked list to implement a Queue.
In javascript, if you want to push a item in front of an Array, it need to shift the rest of items, not good for performance. Using Linked List is O(1) oepration for enque and deque, which is better.
Usecase: Let's say you want to keep at most 20 items, can use a Queue
type Node<T> = {
value: T;
next?: Node<T>;
};
// use a linked list to implement a queue
export default class Queue<T> {
public length: number;
private head?: Node<T>;
private tail?: Node<T>;
constructor() {
this.length = 0;
this.head = this.tail = undefined;
}
enqueue(item: T): void {
const node = { value: item };
this.length++;
if (!this.tail) {
this.head = this.tail = node;
return;
}
this.tail.next = node;
this.tail = node;
}
deque(): T | undefined {
if (!this.head) {
return undefined;
}
this.length--;
const head = this.head;
this.head = this.head.next;
// free up memory
head.next = undefined;
// clean up tail
if (this.length === 0) {
this.tail = undefined;
}
return head.value;
}
peek(): T | undefined {
return this.head?.value;
}
}
Test:
import Queue from "@code/Queue";
test("queue", function () {
const list = new Queue<number>();
list.enqueue(5);
list.enqueue(7);
list.enqueue(9);
expect(list.deque()).toEqual(5);
expect(list.length).toEqual(2);
// this must be wrong..?
debugger;
// i hate using debuggers
list.enqueue(11);
debugger;
expect(list.deque()).toEqual(7);
expect(list.deque()).toEqual(9);
expect(list.peek()).toEqual(11);
expect(list.deque()).toEqual(11);
expect(list.deque()).toEqual(undefined);
expect(list.length).toEqual(0);
// just wanted to make sure that I could not blow up myself when i remove
// everything
list.enqueue(69);
expect(list.peek()).toEqual(69);
expect(list.length).toEqual(1);
});
标签:head,Typescript,toEqual,list,Queue,tail,expect From: https://www.cnblogs.com/Answer1215/p/17565515.html