Implementing stack in JavaScript
Stacks are very similar to queues with one key difference - only the top element is accessible as in LIFO (last in first out). A common analogy to visualize stack is with a stack of plates in a spring-loaded container. One can only add or remove plates at the top. A function call stack is also created in a similar way - when one function calls the another, the called function sits on top of the calling function, and so on.
Stack Operations
new Stack() // create a new stack
TOP(s) // return the first element
PUSH(obj, s) // add object to top of stack
POP(s) // remove and return object from the head
EMPTY(s) // check if stack is empty
Implementing stack in JavaScript is very similar to queue:
// Implementing a stack
//
// create a constructor for stack
function Stack() {
this.data = [];
this.isEmpty = true;
this.top = null;
}
// push method for stack adds value to top
Stack.prototype.push = function(value)
{
if (this.isEmpty)
{
this.data[0] = value;
this.top = this.data[0];
this.isEmpty = false;
}
else
{
this.data[this.data.length] = value;
this.top = value;
}
};
// pop method for stack
// returns and removes the top element
Stack.prototype.pop = function()
{
if (this.isEmpty)
console.log("Stack is already empty!");
else
{
top = this.data[this.data.length - 1];
delete this.data[this.data.length - 1];
this.data.pop();
this.top = this.data[0];
if (this.data.length == 0)
{
this.top = null;
this.isEmpty = true;
}
return top;
}
};
Let's test it
s = new Stack();
console.log(s.top);
console.log(s.isEmpty);
//add three elements to stack
s.push(5);
console.log(); console.log("Top is", s.top);
s.push(6);
s.push(87);
console.log(); console.log("Top is", s.top);
console.log("Is s empty?", s.isEmpty);
// remove two elements from top
s.pop();
s.pop();
console.log();
console.log("Top is", s.top);
console.log("Is s empty?", s.isEmpty);
s.pop();
console.log();
console.log("Top is", s.top);
console.log("Is s empty?", s.isEmpty);
s.pop();
null
true
Top is 5
Top is 87
Is s empty? false
Top is 5
Is s empty? false
Top is null
Is s empty? true
Stack is already empty!