js数据结构与算法_栈

2019-12-02 本文已影响0人 Eastboat

1.解决问题方法的效率，跟数据的组织方式是有关系的,比如图书馆借书,需要刷门禁,找书架,拿到书找管理员登记等等流程
2.解决问题方法的效率，和空间的利用率有关系 (递归打印1~100000(N), 方法一是循环，方法二是递归，结果爆掉了直接输出100000)
3.解决问题方法的效率，也和算法的巧妙运用程度有关系

数据结构+算法=程序

抽象数据类型（ATD）

1.抽象具有普适性，不会因为我之前学的是C语言，换成JAVA,PHP就不适用了。
2.抽象来源于实际，高于实际，通过从一个问题抽象出普适的理论，就可以解决其他相通的问题

JavaScript基础

操作符

算数操作符、赋值操作符、比较操作符、逻辑操作符、位操作符、一元操作符和其他操作符 typeof,delete

真值和假值

在大多数编程语言中，布尔值true和false仅仅表示true/false

function testTruthy(val){ 
 return val ? console.log('truthy') : console.log('falsy'); 
}

相等操作符

类型x | 类型y | 结果
-|-|-|-
null | undefined | true
undefined | null | true
数字 | 字符串 | x==toNumber(y)
字符串 | 数字 | toNumber(x)==y
布尔值 | 任何类型 | toNumber(x)==y
任何类型 | 布尔值 | x==toNumber(y)
字符串或数字 | 对象 | x == toPrimitive(y)
对象 | 字符串或数字 | toPrimitive(x) == y

如果x和y是相同类型，JavaScript会比较它们的值或对象值。其他没有列在这个表格中的情况都会返回false。

条件语句

循环

do...while循环和while循环很相似。区别是

//在while循环里，先进行条件判断再执行循环体中的代码，
var i = 0;
while (i < 10) {
    console.log(i);
    i++;
}


//而在do...while循环里，是先执行循环体中的代码再判断循环条件
var i = 0;
do {
    console.log(i);
    i++;
} while (i < 10)

类

function Book(title, pages, isbn){ //{1} 
 this.title = title; 
 this.pages = pages; 
 this.isbn = isbn; 
} 
Book.prototype.printTitle = function(){ 
 console.log(this.title); 
}; 

//我们可以用ES6把语法简化如下：
class Book { //{2} 
 constructor (title, pages, isbn) { 
 this.title = title; 
 this.pages = pages; 
 this.isbn = isbn; 
 } 
 printIsbn(){ 
 console.log(this.isbn); 
 } 
} 

class ITBook extends Book { //{1} 
 constructor (title, pages, isbn, technology) { 
 super(title, pages, isbn); //{2} 
   this.technology = technology; 
 } 
 printTechnology(){ 
  console.log(this.technology); 
 } 
} 
let jsBook = new ITBook('学习JS算法', '200', '1234567890', 'JavaScript'); 
console.log(jsBook.title); 
console.log(jsBook.printTechnology());

栈


/**
 * 堆栈:是具有一定操作约束的线性表，只在一端做插入和删除
 * 案例说明:日常使用的是中缀表达式，而后缀表达式是利用堆栈
 * 特点:后进先出 LIFO,新插入的元素在栈顶，旧元素接近栈底
 * 抽象描述：
 *  1. 生成空的堆栈，最大长度: createStack , maxSize
 *  2. 判断堆栈是否已满  isFull()
 *  3. 压入堆栈  push()
 *  4. 判断堆栈是否为空 isEmpty()
 *  5. 删除并返回栈顶元素  Pop()
 * 
 *  以下是基于ES5实现
 *
 */
function Stack() {
    let items = [];  //私有变量，多个Stack实例会创建多个items副本
    this.size = function () {
        return items.length;
    }
    this.push = function (element) {  //向栈添加元素
        items.push(element);
    },
        this.pop = function () {  //从栈中移除元素
            return items.pop();
        },
        this.peek = function () {  //查看栈顶元素
            return items[items.length - 1];
        },
        this.isEmpty = function () {  //检查栈是否为空
            return items.length == 0;
        },
        this.clear = function () {  //清空栈
            items = []
        },
        this.print = function () {
            console.log(items.toString())
        }
}

let stack = new Stack();
console.log(stack);
stack.push('A')
stack.push('B')
stack.push('C')
stack.pop() //移除栈顶元素 C
stack.print() // A,B
console.log(`是否为空: ${stack.isEmpty()}`);  // false
console.log(`Stack的size: ${stack.size()}`);  // 2
console.log(`栈顶元素: ${stack.peek()}`);  //此时栈顶元素 B

ES6实现的方式

//第一种方式Symbol
let _items = Symbol()  //利用symbol创建私有属性
class Stack {
    constructor() {
        this[_items] = [];
    }
    push(element) {
         this[_items].push(element)
    }
    pop(){
        this[_items].pop()
    }
    isEmpty(){
        return this[_items].length===0
    }
}

//第二种方式利用weakMap
let Stack = (function() {
  const items = new WeakMap(); //weakMap可以存储键值对，其中键是对象，值可以是任意数据类型
  class Stack {
    constructor() {
      items.set(this, []);
    }
    push(element) {
      let s = items.get(this);
      s.push(element);
    }
    pop() {
      let s = items.get(this);
      let r = s.pop();
      return r;
    }
    isEmpty() {
      return items.get(this).length === 0;
    }
    print() {
      console.log(items.get(this));
    }
  }
  return Stack; //返回类的一个实例
})();

案例

function divideBy2(decNumber) {
  var remStack = new Stack();
  var rem = ""; //余数
  var binaryString = ""; //转成二进制后的
  while (decNumber > 0) {
    rem = Math.floor(decNumber % 2);
    remStack.push(rem);
    decNumber = Math.floor(decNumber / 2);
  }
  while (!remStack.isEmpty()) {
    binaryString += remStack.pop();
  }
  return binaryString;
}

console.log(divideBy2(100000));