JavaScript Stack Implementation
Stack is a structure used to store data in last in first out (LIFO) principle. Stack can be implemented in every Programming Language, while this article focuses on JavaScript implementation, the instructions provided can be used to implement stack in every other Programming Language.
Stack can be explained as a pile of books kept on top of each other. Two main methods of a stack are adding and removing data, same can be applied to the concept of books; new book can be put on top of the pile or the top book can be removed.
It is important to understand that, the LIFO principle means the stack shall be emptied to remove the bottom element, similarly all the books shall be removed from the top of the pile to get the bottom book.
What can a stack do?
Operations that stack can handle are listed:
- Push — adds an element to the top of the stack
- Pop — removes the top element from the stack
- isFull — determines if the stack is full
- isEmpty — determines if the stack is empty
- length — determines length of the stack
- peek — gets the top element from the stack
Stack Implementation in JavaScript
The first step is to create a class for Stack, with an array that will hold the data and a variable that will hold the index value,
class Stack {
constructor() {
this.dataStruct = [];
this.top = 0;
}
}The push()method will append data to the first index of the array (index 0), and increment this.top by 1 to point at the next index in the array, to do this we will take element as an argument,
push(element) {
this.dataStruct[this.top] = element;
this.top += 1;
}The pop() method will remove the last element from this.dataStruct and will decrement 1 from this.top to point at the element that was before,
pop() {
if (this.isEmpty()) {
return 'Stack Underflow';
}
if (this.dataStruct.length > 0) {
this.top -= 1;
return this.dataStruct.pop();
}
}The isEmpty() method will determine if the stack is empty or not,
isEmpty() {
if (this.dataStruct.length === 0) {
return true;
}
else
false;
}The length() method will print length of the stack,
length() {
return this.top;
}The peek() method will print the top element from the stack using isEmpty(),
peek() {
if (!this.isEmpty()) {
return this.dataStruct[this.top - 1];
}
}Last, the optional but useful printStack() method will be implemented, this method uses string formatting and for loop to get all elements available in the stack and print them to the console,
printStack() {
let temp = '';
if (this.isEmpty()) {
return 'Stack Empty';
}
else if (this.dataStruct.length > 0) {
for (let i = 0; i < this.dataStruct.length; ++i) {
temp += this.dataStruct[i] + '\n';
}
return temp;
}
}Real life Application of Stacks
Stack has many real life applications, one of the most commons is reversing an action. This method is used in: text editors, browsers, word processors, on Windows and even in Medium.
In Medium, every word typed, every image added in other words all of our actions are saved into a stack. Once CTRL + Z button is pressed, the current action is removed from the stack and the last action is accessed, this reverts to the last action that one performed. Later that removed data is added to another stack and when CTRL + Y is pressed it is being added back to the other stack, this brings the reverted action back.
Space Complexity of the Stack
The space of Stack is an array and number of operations is number of data in the stack at the current time. This means that Space Complexity O(n) of stack is constant O(1).
