Data Structures With JavaScript: Stack and Queue

Two of the most commonly used data structures in web development are stacks and queues. Many users of the Internet, including web developers, are unaware of this amazing fact. If you are one of these developers, then prepare yourself for two enlightening examples: the undo operation of a text editor uses a stack to organize data and the event loop of a web browser, which handles events (clicks, hoovers, etc.), uses a queue to process data.

Now pause for a moment and imagine how many times we, as both a user and developer, use stacks and queues. That is amazing, right? Due to their ubiquity and similarity in design, I have decided to use them to introduce you to data structures. 

A Stack

In computer science, a stack is a linear data structure. If this statement holds marginal value to you, as it originally did with me, consider this alternative: A stack organizes data into sequential order. 

This sequential order is commonly described as a stack of dishes at a cafeteria. When a plate is added to a stack of dishes, the plate retains the order of when it was added; moreover, when a plate is added, it is pushed towards the bottom of a stack. Every time we add a new plate, the plate is pushed towards the bottom of the stack, but it also represents the top of the stack of plates. 

This process of adding plates will retain the sequential order of when each plate was added into the stack. Removing plates from a stack will also retain the sequential order of all plates. If a plate is removed from the top of a stack, every other plate in the stack will still retain the correct order in the stack. What I am describing, possibly with too many words, is how plates are added and removed at most cafeterias! 

To provide a more technical example of a stack, let us recall the undo operation of a text editor. Every time text is added to a text editor, this text is pushed into a stack. The first addition to the text editor represents the bottom of the stack; the most recent change represents the top of the stack. If a user wants to undo the most recent change, the top of the stack is removed. This process can be repeated until there are no more additions to the stack, which is a blank file!  

Operations of a Stack

Since we now have a conceptual model of a stack, let us define the two operations of a stack:

• push(data) adds data to the top of the stack
• pop() removes and returns the most recently added data

Implementation of a Stack in JavaScript

Before we start, I should mention that JavaScript has a great built-in stack (and queue) implementation: the Array type. That’s right, every JavaScript array has push() and pop() functions. So if you want to use a stack (or queue) in your production code, just use a regular JavaScript array. 

That being said, it’s still a great learning exercise to implement a stack from scratch! 

Properties of a Stack

For our implementation, we will create a constructor named Stack. Each instance of Stack will have two properties: _size and _storage.

class Stack {
  constructor() {
    this._size = 0;
    this._storage = {};
  }
}

this._storage enables each instance of Stack to have its own container for storing data; this._size reflects the number of times data was pushed to the current version of a Stack. If a new instance of Stack is created and data is pushed into its storage, then this._size will increase to 1. If data is pushed, again, into the stack, this._size will increase to 2. If data is removed from the stack, then this._size will decrease to 1. 

Methods of a Stack

We need to define methods that can add (push) and remove (pop) data from a stack. Let’s start with pushing data. 

Pushing Data to the Stack With push(data)

We have two requirements for this method: 

1. Every time we add data, we want to increment the size of our stack.
2. Every time we add data, we want to retain the order in which it was added.

push(data) {
    // assigns size as a key of storage
    // assigns data as the value of this key
    this._storage[this._size] = data;
    
    // Increases the size of our storage
    this._size++;
}

Our implementation of push(data) includes the following logic. Declare a variable named size and assign it the value of this._size++.  Assign size as a key of this._storage. And assign data as the value of a corresponding key. 

If our stack invoked push(data) five times, then the size of our stack would be 5. The first push to the stack would assign that data a key of 1 in this._storage. The fifth invocation of push(data) would assign that data a key of 5 in this._storage. We’ve just assigned order to our data!

Popping Data From the Stack With pop()

We can now push data to a stack; the next logical step is popping (removing) data from a stack. Popping data from a stack is not simply removing data; it is removing only the most recently added data. 

Here are our goals for this method: 

1. Use a stack’s current size to get the most recently added data.
2. Delete the most recently added data.
3. Decrement _this._size by one.
4. Return the most recently deleted data.
5. Return null if the stack is empty.

pop() {
  if (this._size == 0) 
    return null;
  
  let deletedData = this._storage[this._size - 1];

  delete this._storage[this._size - 1];
  this._size--;

  return deletedData;
}

pop() meets each of our five goals. First, we declare two variables: size is initialized to the size of a stack and deletedData is assigned to the data most recently added to a stack. Second, we delete the key-value pair of our most recently added data. Third, we decrement the size of a stack by 1. Fourth, we return the data that was removed from the stack.  

If we test our current implementation of pop(), we find that it works for the following use-case. If we push(data) data to a stack, the size of the stack increments by one. If we pop() data from our stack, the size of our stack decrements by one. 

However if we try to pop() before we add any data to the stack with push(), we’ll get null.

Using JavaScript Array as a Stack 

Even though we are implementing Stack from scratch in this article, it is unnecessary to write your logic to build a stack each time. A stack is already implemented in a JavaScript array. JavaScript provides two methods, push and pop in arrays to perform the same operations.

Here’s how to use JavaScript’s built-in stack:

const nums = [5, 8, 1, 4];
nums.push(6);

console.log(nums); // [5, 8, 1, 4, 6]

In the above example, nums is an array of numbers. We push in  6 using the push method.

The usage of pop operation is also similar. You call the pop method on the array, and it removes the last element of the array.

const nums = [5, 8, 1, 4];
const num = nums.pop();

console.log(num); // 4
console.log(nums); // [5, 8, 1]

From Stack to Queue

A stack is useful when we want to add data in sequential order and remove data. Based on its definition, a stack can remove only the most recently added data. What happens if we want to remove the oldest data? We want to use a data structure named queue.

Similar to a stack, a queue is a linear data structure. Unlike a stack, a queue deletes only the oldest added data.  

To help you conceptualize how this would work, let’s take a moment to use an analogy. Imagine a queue being very similar to the ticketing system of a deli. Each customer takes a ticket and is served when their number is called. The customer who takes the first ticket should be served first. 

Let’s further imagine that this ticket has the number “one” displayed on it. The next ticket has the number “two” displayed on it. The customer who takes the second ticket will be served second. (If our ticketing system operated like a stack, the customer who entered the stack first would be the last to be served!)

A more practical example of a queue is the event-loop of a web browser. As different events are being triggered, such as the click of a button, they are added to an event-loop’s queue and handled in the order they entered the queue. 

Operations of a Queue

Since we now have a conceptual model of a queue, let us define its operations. As you will notice, the operations of a queue are very similar to a stack. The difference lies in where data is removed. 

• enqueue(data) adds data to a queue. 
• dequeue() removes the oldest added data to a queue.  

Implementation of a Queue in JavaScript

Now let us write the code for a queue! Again, JavaScript arrays already implement these queue operations, but we’ll code them from scratch just for practice.

Properties of a Queue

For our implementation, we will create a constructor named Queue. We will then add three properties: _oldestIndex, _newestIndex, and _storage. The need for both _oldestIndex and _newestIndex will become clearer during the next section. 

class Queue {
  constructor() {
    this._oldestIndex = 0;
    this._newestIndex = 0;
    this._storage = {};
  }
}

Methods of a Queue

We will now create the three methods shared amongst all instances of a queue: size(), enqueue(data), and dequeue(data). I will outline the objectives for each method, reveal the code for each method, and then explain the code for each method. 

Getting the Size of the Queue With size()

size() {
  return this._newestIndex - this._oldestIndex;
}

Implementing size() might appear trivial, but it can be a bit tricky. Let me explain why: we have to track both the beginning and the end of the queue. Since we’re adding to one end, and removing from the other end, the size of our queue is the difference between them.

Think of the example of a deli again. When a customer comes in and takes a ticket from the ticketing system, the size of the queue increases by one. When a staff member calls that ticket, the size of the queue is reduced by one. In this example, the most recent number taken by a customer corresponds to the _newestIndex property, and the last number called by a staff member corresponds to the _oldestIndex property. The difference between them is the number of customers still waiting for their number to be called.

Adding Data to the Queue With enqueue(data)

For enqueue, we have two objectives:

1. Add the value to this._storage with the value of _newestIndex as the key.
2. Increment the value of _newestIndex by one.

Based on these two objectives, we will create the following implementation of enqueue(data):

enqueue(data) {
  this._storage[this._newestIndex] = data;
  this._newestIndex++;
}

As you can see, this code does just what we need it to.

That’s all the code we need for enqueue(data). Let’s now implement dequeue().

Removing Data From the Queue With dequeue() 

Here are the objectives for this method: 

1. Remove the oldest data in a queue.
2. Increment _oldestIndex by one.
3. Return null if the queue is empty.

dequeue() {
  if (this._oldestIndex == this._newestIndex)
    return null;

  let deletedData = this._storage[this._oldestIndex];
  delete this._storage[this._oldestIndex];
  this._oldestIndex++;

  return deletedData;
}

In the body of dequeue(), we declare two variables. The first variable, oldestIndex, is assigned a queue’s current value for this._oldestIndex. The second variable, deletedData, is assigned the value contained in this._storage[oldestIndex]. 

Next, we delete the oldest index in the queue. After it is deleted, we increment this._oldestIndex by 1. Finally, we return the data we just deleted. And whenever the values of oldestIndex and newestIndex are equal, the queue is empty and we return null. 

Queue Operations with Built-in Methods

Similar to the built-in Stack implementation, queues can also be used using some JavaScript methods. JavaScript provides two methods, shift and push.

You can think of the push() method as the enqueue operation which adds the provided data at the end of the array. 

Enqueue Operation Using push()

const nums = [5, 8, 1, 4];
nums.push(2, 3);

console.log(nums); //[5, 8, 1, 4, 2, 3 ]

Dequeue Operation Using shift

The shift() method removes an element from the index position 0 and returns the value, just like the dequeue method. In fact shift() works just like pop() but it removes the element from the beginning of the array.

const nums = [5, 8, 1, 4];

const num = nums.shift();

console.log(num); // 5
console.log(nums); // [8, 1, 4]

Even though the stack and queue operations can be easily done using the built-in functions, it is essential to understand the core logic behind these data structures. It helps you to strengthen your fundamentals. This is the reason behind showing the implementations from scratch.

Conclusion

In this article, we’ve explored two linear data structures: stacks and queues. A stack stores data in sequential order and removes the most recently added data; a queue stores data in sequential order but removes the oldest added data. 

If the implementation of these data structures seems trivial, remind yourself of the purpose of data structures. They aren’t designed to be overly complicated; they are designed to help us organize data. In this context, if you find yourself with data that needs to be organized in sequential order, consider using a stack or queue. 

A freelance web developer and a technical writer, Subha Chanda has a passion for learning and sharing experiences with others.