Reverse Stack using Javascript
In this article, I would like to discuss about the stack data structure.
1. What is Stack?
Stack is a linear data structure which works on a principle of Last in First Out (popularly known as LIFO).
If you know about the recursion where program has to go deep (in downwards) and build the solution upward, stack is the obvious choice for it.
Other problems where Stack suited the most -
- Checking if parenthesis or balanced or not
- Reversing array using stack
- expression computation
2. How to create Stack in Javascript?
Stack have following primitive operation -
- push(val)
- pop()
- peek()
- is_empty()
Lets define the object prototype of Stack -
function Stack() {
this.arr = [];
this.top = 0;
}
arr - an array which holds the stack item
top - a pointer which points to the top of stack
push(val)
push function take val and insert it to the top of stack
Stack.prototype.push = function (val) {
this.arr[this.top] = val;
this.top = this.top + 1;
}
pop()
pop remove the top element of the stack, also returned it
Stack.prototype.pop = function () {
if (this.is_empty()) {
throw new Error("Underflow, stack is empty");
}
var topEl = this.arr[this.top - 1];
this.top = this.top - 1;
this.arr.pop();
return topEl;
}
peek()
peek function doesn't delete the data from the stack, instead it just return the top of the stack
Stack.prototype.peek = function () {
if (this.is_empty()) {
throw new Error("Underflow, stack is empty");
}
return this.arr[this.top - 1];
}
is_empty()
is_empty function returns true if the stack is empty else false
Stack.prototype.is_empty = function () {
return this.top === 0;
}
Lets put all the code together -
function Stack() {
this.arr = [];
this.top = 0;
}
Stack.prototype.push = function (val) {
this.arr[this.top] = val;
this.top = this.top + 1;
}
Stack.prototype.pop = function () {
if (this.is_empty()) {
throw new Error("Underflow, stack is empty");
}
var topEl = this.arr[this.top - 1];
this.top = this.top - 1;
this.arr.pop();
return topEl;
}
Stack.prototype.is_empty = function () {
return this.top === 0;
}
3. How to reverse stack?
Approach 1 - Modify original Stack
Pop element from stack one by one and store in new string, this new string will be the reverse of original string.
Let's create a reverse function which reverse the stack and return the reverse string.
Stack.prototype.reverse = function () {
if (this.is_empty()) {
throw new Error("Underflow, stack is empty");
}
var revStr = '';
while(!this.is_empty()) {
revStr += this.pop();
}
return revStr;
}
Approach 2 - Keep original Stack as it is
Since, with the above implementation, we have the reference of the stack arr which have the stack data. Now with top pointer we can loop over arr and process the stack and store the reverse string and return.
Stack.prototype.reverseAlternate = function () {
if (this.is_empty()) {
throw new Error("Underflow, stack is empty");
}
var revStr = '';
for (var i = this.top - 1; i >= 0; i--) {
revStr += this.arr[i];
}
return revStr;
}
Combining all code together with example -
function Stack() {
this.arr = [];
this.top = 0;
}
Stack.prototype.push = function (val) {
this.arr[this.top] = val;
this.top = this.top + 1;
}
Stack.prototype.pop = function () {
if (this.is_empty()) {
throw new Error("Underflow, stack is empty");
}
var topEl = this.arr[this.top - 1];
this.top = this.top - 1;
this.arr.pop();
return topEl;
}
Stack.prototype.is_empty = function () {
return this.top === 0;
}
Stack.prototype.reverse = function () {
if (this.is_empty()) {
throw new Error("Underflow, stack is empty");
}
var revStr = '';
for (var i = this.top - 1; i >= 0; i--) {
revStr += this.arr[i];
}
return revStr;
}
Stack.prototype.reverseV1 = function () {
if (this.is_empty()) {
throw new Error("Underflow, stack is empty");
}
var revStr = '';
while(!this.is_empty()) {
revStr += this.pop();
}
return revStr;
}
var stack = new Stack();
stack.push('a');
stack.push('b');
stack.push('c');
console.log(stack.reverse()); // cba
console.log(stack.reverseV1()); // cba
TC - O(n) to process stack
SC - O(n) for storing the reverse string