DEV Community

Cover image for Data Structures and Algorithms: Stacks
Farai Bvuma
Farai Bvuma

Posted on

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

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;
  }
}
Enter fullscreen mode Exit fullscreen mode

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

 constructor() {
    this.head = undefined;
    this.length = 0;
  }
Enter fullscreen mode Exit fullscreen mode

Push

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

Stack with new node

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

Adding new node to stack

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

Updating head of 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++;
Enter fullscreen mode Exit fullscreen mode

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

    if (!this.head) {
      this.head = newNode;
      return;
    }
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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.

Stack before pop operation

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

Updating head to anterior node of stack

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

Removing reference to anterior node

Pointing node to null

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;
    }
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

Peek

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

 peek() {
    return this.head.data;
  }
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)