Implementing JavaScript Stack

What is stack data structure?

A stack is a data structure that holds a list of elements. A stack works based on the LIFO principle (Last In, First Out), meaning that the most recently added element is the first one to remove.

A stack has two main operations that occur only at the top of the stack: push and pop. The push operation places an element at the top of the stack whereas the pop operation removes an element from the top of the stack.

For better understanding, you may think of a stack as a set of physical items (deck of cards, books) stacked on top of each other with only one limitation: you can only put or take items from the top.

📝 JavaScript has a mechanism for an interpreter to keep track of its place in a script that calls multiple functions — what function is currently being run and what functions are called from within that function. It is called Call Stack, which implements all of the stack principles (Whenever we invoke a function, it is automatically added to the top of Call Stack. Once the function has executed all of its code, it is automatically removed from the top of Call Stack)

Let’s implement our own stack 👨‍💻

We will start by creating our Stack class

class Stack {
    constructor() {
        this.stackItems = [];
    }
}

Our Stack class will have the following methods:

• push(item) - will add an item to the top of the stack
• pop - removes an element from the stack, if the function is called on an empty stack it indicates “Underflow”
• peek - returns the topmost element in the stack without removing it from the stack
• isEmpty - check whether the stack is empty
• print - returns all of the stack items

class Stack {
    constructor() {
        this.stackItems = [];
    }

    push(item) {
        this.stackItems.push(item);
    }

    pop() {
        if (this.stackItems.length === 0) {
            return "Underflow";
        }
        return this.stackItems.pop();
    }

    peek() {
        return this.stackItems[this.stackItems.length - 1];
    }

    isEmpty() {
        return this.stackItems.length === 0;
    }

    print() {
        return this.stackItems.join(', ');
    }
}

Bonus: using stack for ‘undo’ option

We’ve implemented our own stack. Now we can use it for such thing as undo option.

📝 There’s 2 common ways of implementing undo method (as well as redo): Memento Pattern and Command Pattern.

In this article we will use the Memento Pattern.

Before an action is applied, you take a snapshot of the current state and save it into an array. That snapshot is the Memento.

If the user wants to undo, you simply pop the last memento and apply it. The program returns to the state it was before the last action was applied.

This pattern is limited in terms of efficiency. Each memento is relatively large since it captures the whole current state, but it is fine for demonstration purposes.

Input with undo option React implementation

import * as React from "react";

import { Stack } from "./utils/stack";

export const BufferedInput = () => {
  const [value, setValue] = React.useState("");

  const snapshots = React.useRef(new Stack());

  React.useEffect(() => {
    snapshots.current.push(value);
  }, [value]);

  const handleChange = (e) => {
    setValue(e.target.value);
  };

  const undo = () => {
    const previousSnapshot = snapshots.current.pop();
    setValue(previousSnapshot);
  };

  return (
    <div>
      <input type="text" value={value} onChange={handleChange} />
      <button onClick={undo}>Undo</button>
    </div>
  );
};

This implementation makes a snapshot of the input value on each key press, which might be not so useful and user friendly, so lets update this using debounce technique:

import * as React from "react";
import debounce from "lodash/debounce";

import { Stack } from "./utils/stack";

export const BufferedInput = () => {
  const [value, setValue] = React.useState("");
  const [debouncedState, setDebouncedState] = React.useState("");

  const snapshots = React.useRef(new Stack());

  React.useEffect(() => {
    snapshots.current.push(value);
  }, [debouncedState]);

  const handleChange = (e) => {
    setValue(e.target.value);
    debouncedSnapshot(e.target.value);
  };

  const debouncedSnapshot = React.useCallback(
    debounce((value) => {
      setDebouncedState(value);
    }, 500),
    []
  );

  const undo = () => {
    setValue(snapshots.current.pop());
  };

  return (
    <div>
      <input type="text" value={value} onChange={handleChange} />
      <button onClick={undo}>Undo</button>
    </div>
  );
};

Code on Sandbox

Note 💡

This code is just for demonstration and educational purpose only. I would not recommend using it in production.