What is a stack?
A LIFO data structure
LIFO (Last in first out)
The last element added to the stack will be the first element removed from the stack.
Think about it like a pile of books. You can only add books on top, and you can only remove the book on top.
we are going to create stack that has only two methods
- Push() : Method to add data to the stack
- Pop() : Method to remove data from the stack
we can do this in different ways, In this article we are going to implement with JavaScript es6 classes.
JavaScript Stack Implementation
class Node {
constructor(val) {
this.val = val
this.next = null
}
}
class Stack {
constructor() {
this.first = null;
this.last = null;
this.size = 0
}
push(val) {
let newNode = new Node(val)
if (!this.first) {
this.first = newNode;
this.last = newNode;
}
else {
let temp = this.first;
this.first = newNode;
this.first.next = temp;
}
return ++this.size;
}
pop() {
if (!this.first) return null;
let temp = this.first;
if (this.size === 1) {
this.last = null;
}
this.first = this.first.next
this.size--;
return temp.value
}
}
const stack = new Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.pop()
stack.pop()
stack.pop()
stack.pop()
Where stacks are used
- Managing function invocations
- Undo/Redo
- Routing (History Object)
BIG O of Stacks
Insertion - O(1)
Removal - O(1)
Searching - O(n)
Access - O(n)
Top comments (0)