Definition 1.

A stack is an ordered collection that follows LIFO. Add or remove elements from the top of the stack. Stacks in real life: a stack of books or stacked plates, etc.

2. Implement Stack — based on arrays

class StackArray { constructor() { this.items = []; } push(element) { this.items.push(element); } pop() { return this.items.pop(); } peek() { return this.items[this.items.length - 1]; } isEmpty() { return this.items.length === 0; } size() { return this.items.length; } clear() { this.items = []; } toString() { return this.items.toString(); }}Copy the code

3. Implement Stack — object based

class Stack { constructor() { this.count = 0; this.items = {}; } push(element) { this.items[this.count] = element; this.count++; } pop() { if (this.isEmpty()) { return undefined; } this.count--; const result = this.items[this.count]; delete this.items[this.count]; return result; } peek() { if (this.isEmpty()) { return undefined; } return this.items[this.count - 1]; } isEmpty() { return this.count === 0; } size() { return this.count; } clear() { this.items = {}; this.count = 0; } toString() { if (this.isEmpty()) { return ''; } let objString = `${this.items[0]}`; for (let i = 1; i < this.count; i++) { objString = `${objString},${this.items[i]}`; } return objString; }}Copy the code

4. Stack application

(1) Decimal to binary

function decimalToBinary(decNumber) { const remStack = new Stack(); let number = decNumber; let rem; let binaryString = ''; while (number > 0) { rem = Math.floor(number % 2); remStack.push(rem); number = Math.floor(number / 2); } while (! remStack.isEmpty()) { binaryString += remStack.pop().toString(); } return binaryString; } console.log(decimalToBinary(233)); //11101001 console.log(decimalToBinary(10)); //1010 console.log(decimalToBinary(1000)); / / 1111101000Copy the code

(2) Balance the parentheses

function parenthesesChecker(symbols) { const stack = new Stack(); const opens = '([{'; const closers = ')]}'; let balanced = true; let index = 0; let symbol; let top; while (index < symbols.length && balanced) { symbol = symbols[index]; if (opens.indexOf(symbol) >= 0) { stack.push(symbol); } else if (stack.isEmpty()) { balanced = false; } else { top = stack.pop(); if (! (opens.indexOf(top) === closers.indexOf(symbol))) { balanced = false; } } index++; } return balanced && stack.isEmpty(); } console.log(parenthesesChecker('{([])}')); //true console.log(parenthesesChecker('{{([][])}()}')); //true console.log(parenthesesChecker('[{()]')); //falseCopy the code

(3) the Hanoi

function towerOfHanoi(plates, source, helper, dest, sourceName, helperName, destName, moves = []) {
  if (plates <= 0) {
    return moves;
  }
  if (plates === 1) {
    dest.push(source.pop());
    const move = {};
    move[sourceName] = source.toString();
    move[helperName] = helper.toString();
    move[destName] = dest.toString();
    moves.push(move);
  } else {
    towerOfHanoi(plates - 1, source, dest, helper, sourceName, destName, helperName, moves);
    dest.push(source.pop());
    const move = {};
    move[sourceName] = source.toString();
    move[helperName] = helper.toString();
    move[destName] = dest.toString();
    moves.push(move);
    towerOfHanoi(plates - 1, helper, source, dest, helperName, sourceName, destName, moves);
  }
  return moves;
}

function hanoiStack(plates) {
  const source = new Stack();
  const dest = new Stack();
  const helper = new Stack();

  for (let i = plates; i > 0; i--) {
    source.push(i);
  }

  return towerOfHanoi(plates, source, helper, dest, 'source', 'helper', 'dest');
}

function hanoi(plates, source, helper, dest, moves = []) {
  if (plates <= 0) {
    return moves;
  }
  if (plates === 1) {
    moves.push([source, dest]);
  } else {
    hanoi(plates - 1, source, dest, helper, moves);
    moves.push([source, dest]);
    hanoi(plates - 1, helper, source, dest, moves);
  }
  return moves;
}

console.log(hanoiStack(3));
console.log(hanoi(3, 'source', 'helper', 'dest'));
Copy the code

5. To summarize

Creating a Stack with an array is a little easier, and there are array methods to use. When using arrays, most methods are O(n) in time, and in the worst case, you need to iterate through the array to find the element you’re looking for. Arrays take up more memory space to keep their elements organized.

By using objects to store all stack elements, we can retrieve elements directly, take up less memory space, and still maintain element order and LIFO principles.