队列被定义为两端开放的线性数据结构,并且操作按照先进先出(FIFO)顺序执行。
我们将队列定义为一个列表,其中对列表的所有添加都在一端进行,而对列表的所有删除都在另一端进行。首先被推入订单的元素,首先对其执行操作。
队列中的 Fifo 属性
与堆栈一样,队列也可以用数组表示:在这种表示中,队列是使用数组来实现的。本例中使用的变量是
# 创建一个空队列 表示队列的结构
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)
队列还可以使用以下实体表示:
class QNode:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = None
self.rear = None
有不同类型的队列:
给定一个无向图,如何检查图中是否存在环?例如,下图的循环为1-0-2-1。
我们使用父数组来跟踪顶点的父顶点,这样我们就不会将访问的父顶点视为循环。
# 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")
yes
时间复杂度:该程序对图进行简单的 BFS 遍历,并且使用邻接表来表示图。所以时间复杂度是O(V+E) 空间复杂度:对于访问向量来说是 O(V)。