Skip to content

Instantly share code, notes, and snippets.

@Prottoy2938
Last active March 7, 2020 18:14
Show Gist options
  • Save Prottoy2938/008e5f6fb2dc2c61c53b7141d9284d31 to your computer and use it in GitHub Desktop.
Save Prottoy2938/008e5f6fb2dc2c61c53b7141d9284d31 to your computer and use it in GitHub Desktop.
Stack and Queue data structure in JavaScript
//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