面闭 —— 数据结构

知识点

时间复杂度

通常使用最差的时间复杂度来衡量一个算法的好坏。

常数时间 O(1) 代表这个操作和数据量没有关系,是一个固定时间的操作,比如说四则运算。

对于一个算法来说,可能会计算出操作次数为 aN + 1,N 代表数据量。那么该算法的时间复杂度就是 O(N)。因为在计算时间复杂度的时候,数据量通常是非常大的,这时候低阶项和常数项可以忽略不计。

当出现两个算法都是 O(N) 的时间复杂度,那么对比两个算法的好坏就要通过低阶项和常数项了。

栈是一个线性结构。
栈的特点是只能在某一端添加或删除数据,遵循先进后出的原则。

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
class Stack {
constructor() {
this.stack = []
}
// 进
push(item) {
this.stack.push(item)
}
// 出
pop() {
this.stack.pop() // 删除并返回数组第一个
}
// 查看
peek() {
return this.stack[this.getCount() - 1] // 查看最后一个
}
// 获取长度
getCount() {
return this.stack.length
}
// 清空
isEmpty() {
return this.getCount() === 0
}
}

队列

队列是一个线性结构。
队列的特点是某一端添加数据,在另一端删除数据,遵循先进先出的原则。

单链队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Queue {
constructor() {
this.queue = []
}
// 进
enQueue(item) {
this.queue.push(item)
}
// 出
deQueue() {
return this.queue.shift() // 删除并返回数组最后一个
}
getHeader() {
return this.queue[0]
}
getLength() {
return this.queue.length
}
isEmpty() {
return this.getLength() === 0
}
}

因为单链队列在出队操作的时候需要 O(n) 的时间复杂度,所以引入了循环队列。循环队列的出队操作平均是 O(1) 的时间复杂度。

数组越界
比如数组定义时有十个元素,那么a[0] – a[9] 分别对应相应的元素,在程序中如果使用了a[10]那么就超出了原来的数组定义的范围,这就是数组下标越界。

循环队列?

链表

面试题


相关资料

前端面试之道
数组越界的意思

作者

Fallen-down

发布于

2021-06-28

更新于

2021-06-28

许可协议

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

评论

You forgot to set the shortname for Disqus. Please set it in _config.yml.
You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.