耿直咸鱼

的45°人生

0%

Posted on Edited on In Symbols count in article: 1.7k Reading time ≈ 2 mins.

题目来源于某次蔚来笔试~

本渣只能想到这一种方法！感觉好暴力啊！截至目前还没有想到更好的方法呜呜~但是这种方法是可以做的！

题目描述

有两个矩阵，矩阵1（m×m），矩阵2（n×n），判断矩阵2是不是矩阵1的子矩阵，若是输出Yes，若不是输出No

示例

1
2
3
4
5
6
7
8
9
10
11
12
const m1 = [
    ['#', '.', '#'],
    ['.', '#', '.'],
    ['#', '.', '#']
]

const m2 = [
    ['#', '.'],
    ['.', '#']
]

// 输出 'Yes'

解题思路

  • 设两个指针i和j，用于遍历m1，找到m1[i][j] === m2[0][0]

  • 设置指针a和b，用于遍历m2，同时i+a和j+b继续遍历m1

    • 设置边界
      • i+a >= m1.length || j+b >= m2.length 返回false
      • m1[i+a][j+b] !== m2[a][b] 返回false
    • 满足条件
      • a === m2.length -1 && b === m2.length -1， 返回true

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function fn(matrix1, matrix2) {
    const m = matrix1.length, n= matrix2.length;
    // 用于判断是否存在符合的情况
    let flag = false;    // 初始条件为false
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix1[i][j] === matrix2[0][0]) {
                if (dfs(i, j)) flag = true;  // 只要有一次满足，就可以~
            }
        }
    }
    return flag ? 'Yes' : 'No'; // 只要有一次满足，就为true，如果一次都没满足，就是false
    
    
    function dfs(i, j) {
        for (let a = 0; a < n; a++) {
            for (let b = 0; b < n; b++) {
                if (i+a >= n || j+b >= n || matrix1[i+a][j+b] !== matrix2[a][b]) return false;
            }
        }
        return true;
    }
}

测试一下~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// eg1
const m1 = [
    ['#', '.', '#'],
    ['.', '#', '.'],
    ['#', '.', '#']
]

const m2 = [
    ['#', '.'],
    ['.', '#']
]

console.log(fn(m1, m2)) // 'Yes'

// eg2
const m1 = [
    ['#', '.', '#'],
    ['.', '#', '.'],
    ['#', '.', '#']
]

const m2 = [
    ['#', '.'],
    ['#', '#']
]

console.log(fn(m1, m2))  // No

Posted on Edited on In , , Symbols count in article: 1.4k Reading time ≈ 1 mins.

题目描述

实现mergePromise函数，把传进去的数组按顺序先后执行，并且把返回的数据先后放到数据data里面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const time = (timer) => {
    return new Promise(resolve => {
        setTimeout(() => {
            resolve();
        }, timer);
    })
};

const ajax1 = () => time(2000).then(() => {
    console.log(1);
    return 1;
})

const ajax2 = () => time(1000).then(() => {
    console.log(2);
    return 2;
})


const ajax3 = () => time(1000).then(() => {
    console.log(3);
    return 3;
})

function mergePromise(promises) {
    // code in here

}


mergePromise([ajax1, ajax2, ajax3]).then(data => {
    console.log('done');
    console.log('data:', data); // data: [1,2,3]
})

思路分析

这里要按照顺序执行，也就是执行1-2-3这样的顺序，但是1-2-3都用了setTimeout并且时间是不一致的，如果按照普通的思路，那么2-3会在1之前去执行，这样显然是不对的

  • 可以在执行ajax函数之前包装一个promise实例，让ajax在then里面执行

  • 定义一个数组data用于保存所有的结果

  • mergePromise一定返回一个promise实例

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function mergePromise(ajaxArray) {
    // promises = [ajax1, ajax2, ajax3];
    // 存放结果
    let data = [];
    let promise = Promise.resolve();
    ajaxArray.forEach(ajax => {
        // 第一次then是为了调用ajax函数
        // 第二次then是为了获取结果
        promise = promise.then(ajax).then(res => {
            data.push(res);
            return data;
        })
    });
    return promise;
}

/*
	promise执行结果如下
	初始化：
	Promise {<fulfilled>: undefined}
	第一次：
	Promise {<fulfilled>: [1]}
	第二次：
	Promise {<fulfilled>: [1，2]}
	第三次：
	Promise {<fulfilled>: [1，2，3]}
*/

// 执行结果为：
/*
	1
    2
    3
    done
    data: [ 1, 2, 3 ]
*/

Posted on In Symbols count in article: 2.5k Reading time ≈ 2 mins.

forEach和await我们都不陌生

其中，forEach是JS中Array的API，用于遍历数组中的元素，并且可以传入一个回调函数去修改数组中的每一项，特点是没有返回值【不能用return，也不能用break跳出循环】，且会修改原数组

await是异步函数async/await发挥主要作用的标识符，用于阻塞代码的执行，实现异步效果

那么，forEach遇上await会擦出怎样的火花呢？

问题描述

看下面的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function getNumber() {
    return Promise.resolve([1,2,3]);  
    
    // 返回结果为一个Promise实例
    /*
        Promise {<fulfilled>: [1,2,3]};
    */
}


function multi(num) {
    return new Promise((resolve, reject) => {
        setTimeout(() => {
            if (num) {
                resolve(num * num);
            } else {
                reject(new Error('num not specified'));
            }
        }, 1000);
    })
}


async function test() {
    let nums = await getNumber();  // await解包：如果表达式是 promise 对象, await 返回的是 promise 成功的值
    // nums是一个数组[1,2,3]
    nums.forEach(async item => {
        let res = await multi(item);
        console.log(res);
    })
}

test();

我们期望的打印结果是：

1
2
3
4
5
6
// 1秒后
// 1
// 1秒后
// 4
// 1秒后
// 9

实际的打印结果是：

1
2
3
4
// 1秒后
// 1 
// 4
// 9

说明，forEach里面的回调函数并没有异步执行，而是同步执行的

分析问题

在上面这个例子中，我们给forEach的回调函数套上了async/await，使其具有异步函数的功能，我们期望其可以串行执行函数，但实际却是并行执行了

forEach 的 polyfill 参考：MDN-Array.prototype.forEach()，可以帮助我们理解：

1
2
3
4
5
6
7
Array.prototype.forEach = function(cb) {
    // this指代调用forEach的array
    for (let index = 0; i < this.length; i++) {
        // 回调函数的三个参数：index，item，array
        cb(index, this[index], this);
    }
}

从上面的代码可以得知，forEach只是简单地执行了回调函数而已，而不会去处理异步的情况

test函数可以修改为等价的代码，如下所示：

1
2
3
4
5
6
7
8
9
async function test() {
    let nums = await getNumber();   // nums为 [1,2,3]
 	
    for (let i = 0; i < nums.length; i++) {
        (async item => {
            let res = await multi(item);
            console.log(res);
        })(nums[i]);
}

从以上代码可以得知：forEach中异步函数是并行执行，导致了一次性全部输出结果：1，4，9

解决办法

方式一：for循环

通过改造forEach，确保每一个异步的回调执行之后再去执行下一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
async function asyncForEach(array, cb) {
    for (let i = 0; i < array.length; i++) {
        await cb(array[i], i, array);
    }
}

async function test() {
    let nums = await getNumber();   // nums为 [1,2,3]
    
    asyncForEach(nums, async item => {
        let res = await multi(item);
        console.log(res);
    })
}

方式二：for…of

for…of用于遍历可迭代对象，先调用可迭代对象的迭代器方法[Symbol.iterator]()方法，该方法返回一个迭代器对象，对象内部包含next()方法，然后调用迭代器对象上的next方法

1
2
3
4
5
6
7
8
async function test() {
    let nums = await getNumber();   // nums为 [1,2,3]
    
    for (let num of nums) {
        let res = await multi(num);
        console.log(res);
    }
}

上述代码等价于下列代码：

1
2
3
4
5
6
7
8
9
10
11
12
async function test() {
    let nums = await getNumber();   // nums为 [1,2,3]
    let iterator = nums[Symbol.iterator]();   
    let objIterator = iterator.next();   // {value: xxx, done: true || false}

    while (!objIterator.done) {
        let num = objIterator.value;
        let res = await multi(num);
        console.log(res);
        objIterator = iterator.next();  
    }
}

参考

当 async/await 遇上 forEach

MDN-Array.prototype.forEach()

Posted on In , Symbols count in article: 2.9k Reading time ≈ 3 mins.

cookie用于客户端存储会话信息

服务器在响应HTTP请求时，通过发送Set-Cookie HTTP头部包含会话信息，value和name在发送时都会经过URL编码

1
2
3
4
HTTP/1.1 2.0 OK
Content-type: text/html
Set-Cookie: name=value
Other-header: other-hander-value

浏览器会存储这些会话信息，并在之后每一个请求中都会在HTTP请求头中包含cookie，将cooike信息发回服务器，这些信息可以作为唯一标识发送请求的服务器

1
2
3
GET /index.js HTTP/1.1
Cookie: name=value
Other-header: other-hander-value

cookie的构成

  • name：唯一标识cookie 的名称，cookie 名不区分大小写，cookie 名必须经过URL 编码

  • value：存储在cookie 里的字符串值，这个值必须经过URL 编码

  • domain：cookie 有效的域，发送到这个域的所有请求都会包含对应的cookie，值默认包含子域

  • path：请求URL 中包含这个路径才会把cookie 发送到服务器，默认包含子路径

  • expires/max-age：表示何时删除cookie 的时间戳（即什么时间之后就不发送到服务器了），默认情况下，浏览器会话结束后会删除所有cookie，不过，也可以设置删除cookie 的时间。这个值是GMT 格式（Wdy, DD-Mon-YYYY HH:MM:SS GMT），用于指定删除cookie 的具体时间，这样即使关闭浏览器cookie 也会保留在用户机器上，把过期时间设置为过去的时间会立即删除cookie

  • size：cookie大小

  • secure：设置之后，只在使用SSL 安全连接的情况下才会把cookie 发送到服务器

  • HttpOnly：HttpOnly值为 true 或 false，若设置为true，则不允许通过脚本document.cookie去更改这个值，同样这个值在document.cookie中也不可见，但在发送请求时依旧会携带此Cookie，可防止通过JavaScript访问cookie的值

  • SameSite：用来限制第三方 Cookie，从而减少安全风险，它有3个属性，分别是：

    • Strict：Scrict最为严格，完全禁止第三方Cookie，跨站点时，任何情况下都不会发送Cookie

    • Lax：Lax规则稍稍放宽，大多数情况也是不发送第三方 Cookie，但是导航到目标网址的 Get 请求除外。

    • None：网站可以选择显式关闭SameSite属性，将其设为None，不过，前提是必须同时设置Secure属性（Cookie 只能通过 HTTPS 协议发送），否则无效

  • Priority：优先级，定义了三种优先级，Low/Medium/High，当cookie数量超出时，低优先级的cookie会被优先清除

Web Storage

提出的目的是为了解决通过客户端存储不需要频繁发送回服务器的数据时使用cookie的问题

基于cookie，Web Storage提出了两个目标：

  • 提供在cookie之外的存储会话数据的目标
  • 提供跨会话持久化存储大量数据的机制

Storage类型

Storage类型用于保存名/值对数据，直到存储空间上限（浏览器决定！）

Storage在对象的基础上，增加如下方法：

  • clear()：删除所有值；不在Firefox 中实现
  • getItem(name)：取得给定name 的值
  • key(index)：取得给定数值位置的名称
  • removeItem(name)：删除给定name 的名/值对
  • setItem(name, value)：设置给定name 的值

sessionStorage对象（跨会话存储）

  • sessionStorage对象只存储会话数据，所以数据只会存储到浏览器关闭

  • 存储在sessionStorage中的数据不受页面刷新影响，可以在浏览器崩溃并重启后恢复

  • 因为sessionStorage对象与服务器会话紧密相关，所以在运行本地文件时不能使用

  • 存储在sessionStorage对象中的数据只能由最初存储数据的页面使用，在多页应用程序中的用处有限

localStorage对象（永久存储）

  • localStorage对象作为在客户端持久存储数据的机制
  • 要访问同一个localStorage对象，页面必须来自同一个域（子域不可以）、在相同的端口上使用相同的协议

存储事件

每当Storage 对象发生变化时，都会在文档上触发storage事件。使用属性或setItem()设置值、使用delete或removeItem()删除值，以及每次调用clear()时都会触发这个事件

这个事件的事件对象有如下4 个属性

  • domain：存储变化对应的域
  • key：被设置或删除的键
  • newValue：键被设置的新值，若键被删除则为null
  • oldValue：键变化之前的值

可以使用如下代码监听storage事件：

1
2
window.addEventListener("storage",
	(event) => alert('Storage changed for ${event.domain}'));

对于sessionStorage和localStorage上的任何更改都会触发storage事件，但storage件不会区分这两者

总结

三者区别

生命周期

  • cookie：可以通过设置expires/max-age来控制失效时间，没设置就默认关闭浏览器后失效
  • sessionStorage：仅在当前网页会话下有效，关闭页面或者浏览器会被清除
  • localStorage：永久保存，除非手动清除

存放数据大小

  • cookie：4kb左右
  • web Storage：5MB

http请求

  • cookie：每次发送请求的时候都会携带在http头中，如果cookie保存过多数据会带来性能问题
  • web Storage：仅在客户端中保存，不参与和服务器的通信

易用性

  • cookie：需要自己封装，包含get set等方法，详情见红宝书第四版P754页
  • web Storage：原生接口可以接受，也可以再次封装

应用场景

从安全性来说，因为每次http请求都会携带cookie信息，这样无形中浪费了带宽，所以cookie应该尽可能少的使用，另外cookie还需要指定作用域，不可以跨域调用，限制比较多

但是用来识别用户登录来说，cookie还是比stprage更好用的，其他情况下，可以使用storage，就用storage

storage在存储数据的大小上面秒杀了cookie，现在基本上很少使用cookie了

localStorage和sessionStorage唯一的差别一个是永久保存在浏览器里面，一个是关闭网页就清除了信息，localStorage可以用来夸页面传递参数，sessionStorage用来保存一些临时的数据，防止用户刷新页面之后丢失了一些参数

Posted on Edited on In Symbols count in article: 9.7k Reading time ≈ 9 mins.

什么是indexedDB

indexedDB是浏览器结构化存储的一种方式，用于代替目前已经废弃的Web SQL Database API

indexedDB是类似于MySQL或者Web SQL Database的数据库，但是**IndexDB使用对象而不是表格保存数据，因此，可以说indexedDB是在一个公共空间下的一组对象存储，类似于NoSQL风格的实现

如何使用IndexDB数据库

使用indexedDB数据库可通过如下步骤（基础）：

  • Step1：调用indexedDB.open()方法
  • Step2：对象存储
  • Step3：调用事务进行增删改查

Step1：调用indexedDB.open()方法

indexedDB.open()方法用于打开数据库（如果数据库不存在，则为创建）

参数说明

  • 要打开的数据库名称（必选）
  • 指定版本号（可选）

返回值说明

返回一个IDBRequest的实例，可以在这个实例上添加onerror和onsuccess事件处理程序，这两个事件处理程序的event.target都指向这个实例

  • 如果打开的时候发生错误，就会在event.target.errorCode中存储错误码
  • 如果打开成功，就可以通过event.target.result访问数据库
1
2
3
4
5
6
7
8
9
10
11
let db,
    request,
    version = 1;

request = indexedDB.open('admin', version);   // 打开admin这个数据库
request.onerror = (event) => {
    console.log(`Failed to open: ${event.target.errorCode}`);
};
request.onsuccess = (event) => {
    db = event.target.result;
};

Step2：对象存储

对象存储你需要准备：

  • 指定一个键，必须是全局唯一的
1
2
3
4
5
6
let user = {
    username: '007',
    firstName: 'Katrina',
    lastName: 'Ying',
    password: 'foo',
}

假设要存储这样一个对象，很显然username可以用来做主键

  • upgradeneeded事件用于监听更新数据库
1
2
3
4
5
6
7
8
9
10
request.onupgradeneeded = (event) => {
    const db = event.target.result;
    
    // 如果已经存在则删除当前的objectStore
    if (db.objectStoreNames.contains('users')) {
        db.deleteObjectStore('users');
    }
    
    db.createObjectStore('users', {keyPath: 'username'});
}

Step3：通过事务进行后序操作

在对象存储之后，剩下的所有操作都是通过事务完成的

  • 插入对象：add put
  • 删除对象：delete （键作为参数）
  • 获取对象：get（键作为参数）
  • 清空对象：clear
1. 创建事务 db.transaction()
  • 没有指定名称——数据库中所有的对象都只有只读权限
  • 访问一个或者多个数据库——传入数据库名称，单个直接传入，多个以数组的形式传入
  • 传入第二个参数以修改访问模式——readonly readwrite versionchange
1
2
3
4
5
6
7
8
9
// 没有指定名称，数据库中所有的对象都只有只读权限
let transaction = db.transaction();  

// 指定名称
let transaction = db.transaction('users');  
let transaction = db.transaction(['users', 'admin']);  

// 指定第二个参数
let transaction = db.transaction('users', 'readwrite');
2. 事务事件处理程序绑定
1
2
3
4
5
6
const transaction = db.transaction('users'),
      store = transaction.objectStore('users'),
      request = store.get('007');

request.onerror = (event) => alert("Did not get the object!");
request.onsuccess = (event) => alert(event.target.result.firstName);

因为一个事务可以完成任意多个请求，所以事务对象本身也有事件处理程序：onerror 和oncomplete，这两个事件可以用来获取事务级的状态信息

1
2
3
4
5
6
transaction.onerror = (event) => {
	// 整个事务被取消
};
transaction.oncomplete = (event) => {
	// 整个事务成功完成
};

注意，不能通过oncomplete事件处理程序的event对象访问get()请求返回的任何数据，因此，仍然需要通过这些请求的onsuccess事件处理程序来获取数据

插入数据

插入数据的方式有：

  • add（增加新值）
  • put（修改，更新）

这两个方法都接收一个参数：要存储的对象

两者的区别在于：传入对象存储已经包含同名键时，add会报错，而put是重写对象

1
2
3
for (let user of users) {
    store.add(user);
}

每次调用add()或put()都会创建对象存储的新更新请求

如果想验证请求成功与否，可以把请求对象保存到一个变量，然后为它添加onerror 和onsuccess 事件处理程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let request,
    requests = [];

for (let user of users) {
    request = store.add(user);
    
    request.onerror = () => {
        // 处理错误程序
    };
    
    request.onsuccess = () => {
        // 处理成功
    };
    
    requests.push(request);
}

通过游标查询

使用事务可以通过一个已知键取得一条记录，如果想取得多条数据，则需要在事务中创建一个游标

游标是一个指向结果集的指针

与传统数据库查询不同，游标不会事先收集所有结果，相反，游标指向第一个结果，并在接到指令前不会主动查找下一条数据

创建游标 openCursor()

可以接收两个参数：（后面讲！！！）

  • 键范围
  • 游标方向

openCursor()也返回一个请求，所以必须为它添加onsuccess和onerror事件处理程序

1
2
3
4
5
6
7
8
9
10
11
const transaction = db.transaction('users'),
      store = transaction.objectStore('users'),
      request = store.openCursor();

request.onerror = () => {
    // 处理错误程序
};
    
request.onsuccess = () => {
    // 处理成功
};

  1. 在调用onsuccess事件处理程序时，可以通过event.target.result访问对象存储中的下一条记录，这个属性中保存着IDBCursor的实例（有下一条记录时）或null（没有记录时）

    实例有如下属性：

    • direction：字符串常量，表示游标的前进方向以及是否应该遍历所有重复的值。
      • 可能的值包括：NEXT(“next”)、NEXTUNIQUE(“nextunique”)、PREV(“prev”)、PREVUNIQUE(“prevunique”)
    • key：对象的键
    • value：实际的对象
    • primaryKey：游标使用的键，可能是对象键或索引键
    1
    2
    3
    4
    5
    6
    request.onsuccess = (event) => {
        const cursor = event.target.result;
        if (cursor) {  // 永远要检查！
            console.log(`Key:${cursor.key},Value:${JSON.stringify(cursor.value)}`)
        }
    }

  2. 游标可用于更新个别记录——update()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
request.onsuccess = (event) => {
	const cursor = event.target.result;
	let value,
		updateRequest;
	if (cursor) { // 永远要检查
		if (cursor.key == "foo") {
			value = cursor.value; // 取得当前对象
			value.password = "magic!"; // 更新密码
			updateRequest = cursor.update(value); // 请求保存更新后的对象
			updateRequest.onsuccess = () => {
				// 处理成功
			};
			updateRequest.onerror = () => {
				// 处理错误
			};
	}
	}
};
  1. 可以删除游标位置的记录_delete()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
request.onsuccess = (event) => {
	const cursor = event.target.result;
	let value,
		deleteRequest;
	if (cursor) { // 永远要检查
		if (cursor.key == "foo") {
			deleteRequest = cursor.delete(); // 请求删除对象
			deleteRequest.onsuccess = () => {
				// 处理成功
			};
			deleteRequest.onerror = () => {
				// 处理错误
			};
		}
	}
};

注意：如果事务没有修改对象存储的权限，那么update和delete都会报错

游标迭代

默认情况下，每个游标只会创建一个请求

要创建另一个请求，必须调用下列中的一个方法

  • continue(key)：移动到结果集中的下一条记录，参数key 是可选的，如果没有指定key，游标就移动到下一条记录；如果指定了，则游标移动到指定的键
  • advance(count)：游标向前移动指定的count 条记录，这两个方法都会让游标重用相同的请求，因此也会重用onsuccess 和onerror 处理程序，直至不再需要
1
2
3
4
5
6
7
8
9
request.onsuccess = (event) => {
	const cursor = event.target.result;
	if (cursor) { // 永远要检查
		console.log(`Key: ${cursor.key}, Value: ${JSON.stringify(cursor.value)}`);
		cursor.continue(); // 移动到下一条记录
	} else {
		console.log("Done!");
	}
};

键范围

可以使用键范围更容易地管理游标

键范围对应IDBKeyRange的实例

有四种方式指定键范围

  • 方式1：only
1
const onlyRange = IDBKeyRange.only('007');

这个范围保证只获取键为”007”的值

使用这个范围创建的游标类似于直接访问对象存储并调用get(“007”)

  • 方式2：lowerBound

定义结果集的下限，下限表示游标开始的位置

1
const lowerRange = IDBKeyRange.lowerRange('007');   // 保证游标从"007"这个键开始
  • 方式3：upperBound

定义结果集的上限，通过调用upperBound()方法可以指定游标不会越过的记录，如果不想包含指定的键，可以在第二个参数传入true

1
2
3
4
5
// 从头开始，到"ace"记录为止
const upperRange = IDBKeyRange.upperBound("ace");

// 从头开始，到"ace"的前一条记录为止
const upperRange = IDBKeyRange.upperBound("ace", true);
  • 方式4：bound

同时指定下限和上限，这个方法接收四个参数：下限的键、上限的键、可选的布尔值表示是否跳过下限和可选的布尔值表示是否跳过上限

1
2
3
4
5
6
7
8
// 从"007"记录开始，到"ace"记录停止
const boundRange = IDBKeyRange.bound("007", "ace");
// 从"007"的下一条记录开始，到"ace"记录停止
const boundRange = IDBKeyRange.bound("007", "ace", true);
// 从"007"的下一条记录开始，到"ace"的前一条记录停止
const boundRange = IDBKeyRange.bound("007", "ace", true, true);
// 从"007"记录开始，到"ace"的前一条记录停止
const boundRange = IDBKeyRange.bound("007", "ace", false, true);

游标范围设置——传入openCursor

1
2
3
4
5
6
7
8
9
10
11
12
13
const store = db.transaction("users").objectStore("users"),
	range = IDBKeyRange.bound("007", "ace");

request = store.openCursor(range);
request.onsuccess = function(event){
	const cursor = event.target.result;
	if (cursor) { // 永远要检查
		console.log(`Key: ${cursor.key}, Value: ${JSON.stringify(cursor.value)}`);
		cursor.continue(); // 移动到下一条记录
	} else {
		console.log("Done!");
	}
};

设置游标方向

游标方向：

  • next（默认）：从第一条到最后一条，不跳过重复项
  • nextunique：从第一条到最后一条，跳过重复项
  • prev：从最后一条到第一条，不跳过重复项
  • prevunique：从最后一条到第一条，跳过重复项

索引

创建新索引 createIndex()

参数说明

  • 索引名称
  • 索引属性名称
  • 包含键unique的options对象
    • unique必须指定，表示这个键是否在所在记录里面唯一
1
2
3
const transaction = db.transaction("users"),
	store = transaction.objectStore("users"),
	index = store.createIndex("username", "username", { unique: true });

返回值说明

返回IDBIndex实例

1
2
3
const transaction = db.transaction("users"),
	store = transaction.objectStore("users"),
	index = store.index("username");  // 使用索引

  1. 可以在索引上使用openCursor()方法创建新游标，这个游标与在对象存储上调用openCursor()创建的游标完全一样，只是其result.key 属性中保存的是索引键，而不是主键

    1
    2
    3
    4
    5
    6
    7
    8
    const transaction = db.transaction("users"),
    	store = transaction.objectStore("users"),
    	index = store.index("username"),
    	request = index.openCursor();

    request.onsuccess = (event) => {
    	// 处理成功
    };

  2. 使用openKeyCursor()方法也可以在索引上创建特殊游标，只返回每条记录的主键

    这个方法接收的参数与openCursor()一样

    最大的不同在于，event.result.key 是索引键，且event.result.value是主键而不是整个记录

    1
    2
    3
    4
    5
    6
    7
    8
    9
    const transaction = db.transaction("users"),
    	store = transaction.objectStore("users"),
    	index = store.index("username"),
    	request = index.openKeyCursor();

    request.onsuccess = (event) => {
    	// 处理成功
    	// event.result.key 是索引键，event.result.value 是主键
    };

  3. 如果想只取得给定索引键的主键，可以使用getKey()方法，这样也会创建一个新请求，但result.value 等于主键而不是整个记录

    1
    2
    3
    4
    5
    6
    7
    8
    9
    const transaction = db.transaction("users"),
    	store = transaction.objectStore("users"),
    	index = store.index("username"),
    	request = index.getKey("007");

    request.onsuccess = (event) => {
    	// 处理成功
    	// event.target.result.key 是索引键，event.target.result.value 是主键
    };

    在这个onsuccess 事件处理程序中，event.target.result.value 中应该是用户ID

    任何时候，都可以使用IDBIndex 对象的下列属性取得索引的相关信息

    • name：索引的名称
    • keyPath：调用createIndex()时传入的属性路径
    • objectStore：索引对应的对象存储
    • unique：表示索引键是否唯一的布尔值

    对象存储自身也有一个indexNames 属性，保存着与之相关索引的名称

    使用如下代码可以方便地了解对象存储上已存在哪些索引

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    const transaction = db.transaction("users"),
    	store = transaction.objectStore("users"),
    	indexNames = store.indexNames

    for (let indexName in indexNames) {
    	const index = store.index(indexName);
    	console.log(`Index name: ${index.name}
    		KeyPath: ${index.keyPath}
    		Unique: ${index.unique}`);
    }

  4. 在对象存储上调用deleteIndex()方法并传入索引的名称可以删除索引

    1
    2
    3
    const transaction = db.transaction("users"),
    	store = transaction.objectStore("users"),
    	store.deleteIndex("username");

    因为删除索引不会影响对象存储中的数据，所以这个操作没有回调

并发问题

IndexedDB虽然是网页中的异步API，但仍存在并发问题

如果两个不同的浏览器标签页同时打开了同一个网页，则有可能出现一个网页尝试升级数据库而另一个尚未就绪的情形

有问题的操作是设置数据库为新版本，而版本变化只能在浏览器只有一个标签页使用数据库时才能完成

第一次打开数据库时，添加onversionchange 事件处理程序非常重要，另一个同源标签页将数据库打开到新版本时，将执行此回调，对这个事件最好的回应是立即关闭数据库，以便完成版本升级

1
2
3
4
5
6
let request, database;
request = indexedDB.open("admin", 1);
request.onsuccess = (event) => {
	database = event.target.result;
	database.onversionchange = () => database.close();
};

应该在每次成功打开数据库后都指定onversionchange事件处理程序

记住，onversionchange有可能会被其他标签页触发

通过始终都指定这些事件处理程序，可以保证Web应用程序能够更好地处理与IndexedDB相关的并发问题

限制

  • IndexedDB 数据库是与页面源（协议、域和端口）绑定的，因此信息不能跨域共享。这意味着www.wrox.com 和p2p.wrox.com 会对应不同的数据存储
  • 每个源都有可以存储的空间限制。当前Firefox 的限制是每个源50MB，而Chrome 是5MB，移动版Firefox 有5MB 限制，如果用度超出配额则会请求用户许可
  • Firefox 还有一个限制——本地文本不能访问IndexedDB 数据库，Chrome 没有这个限制。

Posted on Edited on In , , Symbols count in article: 3.2k Reading time ≈ 3 mins.

哈希表基础知识

哈希表，又叫散列表（HashTable或者HashMap），是根据键直接访问记录在存储位置的数据结构，通过哈希函数根据计算出在哈希表中的内存地址

作用是尽可能快地在数据结构中找到一个值

实现哈希表

实现方法

  • get(val)
  • put(key, val)
  • remove(key)

手写实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class ValuePair {
    constructor(key, val) {
        this.key = key;
        this.val = val;
    };
    
    toString() {
        return `[${this.key}:${this.val}]`;
    }
}

class HashTable {
    constructor(toStrFn) {
        this.table = {};
    }
    
    
    // 1. 创建哈希函数: 传入key -> 获取内存地址
    loseloseHashTable(key) {
        if (typeof key === 'number') {
            return key;
        }
        
        const tablekey = String(key);
        let hash = 0;
        for (let i = 0; i < tableKey.length; i++) {
            hash += tablekey.charCodeAt(i);
        }
        return hash % 37;  // 获取hash值
    }
    
    hashCode(key) {
        return this.loseloseHashTable(key);
    }
    
    // hashTable添加键值对
    put(key, val) {
        if (key !== null && val !== null) {
            const position = this.hashCode(key);   // position是内存地址
            this.table[position] = new ValuePair(key, val);
            return true;
        }
        return false;
    }
    
    // hashTable中获取val
    get(key) {
        const valuePair = this.table[this.hashCode(key)];
        return valuePair = valuePair ? valuePair.val : undefined;
    }
    
    
    // hashTable删除值
    remove(key) {
        const hash = this.hashCode(key);
        const valuePair = this.table[hash];
        if (valuePair) {
            // 使用delete或者设置null或者undefined是一样的
            delete this.table[hash];
            return true;
        }
        return false;
    }
}

测试一下子~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const hash = new HashTable();

hash.put('Katrina', '111.com');
hash.put('Jenny', '222.com');
hash.puth('Kate', '333.com');

console.log(hash.hashCode('Katrina') + '-Katrina');
console.log(hash.hashCode('Jenny') + '-Jenny');
console.log(hash.hashCode('Kate') + '-Kate');

/*
	11-Katrina
	35-Jenny
	19-Kate
*/

console.log(hash.get('Katrina'));   // 111.com
console.log(hash.get('Lisa'));    // undefined

hash.remove('Kate');
console.log(hash.get('Kate'));   // undefined

哈希表和哈希集合

处理哈希表中的冲突

一些键会有相同的hash值，比如hash.hashCode('Jenny')和hash.hashCode('Jisoo')都是35，一般来说，具有相同hash值的数据在hash表中值会被替换

看下面的代码：

1
2
3
4
5
6
7
8
9
const hash = new HashTable();

hash.put('Jisoo', '111.com');
hash.put('Jenny', '222.com');

console.log(hash.hashCode('Jisoo') + '-Jisoo');   // 35-Jisoo
console.log(hash.hashCode('Jenny') + '-Jenny');   // 35-Jenny

console.log(hash.get('Jisoo'));   // 222.com  显然已经被替换

处理冲突的方法有：分离链接、线性探查、双散列法

1. 分离链接

分离链接指的是为哈希表的每一个位置创建一个链表并且要将元素存储在里面

  • 重写put方法

    重写思路：验证要加入的新元素的位置是否已经被占据，如果已经占据，会创建一个NodeList实例，将ValuePair加入到这个实例

  • 重写get

    重写思路：验证能否在特定位置找到该元素，定位后，通过遍历ListNode得到元素，没有找到就返回undefined

  • 重写remove

    重写思路：类似于定位后找到链表，然后去删除链表中的节点

2. 线性探查

将元素直接存到表中，而不是在单独的数据结构中

  • 重写put

    重写思路：当向hash表存放元素的时候，若发现position已经被占据了，就存放在position+1中，如果position+1也被占据了，则存放在position+2中，以此类推…

  • 重写get

    重写思路：查找键，不存在一定是undefined，如果存在就要检查我们要找的值是不是在这个原始位置上，如果不是，就继续找，完整迭代后还是找不到返回undefined

  • 重写remove

​ 重写思路和put基本相同，不再赘述

3. 双散列法

创建更好地散列函数：1. 插入和检索元素的时间；2. 较低的冲突可能性

比lose lose哈希函数更好的函数是djb2

1
2
3
4
5
6
7
8
djb2HashCode(key) {
    const tableKey = String(key);
   	let hash = 5381;  // 初始化一个hash变量并且赋值
    for (let i = 0; i < table.length; i++) {
        hash = (hash * 33) + tableKey.charCodeAt(i);
    }
    return hash % 1013;
}

参考

代码随想录_哈希表

Posted on Edited on In , , Symbols count in article: 4.4k Reading time ≈ 4 mins.

链表基础知识

什么是链表

链表是一种通过指针串在一起的线性结构，每一个节点由两部分组成：数据域和指针域（用于存放指向下一个节点的指针），最后一个指针域指向null（空指针）

[head：链表头节点，链表入口节点]

链表的存储方式

链表不是连续分布的【区别于数组】，链表是通过指针域连接在内存中的节点，所以链表中的节点在内存中不是连续分布的，而是散乱分布在内存中的某地址上的，分配机制取决于操作系统的内存管理

链表方法

  • 创建链表
  • 插入节点
    • 末尾插入——push(val)
      • 链表为空——添加第一个元素
      • 链表不为空——追加元素
    • 任何位置插入——insert(val, position)
  • 移除元素
    • 根据位置移除——removeAt(position)
    • 根据元素值移除——remove(val)
  • 拓展
    • 查找是否存在val的节点——indexOf(val)
    • 链表是否为空——isEmpty()
    • 链表长度——size()
    • 获取链表节点值——toString()

单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
class NodeList{
    constructor(val, next) {
        this.val = val ? val : undefined;
        this.next = next ? next : null;
        this.count = 0;   // 记录节点个数，也就是链表长度
    }
    
    // 增加节点
    push(val) {
        const node = new NodeList(val, null);
        
        // 情况1：如果没有head节点
        if (!this.head) {
            this.head = node;
        } else {  // 情况2：有head节点
            let current = head;
            while (current.next) {
                current = current.next;   // 找到末尾节点
            };
            current.next = node; // 末尾指向新节点
        };
    }
    
    // 找到XX位置的node
    getElementAt(index) {
        if (index >= 0 && index < this.count) {
            let node = this.head;
            
            while (index--) {
                node = node.next;
            }
            return node;
        }
        return undefined;
    }
    
    // 移除元素
    removeAt(index) {
        // 检查index的情况
        if (index >= 0 && index < this.count) {
            if (index === 0) {
                this.head = current.next;
            } else {
                const previous = getElementAt(index -1);   // 找到前一个节点
                const current = previous.next;
                previous.next = current.next;
            }
            this.count--;
            return current.val;
        }
        return undefined;
    }
    
    // 在任意位置增加节点
    insert(val, index) {
        // 检查index的情况
        if (index >= 0 && index < this.count) {
            const node = new NodeList(val, null);
            // 如果是第一个位置
            if (index === 0) {
                const current = this.head;
                node.next = current;
                this.head = node;
            } else {
                const previous = getElementAt(index -1);   // 找到前一个节点
                node.next = previous.next;
                previous.next = node;
            }
            this.count++;
            return true;
        }
        return false;   // 没有添加元素到链表
    }    
    
    // 找到元素所在位置
    indexOf(val) {
        let current = this.head;
        for (let i = 0; i < this.count && this.count !== null; i++) {
            if (current.val === val) {
                return i;
            } else {
                current = current.next;
            }
        };
        
        return -1; // 没有找到啦~
    }
    
    // size
    size() {
        return this.count;
    }
    
    // isEmpty
    isEmpty() {
        return !this.size();
    }
    
    // toString()
    toString() {
        if (!this.head) return '';
        
        let objString = `${this.head.val}`;
        let current = this.head.next;
        while (current) {
            objString = `${objString},${current.val}`;
            current = current.next;
        };
        return objString;
    }
}

双向链表

双向链表和普通链表的区别在于：

在链表中，一个节点只有链向下一个节点的链接；而在双向链表中，链表是双向的：一个链向前一个节点，一个链向后一个节点

双向链表不用next而用prev和tail指针代替

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class DoubleNodeList {
    constructor(val, prev, tail) {
        this.val = val ? val : undefined;
        this.prev = prev ? prev : null;
        this.tail = tail ? tail : null;
        this.count++;
    }
    
    // 找到XX位置的node
    getElementAt(index) {
        if (index >= 0 && index < this.count) {
            let node = this.head;
            
            while (index--) {
                node = node.next;
            }
            return node;
        }
        return undefined;
    }
    
    // 重写insert方法
    insert(val, index) {
        if (index >= 0 && index <= this.count) {
            const node = new DoubleNodeList(val, null, null);
            let current = head;
            
            // 场景1：第一个位置
            if (index === 0) {
                if (!this.head) {
                    this.head = node;
                    this.tail = node;
                } else {
                    node.next = this.head;
                    current.prev = node;
                    this.head = node;
                }  // 场景2：末尾
            } else if (index === this.count) {
                current = this.tail;
                current.next = node;
                node.prev = current;
                this.tail = node;
            } else {  // 场景3：中间位置
                const previous = this.getElementAt(index - 1);
                current = previous.next;
                node.next = current;
                previous.next = node;
                current.prev = node;
                node.prev = previous;
            }
            this.count++;
            return true;
        }
        return false;
    }
    
    // 重写removeAt方法
    removeAt(index) {
        if (index >= 0 && index <= this.count) {
            let current = this.head;
            
            if (index === 0) {
                this.head = current.next;
                // 如果只有一个节点
                if (this.count === 1) {
                    this.tail = null;
                } else {
                    this.head.prev = null;
                }
            } else if (index === this.count - 1) {
                current = this.tail;
                this.tail = current.prev;
                this.tail.next = undefined;
            } else {   // 建议这个过程可以画图
                current = this.getElementAt(index - 1);
                const previous = current.prev;
                previous.next = current.next;
                current.next.prev = previous;
            }
            this.count--;
            return current.val;
        }
        return undefined;
    }    
}

循环链表

循环链表可以向单链表一样引用，也可以像双链表一样引用，特点在于最后一个元素指向链表中的某一个节点，而不是null

有序链表

有序链表指元素有序的链表结构

参考

代码随想录_链表

Posted on Edited on In , , Symbols count in article: 1.8k Reading time ≈ 2 mins.

Queue类和Deque类请参考：Queue 和 Deque

循环队列——击鼓传花游戏（队列）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
function hotPotato(elementsList, num) {
    const queue = new Queue();
    const elimitatedList = [];
    
    // 先把参与的elementsList加入到队列中
    for (let i = 0; i < elementsList.length; i++) {
        queue.enqueue(elementsList[i]);
    }
    // console.log(queue)
    
    // 开始击鼓
    while (queue.size() > 1) {
        // console.log(queue.size())
        for (let i = 0; i < num; i++) {
            queue.enqueue(queue.dequeue());   // 把对头元素加入到队尾
        }
        elimitatedList.push(queue.dequeue());  // 一轮循环结束后，对头的被淘汰，循环继续
    }
    
    return {
        eliminated: elimitatedList,
        winner: queue.dequeue()   // 最后剩下的人为胜利者
    };
}

// test
const names = ['John', 'Jack', 'Jenny', 'Kate', 'Tom'];
const res = hotPotato(names, 7);

res.eliminated.forEach(ele => {
    console.log(`${ele} 在击鼓传花游戏中被淘汰！`)
})

console.log(`胜利者是${res.winner}！`)

/*
	Jenny 在击鼓传花游戏中被淘汰！
	Jack 在击鼓传花游戏中被淘汰！
	Tom 在击鼓传花游戏中被淘汰！
	Kate 在击鼓传花游戏中被淘汰！
	胜利者是John！
*/

/*
	如果要实现随机，可以在不同轮次传入不同的num！
*/

回文检查器（双端队列）

一般回文检查我们使用双指针的方式，但是使用双端队列也是一种好办法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function palindromeChecker(aString) {
    if (aString === undefined || aString === null || !aString.length) return false;
    
    const deque = new Deque();
   	const lowerString = [...aString];   // 解构赋值：字符串转数组
    let firstChar, lastChar;
    
    // 把元素存入deque中
    for (let i = 0; i < lowerString.length; i++) {
        deque.addBack(lowerString[i]);
    }
    
    // 判断ing
    while (deque.size() > 1) {
        firstChar = deque.removeFront();
        lastChar = deque.removeBack();
        
        if (firstChar !== lastChar) {
            return false;
        } else {
            continue;
        };
    };
    
    return true;
}

// test
const aString1 = 'helloaolleh';
const aString2 = 'helloworldolleh';

console.log(palindromeChecker(aString1));  // true
console.log(palindromeChecker(aString2));  // false

Posted on Edited on In , , Symbols count in article: 1.4k Reading time ≈ 1 mins.

队列具有先进先出的特点，栈具有先进后出的特点，栈和队列互转是经常遇到的情况

参考LeetCode原题：

225. 用队列实现栈

232. 用栈实现队列

用队列实现栈

  • push
  • pop
  • top
  • empty
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class MyStack {
    constructor() {
        this.queue1 = [];
        this.queue2 = [];
    }
    
    // push to back
    push(val) {
        this.queue2.push(val);
        
        while (this.queue1.length) {
            this.queue2.push(this.queue1.shift())
        }
        
        while (this.queue2.length) {
            this.queue1.push(this.queue2.shift());
        }
    }
    
    // 注意：因为是队列，所以只能是pop to front即使用shift()
    pop() {
        if (this.queue1.length) {
            return this.queue1.shift();
        }
    }
    
    // top：要获取的是栈顶元素，对应于队列是队尾元素
    top() {
        if (this.queue1.length) {
            return this.queue1[0];
        }
    }
    
    // empty 判断栈是否为空
    empty() {
        return !this.queue1.length
    }  
}

用栈实现队列

  • push
  • pop
  • peek
  • empty
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class MyQueue {
    constructor() {
        this.stack1 = [];
        this.stack2 = [];
    }
    
    // push
    push(val) {
        this.stack1.push(val);
    }
    
    // pop from bcak 即使用pop方法
    pop() {
        if (!this.stack2.length) {
            while (this.stack1.length) {
                this.stack2.push(this.stack1.pop());
            };
        };
        return this.stack2.pop();
    }
    
    // 取出对头元素 栈只能从后面取，即栈顶元素，所以要交换
    peek() {
        if (!this.stack2.length) {
            while (this.stack1.length) {
                this.stack2.push(this.stack1.pop());
            };
        };
        return this.stack2[this.stack2.length -1];
    }
    
    // 判断为空
    empty() {
        return !this.stack1.length && !this.stack2.length;
    }
}

Posted on Edited on In , , Symbols count in article: 7.6k Reading time ≈ 7 mins.

数组理论基础

数组是存放连续内存空间上的相同数据类型的集合

在JavaScript中，可以在数组中保存不同数据类型的值，因此内存地址并不是连续的，而是采用hash映射的方式

但是现在的JavaScript引擎为了优化JavaScript，会分配一个连续的内存空间给相同数据类型的数组，以达到更好的遍历效果，所以，只要你数组里面存的是相同类型的值，在内存中的地址是连续的

需要注意：

  • 数组的下标都是从0开始的
  • 数组内存空间的地址是连续的

所以在删除或者增加元素的时候，就难免要移动其他元素的地址

数组方法

JavaScript数组API（含手写）

栈（含手写栈类）

栈是一种遵循后进先出（LIFO）的有序集合

栈方法

  • 向栈顶添加元素——push
  • 从栈顶删除元素——pop
  • 查看栈顶元素——peek
  • 检查栈是否为空——isEmpty
  • 清空栈元素——clear

基于数组实现栈及其方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Stack {
    constructor() {
        this.stack = [];
    }
    
    // length可以用size代替
    size() {
        return this.stack.length;
    }
    
    // 向栈顶添加元素——push
    push(val) {
        this.stack.push(val);
        return this.stack.length;
    }
    
    // 从栈顶删除元素——pop 
    pop() {
        return this.stack.pop();
    }
    
    // 查看栈顶元素——peek
    peek() {
        return this.stack[this.stack.length - 1];
    }
    
    // 检查栈是否为空——isEmpty
    isEmpty() {
        return !this.stack.length;
    }
    
    // 清空栈元素——clear
    clear() {
        return this.stack = [];
    }
}

应用一下吧~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 初始化stack
const stack = new Stack();

/*
	实现以下效果：
	[push(2), push(3), push(4), pop(), isEmpty(), peek(), pop(), pop(), isEmpty()]
	得到的结果是：
	[1,2,3,4,false,3,3,2,true]
*/

stack.push(2);
stack.push(3);
stack.push(4);

stack.pop();

// test1
console.log(stack.isEmpty());   // false

// test2
console.log(stack.peek());   // 3

stack.pop();
stack.pop();

// test2
console.log(stack.isEmpty());   // true

基于对象实现栈及其方法

用数组实现Stack是非常方便的，但是如果要在数组中找一个元素，最坏的情况下需要迭代数组的所有位置，也就是时间复杂度是O(n)

另外，数组是一个有序集合，为了保证元素排列有序，它会占用更多的内存空间

使用JavaScript对象存储所有栈元素的优势在于：

  • 直接获取元素，占用较少的内存空间
  • 保证所有元素按照我们需要的排序

注意：相对于数组版本，对象版本需要实现toString()方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Stack {
    constructor() {
        this.count = 0;
        this.stack = {};
    }
    
    // length可以用size代替
    size() {
        return this.count;
    }
    
    // 检查栈是否为空——isEmpty
    isEmpty() {
        return this.count === 0;
    }
    
    // 向栈顶添加元素——push
    push(val) {
        this.stack[this.count] = val;
        this.count++;
        return this.count;
    }
    
    // 从栈顶删除元素——pop 
    pop() {
        if (this.isEmpty()) {
          return undefined;  
        } else {
            const res = this.stack[this.stack.length -1];
            this.count--;
            delete this.stack[this.count];
            return res;
        }
    }
    
    // 查看栈顶元素——peek
    peek() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.stack[this.count -1];
    }
    
    // toString()  [对象特有]
    toString() {
        if (this.isEmpty()) {
            return '';
        }
        
        let objString = String(this.stack[0]);
        for (let i = 1; i < this.count; i++) {
            objString = `${objString},${this.stack[i]}`;
        };
        return objString;
    }
}

应用一下吧~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 初始化stack
const stack = new Stack();

/*
	实现以下效果：
	[push(2), push(3), push(4), pop(), isEmpty(), peek(), pop(), pop(), isEmpty(), push(2), push(3), push(4), toString()]
	得到的结果是：
	[1,2,3,4,false,3,3,2,true,1,2,3, '1,2,3']
*/

stack.push(2);
stack.push(3);
stack.push(4);

stack.pop();

// test1
console.log(stack.isEmpty());   // false

// test2
console.log(stack.peek());   // 3

stack.pop();
stack.pop();

// test2
console.log(stack.isEmpty());   // true

stack.push(2);
stack.push(3);
stack.push(4);

// test3
console.log(stack.toString());  // 2,3,4

栈应用

  • 函数调用
  • 表达式求值
  • 括号匹配
  • 浏览器的前进、后退功能

队列（含手写队列类）

队列是一种遵循先进先出（FIFO）的有序集合

队列方法

  • 向队列添加元素——enqueue
  • 从队列移除元素——dequeue
  • 查看队列头元素——peek
  • 检查队列是否为空——isEmpty
  • 清空队列——clear

基于数组实现队列及其方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Queue{
    constructor() {
        this.queue = [];
    }
    
    // size
    size() {
        return this.queue.length;
    }
    
    // 向队列添加元素——enqueue
    enqueue(val) {
        this.queue.push(val);
        return this.queue.size();
    }
    
    // 从队列移除元素——dequeue
    dequeue() {
        return this.queue.shift();
    }
    
    // 查看队列头元素——peek
    peek() {
        return this.queue[0];
    }
    
    // 检查队列是否为空——isEmpty
    isEmpty() {
        return !this.queue.length;
    }
    
    // 清空队列——clear
    clear() {
        return this.queue = [];
    }
    
}

基于对象实现队列及其方法

基于对象实现队列比数组要难一点，因为对象是根据key来记录索引的，所以需要lowsetCount来记录队头元素的索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Queue{
    constructor() {
        this.queue = [];
        this.count = 0;
        this.lowsetCount = 0;
    }
    
    // size
    size() {
        return this.count - this.lowsetCount;
    }
    
    // 向队列添加元素——enqueue
    enqueue(val) {
        this.queue[this.count] = val;
        this.count++;
    }
    
    // 从队列移除元素——dequeue
    dequeue() {
        if (this.isEmpty()) {
            return undefined;
        }

        const res = this.queue[this.lowsetCount];
        delete this.queue[this.lowsetCount];
        this.lowsetCount++;
        return res;
    }
    
    // 查看队列头元素——peek
    peek() {
        if (this.isEmpty()) {
            return undefined;
        }
        
        return this.queue[this.lowsetCount];
    }
    
    // 检查队列是否为空——isEmpty
    isEmpty() {
        return !this.size();
    }
    
    // 清空队列——clear
    clear() {
        this.queue = {};
        this.count = 0;
        this.lowsetCount = 0;
    }
    
    // toString()
    toString() {
        if (this.isEmpty()) {
            return '';
        }
        
        let objString = String(this.queue[this.lowsetCount]);
        for (let i = this.lowsetCount+1; i < this.count; i++) {
            objString = `${objString},${this.queue[i]}`;
        };
        return objString;
    } 
}

应用一下吧~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 初始化队列
const queue = new Queue();

/*
	实现下列效果：
	[enqueue(1), enqueue(2), enqueue(3), isEmpty() ,peek(), dequeue(), dequeue(), enqueue(4), toString()]
	打印
	[1,2,3,false,1,1,2,4, '3,4']
*/

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

console.log(queue.isEmpty());  // false

console.log(queue.peek());   // 1

queue.dequeue();
queue.dequeue();

queue.enqueue(4);

console.log(queue.toString());   // 3,4

队列应用

  • 排队
  • 异步任务：微任务队列和宏任务队列
  • 打印队列

双端队列（含手写双端队列类）

双端队列支持同时从后面或者前面添加或者移除元素

双端队列方法

  • 从队头添加元素——addFront
  • 从队尾添加元素——addBack
  • 从队头移除元素——removeFront
  • 从队尾移除元素——removeBack
  • 查看队头元素——peekFont
  • 查看队尾元素——peekBack
  • 检查队列是否为空——isEmpty
  • 清空队列——clear

基于对象实现队列及其方法

用数组实现较为简单，这里就写了，直接用对象开写！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class Deque{
    constructor() {
        this.deque = {};
        this.count = 0;
        this.lowsetCount = 0;
    }
    
    // size
    size() {
        return this.count - this.lowsetCount;
    }
    
    // 从队头添加元素——addFront
    addFront(val) {
        if (this.isEmpty()) {  // 情况1： 如果队列是空的
            this.addBack(val);
        } else if (this.lowsetCount > 0) {  // 情况2：如果已经有删除过的情况，即 lowsetCount > 0，顶替lowsetCount-1的位置即可
            this.deque[this.lowsetCount - 1] = val;
        } else if (this.lowsetCount === 0) { // 情况3:为0的情况
            for (let i = this.count; i > 0; i++) {
                this.deque[this.count] = this.deque[this.count -1];
            };
            this.count++;
            this.lowsetCount = 0;
            this.deque[0] = val;
        }
    }
    
    // 从队尾添加元素——addBack
    addBack(val) {
        this.deque[this.count] = val;
        this.count++;
    }
    
    // 从队头移除元素——removeFront
    removeFront() {
        let res = this.deque[this.lowsetCount];
        delete this.deque[this.lowsetCount];
        this.lowsetCount++;
        return res;
    }
    
    // 从队尾移除元素——removeBack
    removeBack() {
        this.count--;
        let res = this.deque[this.count];
        delete this.deque[this.count];
        return res;
    }
    
    // 查看队头元素——peekFont
    peekFront() {
        return this.deque[this.lowsetCount];
    }
    
    // 查看队尾元素——peekBack
    peekBack() {
        return this.deque[this.count - 1];
    }
    
    // 检查队列是否为空——isEmpty
    isEmpty() {
        return this.count - this.lowsetCount === 0;
    }
    
    // 清空队列——clear
    clear() {
        this.queue = {};
        this.count = 0;
        this.lowsetCount = 0;
    }
    
    // toString()
    toString() {
        if (this.isEmpty()) {
            return '';
        }
        
        let objString = String(this.deque[this.lowsetCount]);
        for (let i = this.lowsetCount+1; i < this.count; i++) {
            objString = `${objString},${this.deque[i]}`;
        };
        return objString;
    } 
}

应用一下吧~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const deque = new Deque();

console.log(deque.isEmpty());  // true

deque.addBack(1);
deque.addBack(2);

console.log(deque.toString());   // '1,2'

deque.addBack(3);

console.log(deque.toString());   // '1,2,3'

console.log(deque.size());   // 3
console.log(deque.isEmpty());   // false

deque.removeFront();
console.log(deque.toString());   // '2,3'

deque.removeBack();
console.log(deque.toString());   // '2'

双端队列应用

  • 浏览器撤销和回退操作
  • 判断回文子串

参考

代码随想录_数组基础