队列与广度优先搜索及其相关题目
1. 队列基础知识
1.1 队列简介
-
定义
队列（Queue）：一种线性表数据结构，是一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线性表
队尾（rear）：队列中允许插入的一端
队首（front）：队列中允许删除的一端
空队：队列中没有任何元素时 -
基本操作
- 插入，也称为入队
- 删除，也称为出队
与栈的 先进后出 不同，队列是一种 先进先出（First In First Out）的线性表，简称为 FIFO 结构
定义的解释：
- 线性表：队列首先是一个线性表，队列中元素具有前驱后继的线性关系。队列中元素按照次序依次入队
- 先进先出：根据队列的定义，最先进入队列的元素在队头，最后进入队列的元素在队尾。每次删除的总是队列中的队头元素，即最先进入队列的元素
1.2 队列的顺序存储与链式存储
与线性表相同，队列也有着一下的两种存储方式
- 顺序存储
利用一组地址连续的存储单元依次存放队列中从队头到队尾的元素，同时使用指针 front 指向队头元素在队列中的位置，使用指针 rear 指示队尾元素在队列中的位置 - 链式存储
利用单链表的方式来实现队列。队列中元素按照插入顺序依次插入到链表的第一个节点之后，并使用队头指针 front 指向链表头节点位置，也就是队头元素，rear 指向链表尾部位置，也就是队尾元素
注意：根据算法实现方式的不同，front 和 rear 的指向位置并不完全固定。有时候算法设计上的方便以及代码简洁，也会使 front 指向队头元素所在位置的前一个位置。rear 也可能指向队尾元素在队列位置的下一个位置
下面，我们先看一下队列的基本操作，会让我们对其实现有更深的理解
1.2.1 队列的基本操作
- 初始化空队列：创建一个空队列，定义队列的大小 size，以及队头元素指针 front，队尾指针 rear
- 判断队列是否为空：当队列为空时，返回 True。当队列不为空时，返回 False。一般只用于队列中删除操作和获取队头元素操作中
- 判断队列是否已满：当队列已满时，返回 True，当队列未满时，返回 False。一般只用于顺序队列中插入元素操作中
- 插入元素（入队）：相当于在线性表最后元素后面插入一个新的数据元素。并改变队列顶指针 top 的指向位置
- 删除元素（出队）：相当于在线性表最后元素后面删除最后一个数据元素。并改变队列顶指针 top 的指向位置
- 获取队列队头元素：相当于获取线性表中最后一个数据元素。与插入元素、删除元素不同的是，该操作并不改变队列顶指针 top 的指向位置
1.2.2 队列的顺序实现（List）
- 基本描述：
为了算法设计上的方便以及算法本身的简单，我们约定：队头指针 self.front 指向队头元素所在位置的前一个位置，而队尾指针 self.rear 指向队尾元素所在位置- 初始化时：创建一个空队列 self.queue，定义队列大小 self.size。令队头指针 self.front 和队尾指针 self.rear 都指向 -1。即 self.front = self.rear = -1
- 判断队列为空：判断队列为空：根据 self.front 和 self.rear 的指向位置关系进行判断。如果对头指针 self.front 和队尾指针 self.rear 相等，则说明队列为空
- 判断队列为满：如果 self.rear 指向队列最后一个位置，即 self.rear == self.size - 1，则说明队列已满
- 获取队头元素：先判断队列是否为空，为空直接抛出异常。如果不为空，因为 self.front 指向队头元素所在位置的前一个位置，所以队头元素在 self.front 后面一个位置上，返回 self.queue[self.front + 1]
- 获取队尾元素：先判断队列是否为空，为空直接抛出异常。如果不为空，因为 self.rear 指向队尾元素所在位置，所以直接返回 self.queue[self.rear]
- 入队操作：先判断队列是否已满，已满直接抛出异常。如果不满，则将队尾指针 self.rear 向右移动一位，并进行赋值操作。此时 self.rear 指向队尾元素
- 出队操作：先判断队列是否为空，为空直接抛出异常。如果不为空，则将队头指针 self.front 指向元素赋值为 None，并将 self.front 向右移动一位
- 代码实现：
class Queue:
# 初始化空队列
def __init__(self. size = 100):
self.size = size
self.queue = [None for _ in range(size)]
self.front = -1
self.rear = -1
# 判断队列是否为空
def is_empty(self):
return self.front == self.rear
# 判断队列是否已满
def is_full(self):
return self.rear + 1 == self.size
# 入队操作
def enqueue(self, val):
if self.is_full():
raise Exception('Queue is full')
else:
self.rear += 1
self.queue[self.rear] = value
# 出队操作
def dequeue(self):
if self.is_empty():
raise Exception('Queue is empty')
else:
self.front += 1
return self.queue[self.front]
# 获取队首元素
def front_value(self):
if self.is_empty():
raise Exception('Queue is empty')
else:
return self.queue[self.front + 1]
# 获取队尾元素
def rear_value(self):
if self.is_empty():
raise Exception('Queue is empty')
else:
return self.queue[self.rear]
1.2.3 循环队列的提出及其实现方法
由于出队操作总是删除当前的队头元素，将 self.front 进行右移，而插入操作又总是在队尾进行。经过不断的出队、入队操作，队列的变化就像是使队列整体向右移动。当队尾指针 self.rear == self.size - 1 时，此时再进行入队操作就又抛出队列已满的异常。而之前因为出队操作而产生空余位置也没有利用上，这就造成了假溢出问题。
而为了解决这个问题，有两种做法：
-
每一次删除队头元素之后，就将整个队列往前移动 1 个位置。其代码如下所示
# 出队操作 def dequeue(self): if self.is_empty(): raise Exception('Queue is empty') else: value = self.queue[0] for i in range(self.rear): self.queue[i] = self.queue[i + 1] return value这种情况下，队头指针似乎用不到了。因为队头指针总是在队列的第 0 个位置。但是因为删除操作涉及到整个队列元素的移动，所以每次删除操作的时间复杂度就从O(1)变为了O(n)。这种方式不太可取
-
将队列想象成为头尾相连的循环表，利用数学中的求模运算，使得空间得以重复利用，这样就解决了问题
这样在进行插入操作时，如果队列的第 self.size - 1 个位置被占用之后，只要队列前面还有可用空间，新的元素加入队列时就可以从第 0 个位置开始继续插入
我们约定：self.size 为循环队列的最大元素个数。队头指针 self.front 指向队头元素所在位置的前一个位置，而队尾指针 self.rear 指向队尾元素所在位置。则
- 入队时，队尾指针循环前进 1 个位置，即 self.rear = (self.rear + 1) % self.size
- 出队时，队头指针循环前进 1 个位置，即 self.front = (self.front + 1) % self.size
注意：循环队列在一开始初始化，队列为空时，self.front 等于 self.rear。而当充满队列后，self.front 还是等于 self.rear。这种情况下就无法判断「队列为空」还是「队列为满」了
解决方式为：
- 增加表示队列中元素个数的变量 self.count，用来以区分队列已满还是队列为空。在入队、出队过程中不断更新元素个数 self.count 的值
- 队列已满条件为：队列中元素个数等于队列整体容量，即 self.count == self.size
- 队空为空条件为：队列中元素个数等于 0，即 self.count == 0
- 增加标记变量 self.tag，用来以区分队列已满还是队列为空
- 队列已满条件为：self.tag == 1 的情况下，因插入导致 self.front == self.rear
- 队列为空条件为：在 self.tag == 0 的情况下，因删除导致 self.front == self.rear
- 特意空出来一个位置用于区分队列已满还是队列为空。入队时少用一个队列单元，即约定以「队头指针在队尾指针的下一位置」作为队满的标志
- 队列已满条件为：队头指针在队尾指针的下一位置，即 (self.rear + 1) % self.size == self.front
- 队列为空条件为：队头指针等于队尾指针，即 self.front == self.rear
整体的代码实现：
class Queue:
# 初始化空队列
def __init__(self, size=100):
self.size = size + 1
self.queue = [None for _ in range(size + 1)]
self.front = 0
self.rear = 0
# 判断队列是否为空
def is_empty(self):
return self.front == self.rear
# 判断队列是否已满
def is_full(self):
return (self.rear + 1) % self.size == self.front
# 入队操作
def enqueue(self, value):
if self.is_full():
raise Exception('Queue is full')
else:
self.rear = (self.rear + 1) % self.size
self.queue[self.rear] = value
# 出队操作
def dequeue(self):
if self.is_empty():
raise Exception('Queue is empty')
else:
self.queue[self.front] = None
self.front = (self.front + 1) % self.size
return self.queue[self.front]
# 获取队头元素
def front_value(self):
if self.is_empty():
raise Exception('Queue is empty')
else:
value = self.queue[(self.front + 1) % self.size]
return value
# 获取队尾元素
def rear_value(self):
if self.is_empty():
raise Exception('Queue is empty')
else:
value = self.queue[self.rear]
return value
1.2.4 队列的链式存储实现
对于在使用过程中数据元素变动较大，或者说频繁进行插入和删除操作的数据结构来说，采用链式存储结构比顺序存储结构更加合适
所以我们可以采用链式存储结构来实现队列。我们用一个线性链表来表示队列，队列中的每一个元素对应链表中的一个链节点。然后把线性链表的第 1 个节点定义为队头指针 front，在链表最后的链节点建立指针 rear 作为队尾指针。并且限定只能在链表队头进行删除操作，在链表队尾进行插入操作，这样整个线性链表就构成了一个队列
- 基本描述：
我们约定：队头指针 self.front 指向队头元素所在位置的前一个位置，而队尾指针 self.rear 指向队尾元素所在位置。- 初始化时：建立一个链表头节点 self.head，令队头指针 self.front 和队尾指针 self.rear 都指向 head。即 self.front = self.rear = head
- 判断队列为空：根据 self.front 和 self.rear 的指向位置进行判断。根据约定，如果对头指针 self.front 等于队尾指针 self.rear，则说明队列为空。
- 获取队头元素：先判断队列是否为空，为空直接抛出异常。如果不为空，因为 self.front 指向队头元素所在位置的前一个位置，所以队头元素在 self.front 后一个位置上，返回 self.front.next.value
- 获取队尾元素：先判断队列是否为空，为空直接抛出异常。如果不为空，因为 self.rear 指向队尾元素所在位置，所以直接返回 self.rear.value
- 入队操作：创建值为 value 的链表节点，插入到链表末尾，并令队尾指针 self.rear 沿着链表移动 1 位到链表末尾。此时 self.rear 指向队尾元素
- 出队操作：先判断队列是否为空，为空直接抛出异常。如果不为空，则获取队头指针 self.front 下一个位置节点上的值，并将 self.front 沿着链表移动 1 位。如果 self.front 下一个位置是 self.rear，则说明队列为空，此时，将 self.rear 赋值为 self.front，令其相等
- 代码实现
class Node:
def __init__(self, value):
self.value = value
self.next = None
class Queue:
# 初始化空队列
def __init__(self):
head = Node(0)
self.front = head
self.rear = head
# 判断队列是否为空
def is_empty(self):
return self.front == self.rear
# 入队操作
def enqueue(self, value):
node = Node(value)
self.rear.next = node
self.rear = node
# 出队操作
def dequeue(self):
if self.is_empty():
raise Exception('Queue is empty')
else:
node = self.front.next
self.front.next = node.next
if self.rear == node:
self.rear = self.front
value = node.value
del node
return value
# 获取队头元素
def front_value(self):
if self.is_empty():
raise Exception('Queue is empty')
else:
return self.front.next.value
# 获取队尾元素
def rear_value(self):
if self.is_empty():
raise Exception('Queue is empty')
else:
return self.rear.value
1.3 队列的应用
- 解决计算机的主机与外部设备之间速度不匹配的问题
比如解决主机与打印机之间速度不匹配问题。主机输出数据给计算机打印，输出数据的速度比打印数据的速度要快很多，如果直接把数据送给打印机进行打印，由于速度不匹配，显然行不通。为此，可以设置一个打印数据缓存队列，将要打印的数据依次写入缓存队列中。然后打印机从缓冲区中按照先进先出的原则依次取出数据并且打印。这样即保证了打印数据的正确，又提高了主机的效率。 - 解决由于多用户引起的系统资源竞争的问题
- 比如说一个带有多终端的计算机系统，当有多个用户需要各自运行各自的程序时，就分别通过终端向操作系统提出占用 CPU 的请求。操作系统通常按照每个请求在时间上的先后顺序将它们排成一个队列，每次把 CPU 分配给队头请求的用户使用；当相应的程序运行结束或用完规定的时间间隔之后，将其退出队列，再把 CPU 分配给新的队头请求的用户使用。这样既能满足多用户的请求，又能使 CPU 正常运行
- 再比如 Linux 中的环形缓存、高性能队列 Disruptor，都用到了循环并发队列。iOS 多线程中的 GCD、NSOperationQueue 都用到了队列结构
2. 广度优先搜索
2.1 简介
广度优先搜索算法（Breadth First Search）：简称为 BFS，又译作宽度优先搜索 / 横向优先搜索。是一种用于遍历或搜索树或图的算法。该算法从根节点开始，沿着树的宽度遍历树或图的节点。如果所有节点均被访问，则算法中止
广度优先遍历类似于树的层次遍历过程。呈现出一层一层向外扩张的特点。先看到的节点先访问，后看到的节点后访问。遍历到的节点顺序符合先进先出的特点，所以广度优先搜索可以通过队列来实现
2.2 基于队列的广度优先搜索
- 步骤
- graph 为存储无向图的字典变量，start 为开始节点
- 然后定义 visited 为标记访问节点的 set 集合变量。定义 q 为存放节点的队列
- 首先将起始节点放入队列 q中，即 q.put(start)。并将其标记为访问，即 visited.add(start)
- 从队列中取出第一个节点 node_u。访问节点 node_u，并对节点进行相关操作（看具体题目要求）
- 遍历与节点 node_u 相连并构成边的节点 node_v
如果 node_v 没有被访问过，则将 node_v 节点放入队列中，并标记访问，即 q.append(node_v)，visited.add(node_v)。 - 重复步骤 4 ~ 5，直到 q 为空
- 代码实现
import collections
def bfs(graph, strat):
visited = set(start)
q = collections.deque([start])
while q:
node_u = q.popleft()
print(node_u)
for node_v in graph[node_u]:
if node_v not in visited:
visited.add(node_v)
q.append(node_v)
3. 相关题目
3.1 队列相关题目
225.用队列实现栈
- 思路：
队列是先入先出的线性表，而栈是先入后出的线性表，所以，我们可以使用两个队列来模拟先入后出的栈
建立两个队列queue1和queue2，入栈时先将元素置入queue2，之后将queue1中的元素添加到queue2中，再交换queue1与queue2即可。循环执行 - 代码实现
class MyStack:
def __init__(self):
self.queue1 = collections.deque()
self.queue2 = collections.deque()
def push(self, x: int) -> None:
self.queue2.append(x)
while self.queue1:
self.queue2.append(self.queue1.popleft())
self.queue1, self.queue2 = self.queue2, self.queue1
def pop(self) -> int:
return self.queue1.popleft()
def top(self) -> int:
return self.queue1[0]
def empty(self) -> bool:
return not self.queue1
3.2 BFS相关题目
463.岛屿的周长
-
思路
- 迭代：
遍历网格中的所有点，如果遇到一个网格的值为1，ans + 4，并查看四条边是否与另一个1相邻，如果相邻，减一即可 - 广度优先搜索：
定义一个BFS函数来实现寻找陆地周长的功能。
步骤：
1. 遍历网格，找到一个值为1的位置作为BFS的起始位置
2. 定义结果变量ans和用于BFS的队列q
3. 取出列表中的元素，并将其置为2以避免重复访问
4. 遍历四个方向，如果靠近边界或者靠近水时+1
5. 如果值为1，将其置为2，同时加入队列
- 迭代：
-
代码实现
class Solution: def islandPerimeter(self, grid: List[List[int]]) -> int: r, c = len(grid), len(grid[0]) ans = 0 for i in range(r): for j in range(c): if grid[i][j] == 1: ans += 4 if i - 1 >= 0 and grid[i - 1][j] == 1: ans -= 1 if i + 1 < r and grid[i + 1][j] == 1: ans -= 1 if j - 1 >= 0 and grid[i][j - 1] == 1: ans -= 1 if j + 1 < c and grid[i][j + 1] == 1: ans -= 1 return ansclass Solution: def islandPerimeter(self, grid: List[List[int]]) -> int: def bfs(grid, i, j): directs = [(0, 1), (0, -1), (1, 0), (-1, 0)] q = collections.deque([(i, j)]) ans = 0 while q: row, col = q.popleft() grid[row][col] = 2 for direct in directs: new_row = row + direct[0] new_col = col + direct[1] if new_row < 0 or new_row >= r or new_col < 0 or new_col >= c or grid[new_row][new_col] == 0: ans += 1 elif grid[new_row][new_col] == 1: grid[new_row][new_col] = 2 q.append([new_row, new_col]) return ans r, c = len(grid), len(grid[0]) for i in range(r): for j in range(c): if grid[i][j] == 1: return bfs(grid, i, j)
752.打开转盘锁
- 思路：
将所有可能出现的转盘锁的情况视为一个图，每种情况都是一个节点，可以通过一步相互转化的节点之间连接。所以，我们找的是从起始节点到目标节点的最少步数，也即最短路径，可以使用广度优先搜索。
将0000作为初始状态开始，在搜索过程中不停的判断是否在dead中或者已经搜索过。 - 代码实现：
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
if target == '0000':
return 0
dead = set(deadends)
if '0000' in dead:
return -1
def num_prev(x):
return '9' if x == '0' else str(int(x) - 1)
def num_succ(x):
return '0' if x == '9' else str(int(x) + 1)
# 枚举 status 通过一次旋转得到的数字
def get(s):
s = list(s)
for i in range(4):
num = s[i]
s[i] = num_prev(num)
yield ''.join(s)
s[i] = num_succ(num)
yield ''.join(s)
s[i] = num
q = deque([('0000', 0)])
seen = {'0000'}
while q:
statue, step = q.popleft()
for next_status in get(statue):
if next_status not in seen and next_status not in dead:
if next_status == target:
return step + 1
q.append((next_status, step + 1))
seen.add(next_status)
return -1