课程名称:2周刷完100道前端优质面试真题
课程章节:第2章 前端面试技能拼图1 :数据结构和算法(上),大厂面试必考
主讲老师:双越
课程内容:
今天学习的内容包括:
2-8 用两个栈实现一个队列——也就是使用两个数组来实现队列的功能,使用栈可以优化整体的时间复杂度。
课程收获:
两个栈实现一个队列
- 请用两个栈,实现一个队列。
- 功能 add delete length
队列
- 先进先出。
- API : add delete length。
逻辑结构vs物理结构
- 队列是逻辑结构,抽象模型。
- 简单的,可以用数组、链表实现。
- 复杂的队列服务,需单独设计。
while(stack1.length) {
const n = stack1.pop()
if (n != null) {
stack2.push(n)
}
}
划重点
- 队列。
- 逻辑结构vs物理结构。
- 画图,帮助梳理解题思路。
tips
- private为类的私有属性。
- 数组中的shift()方法时间复杂度是O(n),整体便是O(n^2),因此使用两个栈实现一个队列,这样的情况下整体时间复杂度为O(n)。
- 好记性不如烂笔头,要多做笔记。
- 测试用例中判断数组是否为Null使用toBeNull()。
- 判断具体数字使用的是toBe()。
今天的 学习了 两个栈实现一个队列,通过两个数组使用栈的特性来实现队列的功能,这样可以使队列的整体时间复杂度为O(n),使代码整体性能更好。
下一步就是 使用 JS 反转单向链表了。今天学习就先到这里吧。
坚持打卡,坚持学习,未来可期,加油😀~