Created
July 13, 2021 14:25
-
-
Save davidkayce/de9db7d390acc449c795726f74d4cf7d to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Implement a queue using Delayed shift arrays - It consists of associating an index with the array. | |
// When an element is dequeued, the index moves forward. When the index reaches the middle of the array, | |
// the array is sliced in two to remove the first half. | |
// This is a FIFO data structure | |
/** Queue contains a linked list of Subqueue */ | |
class Subqueue <T> { | |
public full() { | |
return this.array.length >= 1000; | |
} | |
public get size() { | |
return this.array.length - this.index; | |
} | |
public peek(): T { | |
return this.array[this.index]; | |
} | |
public last(): T { | |
return this.array[this.array.length-1]; | |
} | |
public dequeue(): T { | |
return this.array[this.index++]; | |
} | |
public enqueue(elem: T) { | |
this.array.push(elem); | |
} | |
private index: number = 0; | |
private array: T [] = []; | |
public next: Subqueue<T> = null; | |
} | |
class Queue<T> { | |
get length() { | |
return this._size; | |
} | |
public push(...elems: T[]) { | |
for (let elem of elems) { | |
if (this.bottom.full()) { | |
this.bottom = this.bottom.next = new Subqueue<T>(); | |
} | |
this.bottom.enqueue(elem); | |
} | |
this._size += elems.length; | |
} | |
public shift(): T { | |
if (this._size === 0) { | |
return undefined; | |
} | |
const val = this.top.dequeue(); | |
this._size--; | |
if (this._size > 0 && this.top.size === 0 && this.top.full()) { | |
// Discard current subqueue and point top to the one after | |
this.top = this.top.next; | |
} | |
return val; | |
} | |
public peek(): T { | |
return this.top.peek(); | |
} | |
public last(): T { | |
return this.bottom.last(); | |
} | |
public clear() { | |
this.bottom = this.top = new Subqueue(); | |
this._size = 0; | |
} | |
private top: Subqueue<T> = new Subqueue(); | |
private bottom: Subqueue<T> = this.top; | |
private _size: number = 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment