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

## Top comments (0)