作为数据结构中比较常见的类型,你足够了解队列(队列)吗?从今天开始,我将为你讲解关于队列(队列)的一切,包括概念,类型和具体使用方法,如果你对此足够感兴趣,赶快来加入我们,我将同你一起探索队列的奥秘。
概念
队列
队列是一种特殊的线性表,是一种先进先出(FIFO)的数据结构。它只允许在表的前端(前)进行删除操作,而在表的后端(后方)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。正因为队列先进先出的先天特性,在一些特殊场合下称为首选项,比如:电商的秒杀,将每一个订单请求作为一个处理任务,按顺序一一排列到队列中等待处理。经典运用:线程池。
java中的队列(队列)
队列接口与列表,设置为同级别,都为收集接口子接口。除了拥有收集接口基本操作外,队列还提供其他的插入,提取和检查操作。每个方法都存在两种形式:一种抛出异常(操作失败时),另一种返回一个特殊值(零或假,具体取决于操作)。插入操作的后一种形式是用于专门为有容量限制的队列实现设计的;在大多数实现中,插入操作不会失败。
方法对比
分类
队列大体分2类:
1的在非阻塞队列:没有实现BlockingQueue接口的队列:
常见的有:
ConcurrentLinkedQueue:一个基于链表节点的* * *线程安全队列。此队列按照FIFO(先进先出)原则对元素进行排序。队列的头部是队列中时间最长的元素。队列的尾部是队列中时间最短的元素。新的元素插入到队列的尾部,队列获取操作从队列头部获得元素。当多个线程共享访问一个公共收集时,ConcurrentLinkedQueue是一个恰当的选择。
LinkedList:底层维护一个链表,实现所有可选的列表操作,并且允许所有元素(包括null)。除了实现列表接口外,LinkedList类还为在列表的开头及结尾,删除和插入元素提供了统一的命名方法。可用于实现堆栈,队列或双端队列等。
PriorityQueue:一个基于优先级堆的* * *优先级队列。优先级队列的元素按照其自然顺序进行排序,或者根据构造队列时提供的比较器进行排序,具体取决于所使用的构造方法。
2祝辞阻塞队列:实现BlockingQueue接口的队列
常见有:
ArrayBlockingQueue:一个由数组支持的有界阻塞队列。此队列按FIFO(先进先出)原则对元素进行排序。队列的头部是在队列中存在时间最长的元素。队列的尾部是在队列中存在时间最短的元素。新元素插入到队列的尾部,队列获取操作则是从队列头部开始获得元素。因为底层缓存的一有界的数组,当缓存区创建成功后,长度便固定,试图向满队列中放元素,势必导致阻塞。另外,此类也支持公平原则,如果公平参数被设置真的,等待时间最长的线程会优先得到处理。公平性通常会降低吞吐量,但也减少了可变性和避免了”不平衡性”。
LinkedBlockingQueue:底层使用链表实现的无上界的阻塞队列(可以使用指定界限的方式,设置队列的容量大,小默认为整数。MAX_VALUE),通常链表队列的的吞吐量要高于基于数组的队列,但是在大多数并发应用程序中,其可预知的性能要低。
DelayQueue:一个* * *阻塞队列,和其他队列不同,获取该队列数据,只有在延迟期满时才能从中提取元素。该队列的头部是延迟期满后保存时间最长的延迟元素。如果延迟都还没有期满,则队列没有头部,并且调查将返回零。当一个元素的getDelay (TimeUnit.NANOSECONDS)方法返回一个小于等于0的值时,将发生到期。即使无法使用带或调查移除未到期的元素,也不会将这些元素作为正常元素对待。
PriorityBlockingQueue:是一个带优先级的队列,而不是先进先出队列。元素按优先级顺序被移除,该队列也没有上限(看了一下源码,PriorityBlockingQueue是对PriorityQueue的再次包装,是基于堆数据结构的,而PriorityQueue是没有容量限制的,与ArrayList一样,所以在优先阻塞队列上把时是不会受阻的。虽然此队列逻辑上是* * *的,但是由于资源被耗尽,所以试图执行添加操作可能会导致OutOfMemoryError),但是如果队列为空,那么取元素的操作花就会阻塞,所以它的检索操作花是受阻的。另外,往入该队列中的元素要具有比较能力。
SynchronousQueue:一种阻塞队列,其中每个插入操作必须等待另一个线程的对应移除操作,反之亦然。同步队列没有任何内部容量,甚至连一个队列的容量都没有。不能在同步队列上进行peek,因为仅在试图要移除元素时,该元素才存在,除非另一个线程试图移除某个元素,否则也不能(使用任何方法)插入元素;也不能迭代队列,因为其中没有元素可用于迭代。队列的头是尝试添加到队列中的首个已排队插入线程的元素,如果没有这样的已排队线程,则没有可用于移除的元素并且民意调查()将会返回零。对于其他收集方法(例如包含),SynchronousQueue作为一个空集合。此队列不允许零元素。
