Implementing Stack and Queue in JS

Photo by Adolfo Félix on Unsplash

Stack and Queue are not built in data structure in JavaScript. So in this article, we will see how we can implement Stack and Queue using Array and Singly Linked List.

What is Stack?

Stack is a data structure in which the element added last is removed first. It follows Last In First Out (LIFO) principle.

Credit: https://giphy.com/

Implementing Stack

For Stack implementation, we will be writing below methods.

1. push(value) — This method will insert the value at one end of the Stack
2. pop() — This method will remove the value from the same end of the Stack at which it was inserted.

We will see how we can implement Stack using Array and Singly Linked List.

Using Arrays

In JavaScript, Array has some built-in methods which we can utilise to implement Stack.

1. Use push(value) and pop() method for inserting and deleting respectively at the end of the Stack.
2. Use unshift(value) and shift() method for inserting and deleting from the beginning of the Stack .

Note: As unshift() and shift() method will insert and delete in the beginning of the Stack so they require entire array to be reindexed. Hence it’s not a good approach.

Using Singly Linked List

Like arrays, there are also two ways to implement Stack using Linked List.

One way is to insert and remove from the end. But while removing from the end, we will have to traverse the entire list to get to the second last element to set its next to null. Hence this operation is going to have O(n) complexity.

Other way is to insert and remove at the beginning which we will be implementing here. Both insertion and deletion will have O(1) complexity.

Every time we push some value to the Stack, we have to create a Node. Below is the Node Class for creating the Node.

Now we will implement the Stack Class with push(value) and pop() methods.

What is Queue?

Queue is a data structure in which the element which is added first is removed first. It follows First In First Out (FIFO) principle.

Credit: https://giphy.com/

Implementing Queue

For Queue implementation, we will be writing below methods.

1. enqueue(value) — This method will insert the value at one end of the Queue
2. dequeue() — This method will remove the value from the other end of the Queue.

Using Arrays

1. Use unshift(value) method to insert in the beginning and pop() method to delete from the end.
2. Use push(value) method to insert in the end and shift() method to delete from the beginning .

Both the approaches uses shift() or unshift(value) method hence using Arrays for implementing Queue is not a good approach.

Using Singly Linked List

As mentioned above, removing item from the end in the Singly Linked List gives O(n) complexity, hence we will avoid insertion at the beginning and removal from the end.

For our implementation , we will insert at the end and remove from the beginning to have constant time complexity.

Now we will be implementing the Queue Class with enqueue(value) and dequeue() methods.

Let’s Summarise !!

• Stack is LIFO data structure while Queue is FIFO data structure.
• For implementing Stack in constant time, we can use Array’s push(value) /pop() method for insertion/deletion or we can use Linked List to insert and remove at the beginning.
• For implementing Queue in constant time, we can use Linked List to insert at the end and remove from the beginning.

Please find the complete source code here. For any queries or suggestions related to content improvement of this article, please leave a comment.

Happy Learning !!!

Credit: https://giphy.com/