Data Structures: Stack

Akhila Ariyachandra - May 11 '20 - - Dev Community

This was originally posted on my blog on April 22nd, 2020. Check it out for more JavaScript and React content. 😊

Stack is a linear data structure where the elements follow a First In Last Out (FILO) order. It can also be thought as Last In First Out.

Stack Diagram

Stacks can be used for things like tracking which functions are currently running and the navigation state in a web app.

Implementing a Stack data structure

Even though we will be implementing the Stack data structure in TypeScript in this example, the basic concept can be implemented in any language.

First declare a class.

class Stack<T> {}
Enter fullscreen mode Exit fullscreen mode

Then declare a private member variable array to store the data of the stack. Making it private will stop it from being directly accessed from outside the class.

class Stack<T> {
  private _data: T[] = [];
}
Enter fullscreen mode Exit fullscreen mode

Next, we need a way to check the size of the stack. We can use a getter to access the size of the _data array.

class Stack<T> {
  // ...

  // Check the size of the stack
  get size(): number {
    return this._data.length;
  }
}
Enter fullscreen mode Exit fullscreen mode

After that we'll add a method to check whether the stack is empty or not.

class Stack<T> {
  // ...

  // Returns whether the stack is empty or not
  public isEmpty(): boolean {
    return this._data.length === 0;
  }
}
Enter fullscreen mode Exit fullscreen mode

Now we need a method to add new elements to the stack. We can use the push() method in arrays to add an element to the end of the _data array.

class Stack<T> {
  // ...

  // Adds an element to the top of the stack
  public push(element: T): T {
    this._data.push(element);

    return element;
  }
}
Enter fullscreen mode Exit fullscreen mode

Finally we will implement two methods to check the element on top of the stack. One will just check the value, peek(), and the other will remove the element from the stack and return it, pop(). Both will throw an error if they are called when the stack is empty, i.e. the length of the _data array is zero.

class Stack<T> {
  // ...

  // Returns the value of the element on top of the stack without removing it
  public peek(): T {
    if (this.isEmpty()) {
      throw new Error("Stack is empty");
    }

    return this._data[this._data.length - 1];
  }

  // Removes the topmost element of the stack and returns it
  public pop(): T {
    if (this.isEmpty()) {
      throw new Error("Stack is empty");
    }

    return this._data.pop() as T;
  }
}
Enter fullscreen mode Exit fullscreen mode

Finally your stack class should look like this.

class Stack<T> {
  private _data: T[] = [];

  // Check the size of the stack
  get size(): number {
    return this._data.length;
  }

  // Returns whether the stack is empty or not
  public isEmpty(): boolean {
    return this._data.length === 0;
  }

  // Adds an element to the top of the stack
  public push(element: T): T {
    this._data.push(element);

    return element;
  }

  // Returns the value of the element on top of the stack without removing it
  public peek(): T {
    if (this.isEmpty()) {
      throw new Error("Stack is empty");
    }

    return this._data[this._data.length - 1];
  }

  // Removes the topmost element of the stack and returns it
  public pop(): T {
    if (this.isEmpty()) {
      throw new Error("Stack is empty");
    }

    return this._data.pop() as T;
  }
}
Enter fullscreen mode Exit fullscreen mode

Below is an example on how to use the Stack class we just created. The stack can be created to hold any type of data.

const numberStack: Stack<number> = new Stack<number>();

console.log(numberStack.isEmpty()); // true
console.log(numberStack.size); // 0

numberStack.push(1);
// 1
numberStack.push(2);
// 1, 2
numberStack.push(3);
// 1, 2, 3

console.log(numberStack.isEmpty()); // false
console.log(numberStack.size); // 3

console.log(numberStack.peek()); // 3
console.log(numberStack.pop()); // 3
console.log(numberStack.pop()); // 2
console.log(numberStack.pop()); // 1

console.log(numberStack.isEmpty()); // true
console.log(numberStack.size); // 0
Enter fullscreen mode Exit fullscreen mode
. . . . . . . . . . . . . . . . . . . . .