Aelous-Blog

养一猫一狗,猫叫夜宵,狗叫宵夜

0%

队列&栈-01

数组中,我们可以通过索引来访问数据,很多情况下我们可能会想限制数据的处理顺序。

常见的两种处理顺序是:先入先出(FIFO)以及后入先出(LIFO)

处理顺序数据结构
先入先出队列
后入先出

可以学到什么:

  1. 了解:FIFO 和 LIFO 处理顺序的原理
  2. 实现这两个数据结构
  3. 熟悉内置队列和栈结构
  4. 解决基本队列相关问题,BFS。
  5. 解决基本栈相关问题。
  6. 理解,使用 DFS 和其他递归解决问题时,系统栈如何帮你。

队列:先入先出的数据结构

在 FIFO 数据结构中,将首先处理添加到队列中的第一个元素。

如上图所示,队列是典型的 FIFO 数据结构。插入(insert)操作也称作入队(enqueue),新元素始终被添加在队列的末尾。删除(delete)操作也被称为出队(dequeue)。你只能移除第一个元素。

队列-实现

队列的实现方式其实很好理解,就是一个数组,我们通过指针对头部进行索引,就可以实现了。

这种方法实现很简单,但是效率很低,因为数组的大小不是固定的,会随着指针的移动,占用的空间越来越大。

改进队列

循环队列:我们使用固定大小的数组,和两个指针来指示起始位置和结束位置,目的是重用我们之前被浪费掉的存储。

设计循环队列

要求我们设计的队列有如下功能:

  • MyCircularQueue(k):构造器,设置队列长度为 k
  • Front:从队首获取元素。如果队列为空,返回-1
  • Rear:获取队尾元素。如果队列为空,返回-1
  • enQueue(value):向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue():从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty():检查循环队列是否为空。
  • isFull():检查循环队列是否已满。

设计代码如下(C++):

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
class MyCircularQueue {
private:
int *data; // 存放队列数据
int head; // 队列头部
int tail; // 队列尾部
int len; // 队列长度
int count; // 队列内部元素个数
public:
/** 在此初始化数据结构,将队列长度设置为k **/
MyCircularQueue(int k) {
data = new int[k];
head = 0;
tail = 0;
len = k;
count = 0;
}
/** 将元素插入循环队列中,如果成功则返回true **/
bool enQueue(int value) {
if(isFull()){ // 循环队列满
return false;
} else { //插入元素到队列尾部
data[tail] = value;
count++;
tail = (tail+1) %len;
return true;
}
}
/** 从循环队列中删除元素,如果成功则返回true **/
bool deQueue() {
if(isEmpty()){ // 循环队列空
return false;
} else {
head = (head + 1) % len;
count--;
return true;
}
}
/** 获取队列头部元素 **/
int Front() {
if(isEmpty()){ // 循环队列空
return -1;
} else {
return data[head];
}
}
/** 获取队列尾部元素 **/
int Rear() {
if(isEmpty()){ // 循环队列空
return -1;
} else {
int temp = tail == 0 ? (len-1) : (tail-1);
return data[temp];
}
}
/** 检查队列是否为空 **/
bool isEmpty() {
return count == 0; //队列元素个数为0,元素空。
}
/** 检查队列是否已满 **/
bool isFull() {
return count == len; // 队列元素个数等于数组最大长度,队列满
}
};

队列用法

大多数流行语言都提供内置的队列库,因此实际情况我们并不需要重新发明轮子。

队列有着两个重要的操作,入队列和出队列,此外,我们应该能够获得队列中的第一个元素,因为应该首先处理它。

队列和广度优先搜索

队列和 BFS

广度优先搜索(BFS)的一个常见应用就是找出从根节点到目标结点的最短路径,示例来解释 BFS 算法中是如何逐步应用队列的。

  1. 结点的处理顺序是什么?
    在第一轮中,我们处理根节点。在第二轮中,我们处理根结点旁边的结点;在第三轮中,我们处理距根节点两步的结点。
    与树的层序遍历类似,越是接近根节点的结点越早遍历。
    如果在第 K 轮中将结点 X 添加到队列中,则根节点与 X 之间的最短路径长度恰好是 K,也就是说,第一次找到目标结点的时候,你已经处于最短路径中了。
  2. 队列的入队和出队顺序是什么?
    如上面的动画所示,我们首先将根节点排入队列。然后在每一轮中,我们逐个处理已经在队列中的结点,并将所有的邻居添加到队列中。值得注意的是:新添加的结点不会立即遍历,而是在下一轮中处理。
    结点的处理顺序与他们添加到队列的顺序是完全相同的顺序,即先进先出(FIFO)。这就是我们在 BFS 中使用队列的原因。

广度优先搜索-模版

在特定问题中执行 BFS 之前确定结点和边缘非常重要。通常,结点将是实际结点或是状态,而边缘将是实际边缘或可能的转换。

模版如下(伪代码格式):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 返回根节点和目标节点之间最短路径的长度。
*/
int BFS(Node root, Node target) {
Queue<Node> queue; // 存储所有等待处理的节点
int step = 0; // 从根到当前节点所需的步骤数
// 初始化
add root to queue;
// BFS(广度优先搜索)
while (queue is not empty) {
step = step + 1;
// 迭代队列中已经存在的节点
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
add next to queue;
}
remove the first node from queue;
}
}
return -1; // 从根到目标没有路径
}
  1. 如代码所示,在每一轮中,队列中的结点是等待处理的结点。
  2. 在每个更外一层的 while 循环之后,我们距离根结点更远一步。变量 step 指示从根结点到我们正在访问的当前结点的距离。

有时,确保我们永远不会访问一个结点两次很重要。否则,我们可能陷入无限循环。如果是这样,我们可以在上面的代码中添加一个哈希集来解决这个问题。这是修改后的伪代码

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
/**
* 返回根节点和目标节点之间最短路径的长度。
*/
int BFS(Node root, Node target) {
Queue<Node> queue; // 存储所有等待处理的节点
Set<Node> used; // 存储所有使用的节点
int step = 0; // 从根到当前节点所需的步骤数
// 初始化
add root to queue;
add root to used;
// BFS(广度优先搜索)
while (queue is not empty) {
step = step + 1;
// 迭代队列中已经存在的节点
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
if (next is not in used) {
add next to queue;
add next to used;
}
}
remove the first node from queue;
}
}
return -1; // 从根到目标没有路径
}

有两种情况你不需要使用哈希集:1.你完全确定没有循环,例如,在树遍历中;2.你确实希望多次将结点添加到队列中。

岛屿数量

给你一个由’1’(陆地)和’0’(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。

使用广度优先搜索方式进行搜索

思想:遍历所有的网格,遇到 1,我们就认为遇到了一个岛屿,然后对岛屿的其他范围进行搜索,通过广度优先,对相邻的每个元素进行遍历,如果遇到元素值为 1 的则加入队列。知道队列为空。
我们要将遍历过的值归零。这样所有的都为 0 即结束。

代码如下所示(C++):

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
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
// 获取数组的行数和列数
int rows = grid.size();
int cols = 0;
if(rows ==0){
return 0;
}else{
cols = grid[0].size();
}
int nums = 0; // 初始化岛屿数量
queue<pair<int,int>> Q;
// 遍历数组的每一个元素
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(grid[i][j] == '1'){ // 若当前元素值为1
nums++; // 岛屿数量加一
Q.push(make_pair(i,j));
grid[i][j] = '0'; // 将当前元素值设为0,表示已经访问
// 循环迭代直到队列为空
while(!Q.empty()){
pair<int,int> node = Q.front();
Q.pop();
int row = node.first, col = node.second;
// 遍历上下左右四格,若有元素值为1则加入队列
if(row + 1 < rows && grid[row+1][col] == '1'){
Q.push(make_pair(row+1,col));
grid[row+1][col] ='0';
}
if(col + 1 <cols && grid[row][col+1] == '1'){
Q.push(make_pair(row,col+1));
grid[row][col+1] ='0';
}
if(row - 1 >= 0 && grid[row-1][col] == '1'){
Q.push(make_pair(row-1,col));
grid[row-1][col] ='0';
}
if(col - 1 >= 0 && grid[row][col-1] == '1'){
Q.push(make_pair(row,col-1));
grid[row][col-1] ='0';
}
}
}
}
}
return nums;
}
};

声明:本文为学习记录,参考之处较多,如果有侵权内容,请联系我立即删除

End~~ 撒花= ̄ω ̄=花撒
如果您读文章后有收获,可以打赏我喝咖啡哦~