Data Structures and Algorithms: Stacks

Introduction

Stacks are the next data structure that we are going to discuss. A stack is a singly linked list in which you can only add or remove nodes from the Head. Stacks follow the Last In First Out(LIFO) principle. It could be useful to think of a stack of plates, where you can only add or remove plates from the top.

Stack Methods in JavaScript

There are three methods associated with stacks, namely Push, Pop and Peek. Similar to what we did with queues, we can get started by creating a node class:

class Node {
  constructor(data) {
    this.data = data;
    this.previous = null;
  }
}

Then we can create a Stack class with the following constructor:

 constructor() {
    this.head = undefined;
    this.length = 0;
  }

Push

The Push method is used to add new nodes to the Head of the stack.

To do this, first we must point the new node to the Head of the stack.

Next, we must update the new node as the Head of the stack.

To do this in JavaScript, we can create the new node and increment the length property as necessary:

    const newNode = new Node(data);

    this.length++;

Next we check for a Head, making the new node the Head if it does not exist.

    if (!this.head) {
      this.head = newNode;
      return;
    }

Finally we point the new node to the previous Head, and make the new node the Head for the stack.

    newNode.previous = this.head;
    this.head = newNode;

Pop

The Pop method is used to remove nodes from the Head of stack. To start off, we must save a reference to the current Head of the stack.

Next, we update the Head to the anterior node in the stack.

Lastly, we point the previous Head to null, thus removing it from the stack.

To do this in JavaScript, we can start off by setting up a counter to decrease the Stack's length value, but never letting it go below zero.

this.length = Math.max(0, this.length - 1);

Next we check if the stack is empty, pointing the Head to null if necessary.

    if (this.length === 0) {
      const head = this.head;
      this.head = undefined;
      return head.data;
    }

Now we save a reference to the current Head node before making the anterior node the Head of the stack and then pointing the previous Head node to null, thus removing it from the stack:

    const head = this.head;
    this.head = head.previous;

    head.previous = undefined;

Peek

The Peek method is used to view the node that is at the Head of the stack.

 peek() {
    return this.head.data;
  }

Conclusion

With this we have covered the basics of stacks using JavaScript. Just like with queues, this can also be done in JavaScript using arrays and their inbuilt methods.