面试助力,算法 101:JavaScript 描述
搜索文档…
面试助力,算法 101:JavaScript 描述
目录
写在前面
学习指南
开篇——复杂度
字符串
数学
数组
链表
二叉树
动态规划
回溯算法
排序与搜索
栈和队列
汉明距离、位 1 的个数、缺失数字
有效的括号、帕斯卡三角形和颠倒二进制位
两整数之和、数据流的中位数和逆波兰表达式
Task Sheduler、有序矩阵中第K小的元素和多数元素
结束篇
由
GitBook
提供支持
栈和队列
栈(Stack)
栈是一种特殊的列表,限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。它按照
先进后出
的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据。例如饭店里用来放盘子的,就是一种栈的结构。
由于栈具有
后入先出
的特点,因此只能访问在栈顶的元素。栈的操作主要有两种:入栈和出栈。上面的图演示了入栈和出栈的过程。
栈的实现
实现一个栈,可以用数组来实现,也可以用链表来实现。下面将用数组来实现。
1
class
Stack
{
2
constructor
()
{
3
this
.
data
=
[];
4
this
.
top
=
0
;
// 记录栈顶位置,如果有元素进栈,该变量值随之变化
5
}
6
7
push
(
item
)
{
8
this
.
data
[
this
.
top
++
]
=
item
;
9
}
10
11
pop
()
{
12
// 栈为空,则直接返回null
13
if
(
this
.
top
===
0
)
{
14
return
null
;
15
}
16
// 返回下标为top - 1 的数组元素,并将栈中元素个数减一
17
return
this
.
data
[
--
this
.
top
];
18
}
19
20
clear
()
{
21
this
.
top
=
0
;
22
}
23
24
get
length
()
{
25
return
this
.
top
;
26
}
27
}
Copied!
那么栈的空间、时间复杂度又分别是多少?其实很简单,我们发现储存数据只需要长度为
n
n
n
的数组就够了,在入栈和出栈过程中,只需要一两个临时变量存储空间,所以空间复杂度是
O
(
1
)
O(1)
O
(
1
)
。
注意 ⚠️:算法的复杂度是指程序指除了原本的数据存储空间外,算法运行还需要额外的存储空间。
队列(Queue)
队列是一种
先进先出
的数据结构,这点和栈不一样。队列这个概念很好理解,可以想象成在食堂排队买饭吃,先到先得,后面来的排队,不允许插队。
队列的主要操作有两种:向队列中插入或删除新的元素。插入操作可以比喻成吃饭,删除操作可以比喻成(XX)。
和栈一样,队列可以用数组来实现,也可以用链表来实现。下面将用数组来实现一个队列。
1
class
Queue
{
2
constructor
()
{
3
this
.
data
=
[];
4
// head表示头部下标,tail表示尾部下标
5
this
.
head
=
0
;
6
this
.
tail
=
0
;
7
}
8
9
// 入队
10
enqueue
(
item
)
{
11
this
.
data
[
this
.
tail
++
]
=
item
;
12
}
13
14
dequeue
()
{
15
// 如果head == tail 表示队列为空
16
if
(
this
.
head
===
this
.
tail
)
{
17
return
null
;
18
}
19
return
this
.
data
[
++
this
.
head
];
20
}
21
22
get
length
()
{
23
return
this
.
tail
-
this
.
head
;
24
}
25
}
Copied!
对于栈来说,一个指针就够了,但是队列需要两个指针,分别用于指向头部和尾部。
在栈和队列相关的题目之外,挑选了一些额外的题目。不知道看过前面章节的你掌握了多少?这部分的题目可以帮助大家测试以下算法掌握得怎么样了。建议先不要急着看答案,越能自主解决问题,自身的能力才提升得更快。
本章节分为 4 个部分:
Part 1
汉明距离
位1的个数
缺失的数字
Part 2
有效的括号
帕斯卡三角形
颠倒二进制位
Part 3
两整数之和
数据流的中位数
逆波兰表达式
Part 4
Task Sheduler
有序矩阵中第K小的元素
多数元素
以前
搜索二维矩阵 II和计算右侧小于当前元素的个数
下一个
汉明距离、位 1 的个数、缺失数字
最近更新
2yr ago
复制链接
内容
栈(Stack)
队列(Queue)