10. Stacks - marinakosova/master-the-coding-interview GitHub Wiki

#Stacks Introduction

A stack is a data structure which contains an ordered set of data.

Stacks provide three methods for interaction:

• Push - adds data to the “top” of the stack
• Pop - returns and removes data from the “top” of the stack
• Peek - returns data from the “top” of the stack without removing it
• Stacks mimic a physical “stack” of objects. Consider a set of gym weights.

Each plate has a weight (the data). The first plate you add, or push, onto the floor is both the bottom and top of the stack. Each weight added becomes the new top of the stack.

At any point, the only weight you can remove, or pop, from the stack is the top one. You can peek and read the top weight without removing it from the stack.

The last plate that you put down becomes the first, and only, one that you can access. This is a Last In, First Out or LIFO structure. A less frequently used term is First In, Last Out, or FILO.

Stack implementation (from Codecademy)

// NODE CLASS
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }

  setNextNode(node) {
    if (!(node instanceof Node)) {
      throw new Error('Next node must be a member of the Node class');
    }
    this.next = node;
  }

  setNext(data) {
    this.next = data;
  }

  getNextNode() {
    return this.next;
  }
}

// LINKED LIST
class LinkedList {
  constructor() {
    this.head = null;
  }

  addToHead(value) {
    const nextNode = new Node(value);
    const currentHead = this.head;
    this.head = nextNode;
    if (currentHead) {
      this.head.setNextNode(currentHead);
    }
  }

  addToTail(value) {
    let lastNode = this.head;
    if (!lastNode) {
      this.head = new Node(value);
    } else {
      let temp = this.head;
      while (temp.getNextNode() !== null) {
        temp = temp.getNextNode();
      }
      temp.setNextNode(new Node(value));
    }
  }

  findNodeIteratively(comparator) {
    let current = this.head;

    while (current) {
      if (comparator(current.value)) {
        return current;
      }
      current = current.getNextNode();
    }
    return null;
  }

  removeHead() {
    const removedHead = this.head;
    if (!removedHead) return;

    if (removedHead.next) {
      this.head = removedHead.next;
    }
    return removedHead.data;
  }

  get size() {
    let count = 0;
    let currentNode = this.head;

    while (currentNode !== null) {
      count++;
      currentNode = currentNode.next;
    }
    return count;
  }
}

// STACK
class Stack {
  constructor(maxSize = Infinity) {
    this.stack = new LinkedList();
    this.maxSize = maxSize;
    this.size = 0;
  }

  push(value) {
    if(this.hasRoom()) {
      this.stack.addToHead(value);
    this.size++;
    } else {
      throw Error('Stack is full');
    }
  }

  pop() {
    if (!this.isEmpty()) {
      const value = this.stack.removeHead();
      this.size--;
      return value;
    }
    else {
      console.log('Stack is empty!');
    }
  }

  peek() {
    if (!this.isEmpty()) {
      return this.stack.head.data;
    } else {
      return null;
    }
  }

  hasRoom() {
    if(this.size < this.maxSize) {
      return true;
    } else {
      return false;
    }
  }

  isEmpty() {
    if(this.size === 0) {
      return true;
    } else {
      return false;
    }
  }
}

Implementation from Udemy

class Stack {
  constructor(){
    this.array = [];
  }
  peek() {
    return this.array[this.array.length-1];
  }
  push(value){
    this.array.push(value);
    return this;
  }
  pop(){
    this.array.pop();
    return this;
  }
}

const myStack = new Stack();
myStack.peek();
myStack.push('google');
myStack.push('udemy');
myStack.push('discord');
myStack.peek();
myStack.pop();
myStack.pop();
myStack.pop();


//Discord
//Udemy
//google