Implement a Stack Coding Interview Question | Skilled.dev
Interview Question

Implement a Stack

Course launching September 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓

With stacks, we only care about fast operations at the ends. This makes a linked list the perfect data structure to implement them.

Stacks can also be implemented using a dynamic array, but we will gain a better understanding of how it functions by maintaining the stack ourselves. When you are answering an interview question, you are totally fine to use a dynamic array as stack for simplicity.

Our linked list will be built using Node objects that stores data and points to the prev node in the stack.

We will implement a peek, pop, and push method which operate in O(1) time because our stack maintains a that references the last item.

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

class Stack {
  constructor() {
    this.last = null;
  }

  peek() {
    // get the last item of the list
  }
  push(item) {
    // add an item to the end of the list
  }
  pop() {
    // remove the last item of the list
  }
}

peek()

Peek allows us to view the last item that is at the top of the stack. We simply return the value in our last pointer.

peek() {
  return this.last;
}

push(item)

This adds an item to the end of the list. We create a new linked list node and point its prev to the item previously at the top. The previous last item would be null if this is the first item added to the list.

push(item) {
  const previousLastItem = this.last;

  this.last = new Node(item);
  this.last.prev = previousLastItem;

  return this.last;
}

pop()

This function removes the last item from the list and returns it. If the list is empty, or it is the last item in the list, the function will return null.

pop() {
  const removedItem = this.last;

  // Update `last` as long as we have items left in the stack
  if (removedItem) {
    this.last = removedItem.prev;
  }

  return removedItem;
}

Complete Stack Implementation

Putting it all together, we have the following implementation. If you want to see it in action, you can use it in this REPL.

class Stack {
  constructor() {
    this.last = null;
  }

  peek() {
    return this.last;
  }

  push(item) {
    const previousLastItem = this.last;

    this.last = new Node(item);
    this.last.prev = previousLastItem;

    return this.last;
  }

  pop() {
    const removedItem = this.last;

    // Update `last` as long as we have items left in the stack
    if (removedItem) {
      this.last = removedItem.prev;
    }

    return removedItem;
  }
}

Stack Built with Array

Stacks are can be implemented very simply using a dynamic array. Operations at the end of an array all happen in O(1) time, so we haven't sacrificed any Big O complexity. See the implementation in this REPL.

class Stack {
  constructor() {
    this.stack = [];
  }
  peek() {
    return this.stack[this.stack.length - 1];
  }
  push(item) {
    this.stack.push(item);
    return item;
  }
  pop() {
    return this.stack.pop();
  }
}
Prev
Stacks
Next
Max Min Stack

Table of Contents