Created
July 15, 2018 11:24
-
-
Save Youka/e28beeb31f585ac9b9532636cadbdb8d to your computer and use it in GitHub Desktop.
Double-ended queue (typescript)
This file contains hidden or 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
// 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