Stack and Queue in JavaScript

Learn about two important data structures—stack and queue—and how to implement them in JavaScript.

Every time we are developing a new application, there are certain topics that we should think through first in order to achieve our goal and have a nice result. How we are going to store our data, how we are going to deal with state logic, how we should handle authentication, etc.

Probably one of the most important is how to store data. Data is an important aspect of every application. It’s how we can learn and know more about our users. They are counting on us to store their data, and we should handle this job carefully.

We can think of data structures as a nice and performative way to store data. There are different data structures, each one has a different use case, but all of them can have the same objective—that’s how to have the best performance when storing and dealing with data.

We are using data structures in every aspect of computer programming, in our software, applications, websites, CLIs, GUIs, etc. Every computer program has a data structure in it.

The nice thing about data structures is that as algorithms, data structures are not dependent on any specific language or framework. That’s why they are one of the most important concepts for a developer to know. Everyone can understand and learn about them, even people who are not developers.

Knowing how data structures work will help you to think better about your code and how to structure better solutions for your problems. Every problem has different possible solutions that we could use; not every problem is handled the same way.

Stack

Imagine that you have a stack of dinner plates to wash after you have dined with your family, and you are responsible to wash this stack of plates. How would you start it? Well, the obvious answer is: from the top.

A stack normally is a structure of sequential and ordered elements and it’s based on the principle of last in first out (LIFO). You can argue that sometimes you can remove an element from the middle of the stack without actually removing the plate from the top, and that’s a valid argument. But sometimes this solution might not work as expected. Imagine that in some situations we only have the option to remove the most recent element added to the stack.

A stack data structure follows the same principle and it’s called a LIFO data structure. LIFO means last in first out, the same way as a stack of dinner plates or other types of the stack in the real world works—the most recent element added to the stack should be the first out.

A stack data structure has two fundamental operations:

1. push—This operation is responsible for inserting or pushing a new element to the stack.
2. pop—This operation is responsible for removing the most recent element from the stack.

A stack is a linear data structure, which means that all elements are arranged in sequential order. It results that the push and pop operations can only happen at one end of the structure, in this case, the top of the stack.

Sometimes there can be more than two operations in a stack data structure. Sometimes we might use the isEmpty operation to check if the stack is empty, and the peek operation to return the top element without modifying the stack.

Now that we know about how the stack data structure works, let’s start the implementation in JavaScript.

The nice thing about working with stack data structures in JavaScript is that JavaScript already provides us the push and pop methods that we discussed. The push method adds an element to an array and the pop method removes the last element from an array.

We can start our stack by creating a new array named stack:

let stack = [];

Now we can create our push operation. This function will be responsible for receiving an element as an argument and adding this element to our stack.

const push = (item) => stack.push(item);

Now, we will create another operation called pop. This function will be responsible for removing the last element of the stack. Fundamentally it will be the last element added to the stack. Since we don’t know exactly which might be the last element of the stack, this function does not receive any argument.

const pop = () => stack.pop();

We can also implement a stack data structure in JavaScript using classes. Here’s how we can do it:

class Stack {
 constructor() {
   this.stack = [];
 }
 push(item) {
   this.stack.push(item);
 }
 pop() {
   this.stack.pop();
 }
}

Some developers like to implement stack data structures using linked lists instead of arrays in JavaScript. Although this might feel like a clever solution, the performance might not be the best one.

As Hyunjae Jun pointed out here, the performance of arrays instead of linked lists in stack data structures is better.

There are some specific cases where linked lists can perform better than arrays, but when implementing stack data structures in JavaScript, always prefer arrays. The array methods that you are going to use, push and pop, will have a time complexity of O(1), which means that they will run efficiently and will have the best performance possible.

Queue

Imagine that we have a line of people to enter a specific restaurant. The last person to get in the line will be the last person to enter the restaurant, depending on the size of the line. The first person that got into line will be the first person to enter the restaurant.

A queue is a linear structure of sequential and ordered elements, similar to a stack, with a difference that it works based on the principle of first in first out (FIFO).

A queue data structure is called a FIFO data structure: It’s a structure of sequentially ordered elements in which the first element to be removed will be the first element added to the queue.

A queue data structure has two fundamental operations:

1. enqueue—This operation is responsible for inserting or pushing a new element to the queue.
2. dequeue—This operation is responsible for removing the oldest element from the queue.

Similar to a stack, we have a linear data structure, which means that all the operations in a queue can only happen at one end of the structure, in this case, the beginning of the queue.

JavaScript is a very helpful and handy language that provides us a lot of different methods to help us to achieve better results. The nice thing about JavaScript is that we also have a method to remove the first element of an array, which is the shift array method.

The implementation of a queue in JavaScript gets very simple and powerful. We can define our queue array like the following:

let stack = [];

Now we can create our enqueue operation to add an element to our queue, exactly the same as we did with the stack example. Create a function called enqueue and pass an argument to this function, like this:

const enqueue = (item) => queue.push(item);

Now we can create the function to remove the first element of our queue. We will create a function called dequeue and this function will be responsible for removing the first element of our queue.

const dequeue = () => queue.shift();

Pretty easy, huh? But there are some hidden differences that we might not notice at first, specifically about performance.

Remember that both the push and pop methods have a time complexity of O(1)? The shift method has a time complexity of O(n).

A simple difference in the time complexity of a piece of code can make a total difference in money, costs and performance for a company. If you’re planning to work with a queue data structure, the best possible idea is to create your own queue.

function Queue() {
  this.queue = {};
  this.tail = 0;
  this.head = 0;
}

// Add an element to the end of the queue.
Queue.prototype.enqueue = function(element) {
  this.queue[this.tail++] = element;
}

// Delete the first element of the queue.
Queue.prototype.dequeue = function() {
  if (this.tail === this.head)
      return undefined

  var element = this.queue[this.head];
  delete element;
  return element;
}

Both stack and queue data structures are very flexible and easy to implement, but there are different use cases for each of them.

A stack is useful when we want to add elements inside a list into sequential order and remove the last element added. A queue is useful when we want the same behavior, but instead of removing the last added element, we want to remove the first element added to the list.

Conclusion

Data structures are a very simple and powerful concept to learn about. They can help us improve our logical thinking, the way we structure and solve problems, and how we find the best solutions for specific use cases in our modern applications. Stacks and queues are two powerful solutions that can help us organize data into sequential order depending on what result we want to achieve and have efficient and fantastic performance.