# Data Structures: Stack

## A simple guide to understanding Stack data structure ๐

## Introduction

Stack is a **Last In First Out** data structure that holds a collection of items. The last element pushed into the stack will be the first element that is going to be removed. The stack data structure is one of the most used data structures and is simple to learn.

## Important Concept

- The last item that is pushed into the stack is called the top of the stack.
- Stack works on LIFO (last in first out) system which means the last pushed item will be removed first.
- In a stack, we always perform insertion and deletion at the top of the stack.

## Time Complexity

Operation | Time Complexity |

Search | O(n) |

Push | O(1) |

Pop | O(1) |

Peek | O(1) |

## Applications of Stack

### Undo/Redo

For Undo/Redo features, the stack has been a choice for a lot of engineers. Stack and momento design pattern combined are heavily used to create Undo/Redo mechanism.

### Backtracking

Backtracking is one of the algorithm designing techniques. In backtracking, we try a way to solve a problem. If that way is not efficient, we come back to the previous state and go into some other paths. To get back from the current state, we need to store the previous state. For that purpose, we need a stack.

### CallStack

If you are working with javascript then you will definitely come across the term "Call Stack". Yes, javascript execution states are also maintained in a stack that is in the browser. For more information read my blog How V8 engine works?

## Coding a Stack in JavaScript

Let's take a look at how we can create a stack in javascript

```
class Stack {
constructor() {
this.items = []; // initially, the stack is empty.
}
}
```

We are going to use Arrays to create a stack. We have created a simple class named `Stack`

and inside the constructor, we are initializing an empty array which is an empty stack.

Now let's take a look at some of the most important operations of a stack.

#### push

Adding an item at the **end/top of a stack** is called `push`

```
push(item) {
this.items.push(item);
return item;
}
```

#### pop

Removing an item at the **end/top of a stack** is called `pop`

.

```
pop() {
return this.items.pop();
}
```

#### length / size

`size`

method returns the length of the stack or the count of total items in the stack.

```
size() {
return this.items.length;
}
```

#### peek

`peek`

method returns the top element of the stack.

```
peek() {
return this.items[this.size() - 1];
}
```

Now, we have coded all the operations in the stack, let's test it.

```
const stack = new Stack(); // [] => Empty stack
stack.push(1); // [1];
stack.push("Heyy!!"); // [1, 'Heyy!!']
stack.size(); // 2
stack.peek(); // "Heyy!!"
stack.push(false); // [1, "Heyy!!", false]
stack.pop(); // After pop, stack: [1, "Hey!!"]
stack.pop(); // After pop, stack: [1]
stack.peek(); // 1
```

## Improvements?

For now, the basic functionality of the stack is done. But yes, we can add more stuff to make it more functional. And you are going to do it as your assignment.

### Tasks:

Add an

`isEmpty()`

function which can check either a stack is empty or not. The function will return`boolean`

`true`

if the stack is empty and`false`

if not.Use that function in the

`pop`

,`peek`

and`size`

method and provide user-friendly messages to users. For example, If I'm poping an element from the stack, and the stack is already empty, you can show a message`The stack is already empty.`

That's all folks!

That's it, folks! hope it was a good read for you. Thank you! โจ