Implement a stack in JavaScript
This post will discuss how to implement stack data structure in JavaScript.
A stack is a data structure that follows the principle of Last In First Out (LIFO), meaning that the last element that is added to the stack is the first one that is removed. A stack can be implemented in JavaScript using different functions, such as using an array, a linked list, or a class. Here are some examples of how to implement a stack in JavaScript:
1. Using an array
An array is a built-in data structure in JavaScript that can store multiple values of any type. It is a collection of ordered and indexed elements. We can use an array to store the elements of the stack and use the array functions push() and pop() to add and remove elements from the end of the array, which corresponds to the top of the stack. Here’s an example of how we can achieve this:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Create a stack using an array let stack = []; // Push some elements to the stack stack.push(1); stack.push(2); stack.push(3); // Pop an element from the stack let top = stack.pop(); // Log the stack and the popped element console.log(stack); // [1, 2] console.log(top); // 3 |
2. Using an object
An object is another built-in data structure in JavaScript that can store key-value pairs of any type. An object can be used to implement a stack by using a property to store the size of the stack, and another property to store the elements as a nested object. For instance:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
// Create a stack using object let stack = { size: 0, // store the size of the stack storage: {} // store the elements as a nested object }; // define a function to add an element to the stack stack.push = function(value) { // store the value at the current size this.storage[this.size] = value; // increment the size this.size++; }; // define a function to remove an element from the stack stack.pop = function() { // check if the stack is not empty if (this.size > 0) { // decrement the size this.size--; // store the value at the current size let result = this.storage[this.size]; // delete the value from the nested object delete this.storage[this.size]; // return the value return result; } }; // Push some elements to the stack stack.push(1); stack.push(2); stack.push(3); console.log(stack); // { size: 3, storage: { '0': 1, '1': 2, '2': 3 }} console.log(stack.pop()); // 3 console.log(stack); // { size: 2, storage: { '0': 1, '1': 2 } } |
3. Using a class
A class is a syntactic sugar in JavaScript that allows us to create objects with predefined properties and functions. A class can be used to implement a stack by using a constructor to initialize an array or an object as a backing store, and defining functions to add and remove elements from the stack. For instance:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
class Stack { constructor() { // create an empty array as a backing store this.items = []; } // define a function to add an element to the stack push(element) { // use the array push function this.items.push(element); } // define a function to remove an element from the stack pop() { // check if the stack is not empty if (this.items.length > 0) { // use the array pop function return this.items.pop(); } } } // create an instance of Stack class let stack = new Stack(); // Push some elements to the stack stack.push(1); stack.push(2); stack.push(3); console.log(stack.items); // [1, 2, 3] console.log(stack.pop()); // 3 console.log(stack.items); // [1, 2] |
4. Using a linked list
A linked list is a collection of nodes that are connected by pointers. We can use a linked list to store the elements of the stack and use a head pointer to keep track of the top of the stack. We can then add and remove nodes from the head of the list, which corresponds to the top of the stack. Here’s an example of how we can achieve this:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
// Define a class for a node class Node { constructor(value, next = null) { this.value = value; this.next = next; } } // Define a class for a stack using a linked list class Stack { constructor() { this.head = null; this.size = 0; } // Push an element to the top of the stack push(value) { // Create a new node with the value let node = new Node(value); // Link the node to the current head node.next = this.head; // Make the node the new head this.head = node; // Increment the size this.size++; } // Pop an element from the top of the stack pop() { // Check if the stack is empty if (this.head === null) { return null; } // Store the value of the current head let value = this.head.value; // Move the head pointer to the next node this.head = this.head.next; // Decrement the size this.size--; // Return the value return value; } } // Create a stack using a linked list let stack = new Stack(); // Push some elements to the stack stack.push(1); stack.push(2); stack.push(3); // Pop an element from the stack let top = stack.pop(); // Log the size and the popped element console.log(stack.size); // 2 console.log(top); // 3 |
5. Using mnemonist library
Finally, we can use third-party library such as mnemonist that provides the stack functionality. The mnemonist library offer various functions and options for creating and manipulating queues, such as push, pop, peek, etc. Here’s an example of its usage:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// import stack from mnemonist let Stack = require("mnemonist/stack"); // create an empty stack let stack = new Stack(); // Push some elements to the stack stack.push(1); stack.push(2); stack.push(3); console.log(stack); // [3, 2, 1] console.log(stack.pop()); // 3 console.log(stack.peek()); // 2 console.log(stack); // [2, 1] |
We can find more information and examples about this library here.
That’s all about implementing stack data structure in JavaScript.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)