Deque是双端队列,可以使用FIFO(队列)和FILO(栈),其实现常见的有ArrayDeque,LinkedList、LinkedBlockingDeque(线程安全)
一. ArrayDeque是基于数组实现的,且数组容量是可扩展的(即无容量边界)的双端队列。它不是线程安全的。该类性能可能快于stack,在作为队列时快于LinkedList。
ArrayDeque作为stack的取代类,而使用。
多数情况下,需要对ArrrayDeque作为线性访问来使用。ArrayDeque内部通过对数组结构使用了存取技巧:双向操作数组。在开始,数组的最后索引位置为head标,起始索引为
tail标,从外观上看,类似一个队列。addFirst将触发head游标-1,addLast将触发tail游标+1,直到head == tail时宣布数组尺寸重新分配。当然removeFirst是将head值置为null,
然后head游标+1。removeLast同样。。由此可见,ArrayDeque(包括所有类型的queue)是不能加入null的。
重新设置size时,是将数组的尺寸直接扩充为原来的两倍,此时head=tail,使用数组copy吧0~tail和head~(length -1)的两段数组分别copy到新数组中,
即新数组和原数组的却别就是中间有已被尺寸的空位。
操作示意图0----tail--->|<-----head----end.
二. LinkedList也是非线程安全的,直接原因就是它和AarrayDeque一样在java.util包中,而不是concurrent包中。LinkedList是非常常用的实现stack和queue的API。
三. ArrayBlockingQueue和LinkedBlockingQueue,这2个API是线程安全的,支持阻塞行为的。
ArrayBlockingQueue是一个有界队列API,需要指定队列的尺寸,其内部实现是基于数组,操作技巧:循环数组。数组的操作上,有2个属性putIndex和takeIndex,putIndex是
下一次put时的位置,takeIndex是下一次take操作时的位置,putIndex和takeIndex区间内的数据时可访问的,如果putIndex = takeIndex,说明数组已经“满”或者“空了”。
0---takeIndex-->---<--putIndex---End.
LinkedBlockingQueue是基于链表实现,支持无界队列,同时也可以支持有界队列(需要传递容量参数)。
相关推荐
STL的容器deque的详细使用方法和文档 6.0代码
STL中的deque模板包括迭代器等接口
PTA 6-3 Deque for DS lesson
SGI STL deque相关代码
案例-评委打分 ...遍历vector容器,取出来每一个选手,执行for循环,可以把10个评分打分存到deque容器中 sort算法对deque容器中分数排序,去除最高和最低分 deque容器遍历一遍,累加总分 获取平均分
自定义deque类,复杂度sqrt(n)
deque dll
双队列双队列双队列双队列双队列双队列双队列双队列双队列双队列双队列双队列双队列双队列双队列双队列双队列双队列
本文深入地研究了std::deque 容器。本文将讨论在一些情况下使用deque> 比vector更好。读完这篇文章后读者应该能够理解在容量增长的过程中deque 与vector在内存分配和性能的不同表现。由于deque> 和vector的用法很...
最近在pythonTip做题的时候,遇到了deque模块,以前对其不太了解,现在特此总结一下 deque模块是python标准库collections中的一项,它提供了两端都可以操作的序列,这意味着,在序列的前后你都可以执行添加或删除...
Deque - 副本
C语言头文件 DEQUEC语言头文件 DEQUEC语言头文件 DEQUEC语言头文件 DEQUEC语言头文件 DEQUEC语言头文件 DEQUEC语言头文件 DEQUEC语言头文件 DEQUEC语言头文件 DEQUEC语言头文件 DEQUEC语言头文件 DEQUEC语言头文件 ...
C++实现STL容器之deque
vector和deque使用方法
STL中vector、list、deque和map的区别
双端队列 Package deque实现了一种非常快速和高效的通用队列/堆栈/ deque数据结构,该结构经过特别优化,可以在生产环境中运行的微服务和无服务器服务使用时执行。 在内部,双端队列将元素存储在动态增长的圆形双向...
创建Deque序列: from collections import deque d = deque() Deque提供了类似list的操作方法: d = deque() d.append('1') d.append('2') d.append('3') len(d) d[0] d[-1] 输出结果: 3 '1' '3' 两端...
在Python文档中搜索队列(queue)会发现,Python标准库中包含了四种队列,分别是queue.Queue / asyncio.Queue / multiprocessing.Queue / collections.deque。 collections.deque deque是双端队列(double-ended ...
list 和 deque郭 炜 刘家瑛北京大学程序设计实习双向链表 #include 在任何位置插入/删除都是常数时间不支持根据下标随机存取元素具有
45. movable元素对于deque速度效能的影响