JavaScript Program to Implement a Stack

Introduction

Data is the main entity in this modern era for nearly every process we need some data and with no doubt, each process should be fast. To store data and properly organize the data so that handling the data becomes easy to add new data, update existing data, and delete or access the data efficiently we have data structures.

Data structures can be of various types based on the requirement like if we need the elements in a sorted manner and all unique values then we can use the set, if we want to collect the frequency of the random numbers or keys then we can use the map, etc.

Data structures can be designed using dynamic memory allocation or using the previously defined data structure such as an array. Sometimes an algorithm is also included with the data structure to decrease the time complexity of a particular operation.

Let’s see the javascript stack data structure and move to its implementation in javascript:

Introduction to the Stack Data Structure

Imagine a scenario: there is a stack of books on the table what type of operations we can perform on it if at a single time we can pick only one book? First, we can add a new book to the stack, second, we can take away the topmost book from the stack and last, we can read the topmost book without moving it.

Similarly, a Javascript stack is a linear data structure that takes the elements and stores them. We can add a single element at a time in the stack, can get only a single element out of the stack, and can access the topmost element of the stack.

Stack works on the LIFO property which stands for Last in First Out and means the element which is added in last will leave the stack first and then the second last element, and so on.

A stack in Javascript is implemented using another linear data structure array. We can maintain an array and a variable pointing to the last position of the array and by using it Javascript stack operations can be performed easily. We will see the detailed implementation in the upcoming sections.

Prerequisites

To implement a stack in Javascript we need some basic knowledge of variables in Javascript to iterate over the array and the arrays themselves to know how to work with the arrays. To add the operations of the stack basic knowledge of the functions is also required to pass the variables to the function and get the return value from the functions. We need to wrap up all the functions, and variables to iterate over the array, and array in a single item we can use classes in Javascript.

• To learn about the variables please go through Variables in Javascript
• To learn about the function in Javascript, follow this article: Functions in Javascript
• To learn about arrays in Javascript, follow the article: Arrays in Javascript.
• To learn about the classes in Javascript, follow the article: Classes in Javascript

Now let's move to the implementation of the stack in Javascript:

Implementation of the Following Operations in a Stack In Javascript

Before the implementation of the given following operations first, we will create a class to define the constructor and array in it.

Explanation:

In the above code, first, we have created a class using the class keyword. In the constructor of the class using the this keyword initialized an array.

Push

Push operation is used to add a new element to the stack. As the stack works on the Last in First Out property we will add the element at a place where it is easy to remove it if it is last in the array. For this purpose, we will add the new element at the last of the array by using the push() method of the javascript array as we are using the array to store the elements.

Explanation:

In the above code, first, we have created a class function push that will take a single element as a parameter. In the function, the element passed as the parameter will be added to the array at the last position using the array push method. Also, the push function will not return any value.

Time and Space Complexity

The time complexity of the push function is $O(1)$ because we are adding only a single element at the end of the array. But, if we want to make the complete stack then we have to make N operations (where N is the number of elements to push in the stack) and make the time complexity of the operation equal to $O(N)$. The space complexity for the push function is $O(1)$ because we are adding only a single element. But, the space complexity for creating a stack of N size is $O(N)$ (where N is the number of elements pushed in the stack) because N elements will take N memory positions.

Pop()

Pop operation is used to remove the element from the stack. As the element which is added in the last is present at the last in the array, we will pop the last element of the array. Also, we will return the popped element as the return value of the function.

Explanation:

In the above code, first, we have created a class function pop that will take zero parameters. In the function, we will check whether the stack is empty or not using the length method of the array. If the array is empty then we will print the "stack is empty" and return nothing, which is equivalent to undefined, otherwise, we will delete the last element of the array by using the array pop method, which will delete the last element as well as return it.

Time and Space Complexity

The time complexity of the pop function is $O(1)$ because we are removing only a single element from the end of the array. But, if we want to make the complete stack empty we have to make N operations (where N is the number of elements to pop from the stack) and make the time complexity of the operations equal to $O(N)$.

For the pop operation, we are not using any extra space and we are deleting elements from the array.

Peek()

The peek operation is also known as the top() operation, because the stack, in general, is seen as the vertical stack of the elements and the peek element, will be present on the top. But, in our implementation, the new element is present at the end. The main purpose of the peek() operation is they provide information about the last added element in the stack.

Explanation:

In the above code, first, we have created a class function peek which will take zero parameters. In the function, we will check whether the stack is empty or not using the length method of the array. If the array is empty then we will print the "stack is empty" and return nothing, which is equivalent to undefined, otherwise, we will return the last element of the array using the array.length method.

Time and Space Complexity

The time complexity of the peek() operations is $O(1)$ because we are just reading the topmost element from the array. The space complexity of the peek() operation is $O(1)$ because we are just returning a single variable.

Helper Methods

We have seen the main methods or functions of the stack which are the basic operations of the stack or the main building blocks of the stack. Now we will create some helper functions which make our work easy. Let's move to some helper functions:

isEmpty()

As we have seen in the pop() and peek() operations that there may be an error if the size of the stack is zero or there is no element present in the array. To escape from this case we can define a method that will tell whether the stack is empty or not.

Explanation:

In the above code, first, we checked whether the length of the array is zero or not. If the length of the array is zero means there is no element present in the array or stack so we will return true otherwise, we will return false as there are some elements present in the stack. This method helps us to deal with the edges cases which occur due to operation on the undefined element if the stack is empty and we will get the peek element it may affect our code.

Time and Space Complexity

The time complexity for the isEmpty() operations is $O(1)$ because we are just checking the length of the array and returning it. Similarly, the space complexity of the isEmpty() function is the same $O(1)$, which is only for the returning variable.

printStack()

If we want to print all the elements present in the stack at once then we can use this method, as it prints all the remaining elements present in the stack with a single call.

Explanation:

In the above code, we have traversed over the stack or the array from the last element to the first element to follow the property of the LIFO and using the for loop we have printed each element.

Time and Space Complexity

The time complexity for the printStack() operations is $O(N)$ (where N is the number of elements present in the Stack) because we are traversing all the stack elements once. The space complexity of the printStack() function is the $O(1)$ because we are using extra memory only for the variable used to traverse the array.

Example - Reverse a String Using a JavaScript Stack

As we have discussed in the article the stack works on the LIFO property and the element which is added in the last will be popped out first. This gives us a plus point when we have to reverse an array or a string. We can add characters of the string in the stack from the starting to end one by one and when the string got iterated we can take them out one by one and store them in another string. As the last element of the string is added, at last, it will come out first and will be added at the first position of the new string, and this way, we can rotate the string. Let’s see the complete code and understand this concept by implementation in Javascript:

Output:

Explanation:

In the above code, first, we have created a stack class in which we have added all the functions defined above. Then we have to create a string to reverse it and created an object of the stack class to store the string in it. We traversed over the string and added each element to the stack. We have created another variable to store the reversed string in it and by using the while loop with the terminating condition stack is empty or not. In the while loop, we have popped the elements of the stack, and the value returned by the stack at each pop() operation is stored in the string variable. At last, we have printed the string variable which contains the reversed string using the console method of javascript.

Time and Space Complexity

The time and space complexity for the above example are $O(N)$ because we are storing N elements or characters of the string in the stack and for that, we are traversing over them.