DEV Community

Ajay Kumar Verma
Ajay Kumar Verma

Posted on • Updated on • Originally published at weekendtutorial.com

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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]; 

}
Enter fullscreen mode Exit fullscreen mode

is_empty()

is_empty function returns true if the stack is empty else false

Stack.prototype.is_empty = function () {
  return this.top === 0;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}


Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

Github Link

Top comments (0)