Implementing Stacks with JavaScript 
Tags: javascript, beginners, stacks, webdev
Published: 2020-07-02 00:18:25

While arrays allow us to add or remove elements at any index, sometimes we need a data structure where we have more control over adding and removing items. In this article, I am going to explain what stacks are, how we can use them to address this sort of problem, and provide examples of implementation. 

# What is a Stack?
A stack is an ordered collection of items that follows the last in, first out (LIFO) principle. In other words, the addition and removal of items happen at the same end. The newest elements are near the *top* of the stack and the oldest are near the *base*. You can think of a stack as a stack of books or even your browser history (the browser’s back button). 

## The Pros and Cons of Stacks
Stacks allow for constant time when adding and removing elements. This is due to the fact that you don’t need to shift elements around to add and remove them from the stack. 

The downside of stacks is that they don’t offer constant-time access to the nth element in the stack, unlike an array. This means it could take O(n) time to retrieve an element where n is the number of elements in the stack. 

## Creating an Array-based Stack Class
I encourage you to try this on your own if you haven’t before since it is a great way to learn about how stacks work and to experiment with this essential data structure. 
```javascript
class Stack {
  constructor() {
    this.items = [];
  }
}
```
In our example, we are using an array to store the elements of the stack. Since the stack follows the LIFO principle however, we will need to limit the functionalities that will be available for the insertion and removal of elements. The following methods will be available in the Stack class: 
- `push(element(s))`: add an element (or several elements) to the top of the stack.
- `pop()`: remove the top element of the stack and return the removed element. 
- `peek()`: return the top element of the stack without modifying the stack itself. 
- `isEmpty()`: return `true` if the stack does not contain any elements, `false` if the stack’s size is greater than 0.
- `clear()`: remove all elements from the stack.
- `size()`: return the number of elements in the stack (similar to the `length` property of an array). 
If you want some practice, I challenge you to implement the methods mentioned above on your own. If  you don’t want spoilers, stop scrolling! 

![illustration of push and pop on a stack](https://res.cloudinary.com/practicaldev/image/fetch/s--GS1k4iwx--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://thepracticaldev.s3.amazonaws.com/i/l8r4ic2gedi0j9obd7ix.jpg)

```javascript
class Stack {
	constructor() {
		this.items =[];
	}

	push(item) {
		return this.items.push(item);
	}
	
	pop() {
		return this.items.pop();
	}
	
	peek() {
		return this.items[this.length - 1];
	}

	isEmpty() {
		return this.items.length === 0;
	}

	clear() {
		this.items = [];
	}

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

## Solving Problems Using Stacks
Stacks can be applied to a variety of real-world problems. They can be used for backtracking problems, remembering paths taken, and to undo actions. I will go over one example and encourage you to try solving others on your own, perhaps through [HackerRank](https://www.hackerrank.com/domains/data-structures?filters%5Bsubdomains%5D%5B%5D=stacks). 

### Convert Decimal Numbers to Binary
To convert a decimal number into a binary representation, we can divide the number by 2 (since binary is a base 2 number system) until the division result is 0. For example:

![decimal to binary conversion example](https://www.onlinemath4all.com/images/decimal2binary.png)

Here is a solution using a stack:
```javascript
function decimalToBinary(num) {
	const remStack = [];
  	let number = num;
	let rem;
	let binaryString = '';
	
	while (number > 0) {
		rem = Math.floor(number % 2);
		remStack.push(rem);
		number = Math.floor(number / 2);
	}

	while (remStack.length !== 0) {
		binaryString += remStack.pop().toString();
	}

	return binaryString;
}
```
In this algorithm, while the division result is not zero, we get the remainder of the division (modulo - mod), and push it to the stack and update the number that will be divided by 2. Then, we pop the elements from the stack until it is empty, concatenating the elements that were removed from the stack to a string. 

# Conclusion
In this article, we learned about the stack data structure, implemented our own algorithm that represents a stack using arrays, and we did a practice problem. To learn more, I recommend checking out some of these resources:
- [How to Implement a Stack](https://www.freecodecamp.org/news/stack-5404d9735f88/) by Prashant Yadav of freeCodeCamp
- [Stacks in JavaScript](http://dl.booktolearn.com/ebooks2/computer/programming/9781788623872_Learning_JavaScript_Data_Structures_and_Algorithms_e5b9.pdf) by Loiane Groner from the textbook, Learning JavaScript Data Structures and Algorithms