Last active
March 7, 2020 18:14
-
-
Save Prottoy2938/008e5f6fb2dc2c61c53b7141d9284d31 to your computer and use it in GitHub Desktop.
Stack and Queue data structure in JavaScript
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
//Stack implementation================================================================================== | |
// Stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. | |
class Node { | |
constructor(data, next = null) { | |
this.data = data; | |
this.next = next; | |
} | |
} | |
class Stack { | |
constructor() { | |
this.first = null; | |
this.last = null; | |
this.size = 0; | |
} | |
//Adds element to the beginning of the list. similar to Array.unShift() | |
add(data) { | |
const newNode = new Node(data); | |
if (!this.first) { | |
this.last = newNode; | |
this.first = newNode; | |
} else { | |
const cptrFirst = this.first; | |
this.first = newNode; | |
newNode.next = cptrFirst; | |
} | |
return ++this.size; | |
} | |
//Removes element from the beginning of the list. similar to Array.shift() | |
remove() { | |
if (!this.first) return null; | |
const cptrFirst = this.first; | |
this.first = this.first.next; | |
this.size--; | |
cptrFirst.next = null; //removing the connection, not necessary but important | |
return cptrFirst.data; | |
} | |
} | |
//This class two methods are similar to `Array.unShift()` and `Array.shift()`, but it can be also done with `Array.push()` and `Array.pop()` | |
//EXAMPLES | |
const stack = new Stack(); | |
stack.add("Hello"); | |
stack.add("World"); | |
stack.add("!"); | |
stack.remove() | |
//Queue is a container of objects (a linear collection) that are inserted and removed according to the first-in first-out (FIFO) principle. | |
//Queues implementation========================================================================== | |
class Node { | |
constructor(data, next=null) { | |
this.value = data; | |
this.next = next; | |
} | |
} | |
class Queues { | |
constructor() { | |
this.first = 0; | |
this.last = 0; | |
this.size = 0; | |
} | |
//Adds element to the end of the list. Similar to Array.push() | |
add(data) { | |
const newNode = new Node(data); | |
if (!this.first) { | |
this.first = newNode; | |
} else { | |
//`this.tail.next` has the same reference as `this.head`'s very last item aka the last item of the list. So modifying `this.tail.next` will also modifies `this.head`'s last item. | |
this.last.next = newNode; | |
} | |
this.last = newNode; | |
return ++this.size; | |
} | |
//removes element from the beginning of the list. Similar to Array.shift() | |
remove() { | |
if (this.size === 0) return null; | |
if (this.size === 1) this.last = null; | |
const cptrFirst = this.first; | |
this.first = this.first.next; | |
this.size--; | |
cptrFirst.next = null; //removing the connection, not necessary but important. | |
return cptrFirst; | |
} | |
} | |
//This class have two method which are similar to `Array.push()` and `Array.shift()`, but it can be also done with creating methods like `Array.unShift()` and `Array.pop()` | |
//EXAMPLES | |
const queues = new Queues(); | |
queues.add("Hello"); | |
queues.add("World"); | |
queues.add("!"); | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment