Implementation of Stack in JavaScript
Implementation of a stack in JavaScript involves creating a data structure that follows the Last-In-First-Out (LIFO) principle, where elements are added and removed from the same end. We use stacks to manage function calls, undo functionality, and parse algorithms efficiently in JavaScript applications.
Note : Assuming the stack can grow dynamically we are not considering the overflow condition.
Examples: Below is an example of a stack class using an array in JavaScript.
// Stack class
class Stack {
// Array is used to implement stack
constructor()
{
this.items = [];
}
// Functions to be implemented
// push(item)
// pop()
// peek()
// isEmpty()
// printStack()
}
As you can see in the above definition we have created a skeleton of a stack class which contains a constructor in which we declare an array to implement stack. Hence, with the creation of an object of a stack class, this constructor would be called automatically.
Methods in Stack
- Push: Used to add an element to the stack. This method adds an element at the top of the stack.
// push function
push(element)
{
// push element into the items
this.items.push(element);
}
- Pop() : Removes an element from the stack, if the function is call on an empty stack it indicates “Underflow”. This method returns the topmost element of stack and removes it. Return underflow when called on an empty stack.
// pop function
pop()
{
// return top most element in the stack
// and removes it from the stack
// Underflow if stack is empty
if (this.items.length == 0)
return 'Underflow'
return this.items.pop();
}
- Peek() : returns the top most elements in the stack, but doesn’t delete it. It Return the topmost element without removing it from the stack.
// peek function
peek()
{
// return the top most element from the stack
// but does'nt delete it.
return this.items[this.items.length - 1];
}
Helper methods
- isEmpty() : return true if the stack is empty. Returns true if the stack is empty.
// isEmpty function
isEmpty()
{
// return true if stack is empty
return this.items.length == 0;
}
- printStack() : This method returns a string in which all the element of an stack is concatenated.
// printStack function
printStack()
{
let str = "";
for (let i = 0; i < this.items.length; i++)
str += this.items[i] + " ";
return str;
}
Note : Different helper function can be declared in Stack class as per the requirement. Now as we are done with defining the stack class lets use it.
Sample Functions
Example: In this example we would create an object of stack class and test few functions of it.
// creating object for stack class
let stack = new Stack();
// testing isEmpty and pop on an empty stack
// returns false
console.log(stack.isEmpty());
// returns Underflow
console.log(stack.pop());
Example: Some more functions of stack class
// Adding element to the stack
stack.push(10);
stack.push(20);
stack.push(30);
// Printing the stack element
// prints [10, 20, 30]
console.log(stack.printStack());
// returns 30
console.log(stack.peek());
// returns 30 and remove it from stack
console.log(stack.pop());
// returns [10, 20]
console.log(stack.printStack());
Application: Evaluation of Postfix Expression
Example: In this example, we would use the above stack class to evaluate postfix expression.
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
if (this.items.length === 0) {
return "Underflow";
}
return this.items.pop();
}
}
function postFixEvaluation(exp) {
let stack = new Stack();
for (let i = 0; i < exp.length; i++) {
let c = exp[i];
if (!isNaN(c))
stack.push(c - '0');
else {
let val1 = stack.pop();
let val2 = stack.pop();
if (val1 == "Underflow" || val2 == "Underflow")
return "Can not perform postfix evaluation";
switch (c) {
case '+':
stack.push(val2 + val1);
break;
case '-':
stack.push(val2 - val1);
break;
case '/':
stack.push(val2 / val1);
break;
case '*':
stack.push(val2 * val1);
break;
}
}
}
return stack.pop();
}
// calling the above method
// returns 9
console.log(postFixEvaluation("235*+8-"));
// returns "Can not perform postfix evaluation"
console.log(postFixEvaluation("23*+"));
Output
9 Can not perform postfix evaluation
Contact Us