数据结构和算法教程: 队列数据结构

用户1418987

发布于 2023-11-10 08:25:54

1530

发布于 2023-11-10 08:25:54

文章被收录于专栏：coder

什么是队列数据结构？

队列被定义为两端开放的线性数据结构，并且操作按照先进先出（FIFO）顺序执行。

我们将队列定义为一个列表，其中对列表的所有添加都在一端进行，而对列表的所有删除都在另一端进行。首先被推入订单的元素，首先对其执行操作。

队列的先进先出原理：

队列就像等待买票的队伍，队列中的第一个人就是第一个得到服务的人。（即先到先得）。
队列中准备被服务的条目的位置，即将从队列中删除的第一个条目，称为队列的前端（有时称为队列头），类似地，最后一个条目的位置队列中，即最近添加的队列，称为队列的后部（或尾部）。见下图。

队列中的 Fifo 属性

队列的特点：

队列可以处理多个数据。
我们可以访问两端。
它们快速且灵活。

队列表示：

与堆栈一样，队列也可以用数组表示：在这种表示中，队列是使用数组来实现的。本例中使用的变量是

队列：存储队列元素的数组名称。
Front：表示队列的数组中存储第一个元素的索引。
后部：代表队列的数组中存储最后一个元素的索引。

1.队列的数组表示：

Python

# 创建一个空队列 表示队列的结构
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:

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 代码实现：

# 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")