什么是队列数据结构？
队列被定义为两端开放的线性数据结构，并且操作按照先进先出（FIFO）顺序执行。
我们将队列定义为一个列表，其中对列表的所有添加都在一端进行，而对列表的所有删除都在另一端进行。首先被推入订单的元素，首先对其执行操作。
队列的先进先出原理：
- 队列就像等待买票的队伍，队列中的第一个人就是第一个得到服务的人。（即先到先得）。
- 队列中准备被服务的条目的位置，即将从队列中删除的第一个条目，称为队列的前端（有时称为队列头），类似地，最后一个条目的位置队列中，即最近添加的队列，称为队列的后部（或尾部）。见下图。
队列中的 Fifo 属性
队列的特点：
- 队列可以处理多个数据。
- 我们可以访问两端。
- 它们快速且灵活。
队列表示：
与堆栈一样，队列也可以用数组表示：在这种表示中，队列是使用数组来实现的。本例中使用的变量是
- 队列：存储队列元素的数组名称。
- Front：表示队列的数组中存储第一个元素的索引。
- 后部：代表队列的数组中存储最后一个元素的索引。
1.队列的数组表示：
Python
代码语言：javascript复制# 创建一个空队列 表示队列的结构
class Queue:
# 构造函数
def __init__(self, cap):
self.cap = cap
self.front = 0
self.size = 0
self.rear = cap - 1
self.arr = [0] * cap
# 创建指定容量队列的函数
# 它将队列的大小初始化为 0
def createQueue(self):
return Queue(self.cap)2.队列的链表表示：
队列还可以使用以下实体表示：
- 链接列表，
- 指针，以及
- 结构。
Python:
代码语言：javascript复制class QNode:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = None
self.rear = None队列类型：
有不同类型的队列：
- 输入受限队列：这是一个简单的队列。在这种类型的队列中，只能从一端获取输入，但可以从任意一端进行删除。
- 输出受限队列：这也是一个简单的队列。在这种类型的队列中，可以从两端获取输入，但只能从一端进行删除。
- 循环队列：这是一种特殊类型的队列，其中最后一个位置连接回第一个位置。这里的操作也是按照 FIFO 顺序执行的。
- 双端队列（Dequeue）：在双端队列中插入和删除操作，都可以从两端进行。
- 优先级队列：优先级队列是一种特殊的队列，其中的元素根据分配给它们的优先级进行访问。
使用 BFS 检测无向图中的循环
给定一个无向图，如何检查图中是否存在环？例如，下图的循环为1-0-2-1。
我们使用父数组来跟踪顶点的父顶点，这样我们就不会将访问的父顶点视为循环。
Python3 代码实现：
代码语言：javascript复制# Python3 程序使用 BFS 检测无向图中的循环。
# 使用 BFS 检测无向图中的循环。
from collections import deque
def addEdge(adj: list, u, v):
adj[u].append(v)
adj[v].append(u)
def isCyclicConnected(adj: list, s, V,
visited: list):
# 将每个顶点的父顶点设置为 -1。
parent = [-1] * V
# 为 BFS 创建队列
q = deque()
# 将当前节点标记为
# 标记为已访问，并将其排队
visited[s] = True
q.append(s)
while q != []:
# Dequeue a vertex from queue and print it
u = q.pop()
# 获取已出队的顶点u的所有相邻顶点。如果相邻顶点尚未被访问，
# 则将其标记为已访问并入队。我们还标记父节点，以便不考虑循环。
for v in adj[u]:
if not visited[v]:
visited[v] = True
q.append(v)
parent[v] = u
elif parent[u] != v:
return True
return False
def isCyclicDisconnected(adj: list, V):
# 标记所有顶点为未访问顶点
visited = [False] * V
for i in range(V):
if not visited[i] and
isCyclicConnected(adj, i, V, visited):
return True
return False
if __name__ == "__main__":
V = 4
adj = [[] for i in range(V)]
addEdge(adj, 0, 1)
addEdge(adj, 1, 2)
addEdge(adj, 2, 0)
addEdge(adj, 2, 3)
if isCyclicDisconnected(adj, V):
print("Yes")
else:
print("No")输出
代码语言：javascript复制yes时间复杂度：该程序对图进行简单的 BFS 遍历，并且使用邻接表来表示图。所以时间复杂度是O(V E) 空间复杂度：对于访问向量来说是 O(V)。
