栈和队列
栈(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!
那么栈的空间、时间复杂度又分别是多少？其实很简单，我们发现储存数据只需要长度为
的数组就够了，在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是
。
注意 ⚠️：算法的复杂度是指程序指除了原本的数据存储空间外，算法运行还需要额外的存储空间。
队列(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小的元素
- 多数元素
最近更新 2yr ago