关于个人工作室网站模板,廊坊seo关键词优化,莱州市规划建设管理局网站,集团网站建设运营公司文章目录 一、什么是队列二、队列特性阻塞和非阻塞有界和无界单向链表和双向链表 三、Java队列接口继承图四、Java队列常用方法五、队列实现方式与效率分析六、队列的应用场景七、Python中队列与优先级队列使用 一、什么是队列
队列是一种特殊的线性表#xff0c;遵循先入先出… 文章目录 一、什么是队列二、队列特性阻塞和非阻塞有界和无界单向链表和双向链表 三、Java队列接口继承图四、Java队列常用方法五、队列实现方式与效率分析六、队列的应用场景七、Python中队列与优先级队列使用 一、什么是队列
队列是一种特殊的线性表遵循先入先出、后入后出的基本原则一般来说它只允许在表的前端进行删除操作而在表的后端进行插入操作但是Java的某些队列允许在任何地方插入删除Python则不能这是因为这些队列实现了Collections接口比如我们常用的LinkedList集合它实现了Queue接口因此我们可以理解为 LinkedList 就是一个队列再比如优先级队列PriorityQueue实现了Queue接口Queue接口中的remove()方法删除对头元素同时实现了Collection接口Collection接口提供了remove(Object o)方法用于删除队列中任意存在的元素但该方法效率较低。
二、队列特性
队列主要分为阻塞和非阻塞有界和无界、单向链表和双向链表之分
阻塞和非阻塞
阻塞队列 入列(添加元素)时如果元素数量超过队列总数会进行等待阻塞待队列的中的元素出列后元素数量未超过队列总数时就会解除阻塞状态进而可以继续入列
出列(删除元素)时如果队列为空的情况下也会进行等待阻塞待队列有值的时候即会解除阻塞状态进而继续出列 阻塞队列的好处是可以防止队列容器溢出只要满了就会进行阻塞等待也就不存在溢出的情况 只要是阻塞队列都是线程安全的
非阻塞队列 不管出列还是入列都不会进行阻塞. 入列时如果元素数量超过队列总数则会抛出异常出列时如果队列为空则取出空值
一般情况下非阻塞式队列使用的比较少一般都用阻塞式的对象比较多阻塞和非阻塞队列在使用上的最大区别就是阻塞队列提供了以下2个方法
出队阻塞方法 take()
入队阻塞方法 put()有界和无界
有界有界限大小长度受限制 无界无限大小其实说是无限大小其实是有界限的只不过超过界限时就会进行扩容就行ArrayList一样在内部动态扩容
单向链表和双向链表
单向链表 每个元素中除了元素本身之外还存储一个指针这个指针指向下一个元素
双向链表 除了元素本身之外还有两个指针一个指针指向前一个元素的地址另一个指针指向后一个元素的地址
三、Java队列接口继承图 四、Java队列常用方法
队列除了基本的 Collection 操作外还提供特有的插入、提取和检查操作(如上)。每个方法都存在两种形式一种抛出异常操作失败时另一种返回一个特殊值null 或 false具体取决于操作。插入操作的后一种形式是用于专门为有容量限制的 Queue 实现设计的在大多数实现中插入操作不会失败。
Queue是java中实现队列的接口它总共只有6个方法我们一般只用其中3个就可以了。Queue的实现类有LinkedList和PriorityQueue。最常用的实现类是LinkedList。
Queue的6个方法分类 压入元素添加add()、offer() 相同未超出容量从队尾压入元素返回压入的那个元素。 区别在超出容量时add()方法会对抛出异常offer()返回false 弹出元素删除remove()、poll() 相同容量大于0的时候删除并返回队头被删除的那个元素。 区别在容量为0的时候remove()会抛出异常poll()返回false 获取队头元素但不删除element()、peek() 相同容量大于0的时候都返回队头元素。但是不删除。 区别容量为0的时候element()会抛出异常peek()返回null。
抛出异常返回特殊值插入add(e)offer(e)删除remove()poll()检查element()peek()
知识点 offer、poll、remove、element、peek 其实是属于Queue接口。
五、队列实现方式与效率分析
数组队列通过数组可变数组实现一个队列 数组是连续存储添加元素、删除元素很慢时间复杂度O(n)这是因为添加元素需要动态扩容删除某位置元素后需要将其后元素整体前移改查很快不需要改变数据结构 链表队列通过链表实现一个对列 链表是非连续存储增删很快添加删除元素的时间复杂度都是O(1)但是改查很慢因为没有索引需要遍历链表找到元素位置进行删除。 栈队列通过两个栈实现一个队列 在20万数据循环操作下链表实现的队列最快是栈队列的2572倍是数组的643倍。这个数值具体看设备算力这里只做参考。
六、队列的应用场景
用于解决图和树等数据结构中的搜索问题。 广度优先搜索广度优先搜索可以通过队列来实现对节点的遍历通常就会从搜索候补中选择最早的数据作为下一个顶点。此时在候补顶点的管理上就可以使用队列。
Dijkstra算法优先队列
A*算法优先队列
七、Python中队列与优先级队列使用
Python的Queue模块中提供了同步的、线程安全的队列类包括FIFO先入先出)队列QueueLIFO后入先出队列LifoQueue和优先级队列PriorityQueue。这些队列都实现了锁原语能够在多线程中直接使用。可以使用队列来实现线程间的同步。
常用方法
Queue.qsize() 返回队列的大小Queue.empty() 如果队列为空返回True,反之FalseQueue.full() 如果队列满了返回True,反之FalseQueue.full 与 maxsize 大小对应Queue.get([block[, timeout]])获取队列timeout等待时间Queue.get_nowait() 相当于Queue.get(False)非阻塞方法Queue.put(item) 写入队列timeout等待时间Queue.task_done() 在完成一项工作之后Queue.task_done()函数向任务已经完成的队列发送一个信号。每个get()调用得到一个任务接下来task_done()调用告诉队列该任务已经处理完毕。Queue.join() 实际上意味着等到队列为空再执行别的操作
import queuequeue queue.Queue()添加元素至队列
queue.put(zhangsan)查看队列元素
print(queue) # 直接打印队列不行
print(queue.queue)queue.Queue object at 0x0000022B05E98430
deque([zhangsan])判断元素是否在队列中
print(zhangsan in queue.queue)True删除队头元素
print(queue.get())
print(queue.queue)
print(queue.qsize)zhangsan
deque([])
bound method Queue.qsize of queue.Queue object at 0x0000022B05E98430判断队列是否为空
print(queue.empty())True优先级队列的使用 创建优先级队列
import queue
queue queue.PriorityQueue()添加元素至优先队列查看队列元素
# 添加元素至优先队列
queue.put((3,古力热巴))
queue.put((2,马儿扎哈))
queue.put((1,迪丽热巴))
queue.put((9,仓央嘉措))
# 查看队列元素
print(queue.queue)[(1, 迪丽热巴), (3, 古力热巴), (2, 马儿扎哈), (9, 仓央嘉措)]判断元素是否在队列中
print((1,迪丽热巴) in queue.queue)True删除并返回队头
# 删除队头
print(queue.get())
print(queue.queue)(1, 迪丽热巴)
[(2, 马儿扎哈), (3, 古力热巴), (9, 仓央嘉措)]参考 https://blog.csdn.net/xijinno1/article/details/132114694
