Skip to content

Instantly share code, notes, and snippets.

@Youka
Created July 15, 2018 11:24
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Youka/e28beeb31f585ac9b9532636cadbdb8d to your computer and use it in GitHub Desktop.
Save Youka/e28beeb31f585ac9b9532636cadbdb8d to your computer and use it in GitHub Desktop.
Double-ended queue (typescript)
// Linked data structure part
interface Node<T> {
previous: Node<T>,
value: T,
next: Node<T>
}
// Double-ended queue structure
class Deque<T> {
private first: Node<T> = null;
private last: Node<T> = null;
private size: number = 0;
public get length() {
return this.size;
}
public pushBack(value: T) {
// Update last
const last = this.last;
this.last = {previous: last, value: value, next: null};
if(last !== null)
last.next = this.last;
// Update first
if(this.first === null)
this.first = this.last;
// Update size
this.size++;
// Return new size
return this.size;
}
public pushFront(value: T) {
// Update first
const first = this.first;
this.first = {previous: null, value: value, next: first};
if(first !== null)
first.previous = this.first;
// Update last
if(this.last === null)
this.last = this.first;
// Update size
this.size++;
// Return new size
return this.size;
}
public popBack() {
// Check possibility
if(this.size === 0)
return null;
// Update last
const entry = this.last;
this.last = entry.previous;
if(this.last !== null)
this.last.next = null;
// Update first
if(this.first === entry)
this.first = null;
// Update size
this.size--;
// Return value of removed entry
return entry.value;
}
public popFront() {
// Check possibility
if(this.size === 0)
return null;
// Update first
const entry = this.first;
this.first = entry.next;
if(this.first !== null)
this.first.previous = null;
// Update last
if(this.last === entry)
this.last = null;
// Update size
this.size--;
// Return value of removed entry
return entry.value;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment