数据结构基本知识与常见的数据结构:数组、栈、队列、链表

var arr = [];
var arr1 = new Array();

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

  // 往栈内添加一个元素
  push(ele) {
    this.items.push(ele);
  }

  // 原属出栈
  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.length = 0;
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
console.log(stack) // Stack {items: [1,2,3,4]}

console.log(stack.pop()) // 4
console.log(stack.isEmpty()) // false
console.log(stack.size()) // 3
stack.clear();
console.log(stack.isEmpty()) // true

const binary = number => {
  let stack = new Stack();
  let remainder = 0 // 余数
  let top = '';

  while(number > 0) {
    remainder = number % 2;
    stack.push(remainder);
    number = Math.floor(number / 2);
  }

  while(!stack.isEmpty()) {
    top += stack.pop();
  }

  return top;
}

console.log(binary(100)); // 1100100

function factor(n) {
  if (n === 1) return 1;
  return n * factor(n-1);
}
console.log(factor(5)) // 120

class Queue {
  constructor() {
    this.items = [];
  }
  // 入队
  enqueue(ele) {
    this.items.push(ele);
  }
  // 出队
  dequeue() {
    return this.items.shift();
  }
  // 查看队头
  front() {
    return this.items[0]
  }
  // 查看队尾
  rear() {
    return this.items[this.items.length-1]
  }
  // 是否为空
  isEmpty() {
    return this.items.length === 0;
  }
  // 获取长度
  size() {
    return this.items.length;
  }
  // 清空队列
  clear() {
    this.items.length = 0;
  }
}

class Node {
        constructor(element) {
          this.element = element;
          this.next = null
        }
      }
      class LinkedList {
        constructor() {
          // 链表的长度
          this.head = null;
          // 链表的长度
          this.length = 0;
        }
        // 在链表的尾部追加元素
        append(element) {
          let node = new Node(element);
          if(this.length === 0) {
            this.head = node
          }else {
            let current = this.head;
            while(current.next) {
              current = current.next;
            }
            current.next = node;
          }
          this.length += 1;
        }
        // 获取链表的头
        getHead() {
          return this.head;
        }
        toString() {
          let current = this.head;
          let linkString = '';
          while(current){
            linkString += ',' + current.element;
            current = current.next
          }
          return linkString.slice(1);
        }
        // 插入元素
        insert(element, position) {
          if(position < 0 || position > this.length) {
            return false;
          }
          let index = 0;
          let current = this.head;
          // 上一个元素
          let prev = null;
          let node = new Node(element);
          if(position === 0) {
            node.next = this.head;
            this.head = node;
          }else {
            while(index < position) {
              prev = current;
              current = current.next;
              index++;
            }
            node.next = current;
            prev.next = node;
          }
          this.length += 1;
          return true;
        }
        getPosition(position) {
          if(position < 0 || position > this.length) {
            return null
          }
          let current = this.head;
          let index = 0;
          while(index < position) {
            current = current.next;
            index++;
          }
          return current.element;
        }
        removeAt(position) {
          if(position < 0 || position >= this.length) return null;
          let current = this.head;
          let index = 0;
          let prev = null;
          if(position === 0) {
            this.head === this.head.next;
          }else {
            while(index < position) {
              prev = current
              current = current.next;
              index++;
            }
            prev.next = current.next;
          }
          this.length--;
          return current.element;
        }
      }

      const linkedList = new LinkedList();
      linkedList.append(1)
      linkedList.append(2)
      linkedList.append(3)
      console.log(linkedList);
      console.log(linkedList.removeAt(2))

function SuperType() {
  this.name = 'name';
}
SuperType.prototype.getName = function () {
  return this.name;
}
console.log(SuperType)
/**
 * 因为prototype属性是隐式的对象，所以打印出来的是函数体
 SuperType() {
  this.name = 'name';
 }
 */
//  我们可以手动的打印一下prototype属性
console.log(SuperType.prototype)

console.log(new SuperType())

// 父级函数
function SuperType() {
  this.name = 'name';
}
SuperType.prototype.getName = function () {
  return this.name;
}
// 子级函数
function SubType() {
  this.age = 100;
}
// 子级的原型对象等于父级的实例
SubType.prototype = new SuperType();
SubType.prototype.getAge = function () {
  return this.age;
}
console.log(SubType.prototype);

var a = new SubType();
console.log(a);