Sources Contact Advanced Search Tutorials

An Interest In:

Web News this Week

Search Archive

Some of Our Sources

View All Sources

Help Webnuz

Referal links:

January 9, 2022 11:50 am GMT

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()); // cbaconsole.log(stack.reverseV1()); // cba

TC - O(n) to process stack
SC - O(n) for storing the reverse string

Github Link

Original Link: https://dev.to/ajayv1/reverse-stack-using-javascript-4fmm

Share this article:

View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To