Java数据结构:队列(Queue)

xiaoxiao2022-06-12  27

Queue 队列


Queue 接口的定义形式是:

public interface Queue<E> extends Collection<E>

队列可以让人们有效的在尾部添加一个元素,在头部删除一个元素。 是一种先入先出 (FIFO ) 的数据结构。

双端队列可以让人们有效的在头部和尾部同时添加或删除元素,不支持在队列中间添加元素。

在Java SE 6 中引入了Deque接口,并由 ArrayDeque LinkedLisk 类实现。这两个类都提供了双端队列,而且在必要时可以增加队列的长度。

Collection接口继承树

由上图可以看出Queue类也可以用 LinkedList实现

Queue<E> queue = new LinkedList<E>();

1. API

类型方法名功能booleanadd(E element)将元素element插入到队列的尾部booleanoffer(E element)将元素element插入到队列的尾部,如果队列已满,返回nullEremove()删除并返回队列头部元素Epoll()删除并返回队列头部元素,如果队列为空,返回nullEelement()返回队列头部元素,但是不会删除该元素Epeek()返回队列头部元素,但是不会删除该元素,如果队列为空,返回null

1.1 java.util.Queue< E > 5.0

boolean add(E element) boolean offer(E element) //加入 E remove() E poll() //移除 E element() E peek() //获取元素

注1:如果队列没有满, add offer 方法会将给定的元素添加到队列的尾部并返回 true,如果队列已满,add方法将会抛出一个 IllegalStateException 异常,而offer方法会返回 false

注2:如果队列没有空,remove poll 方法会删除并返回队列头部元素 ;如果队列为空,remove方法会抛出一个 NoSuchElementException异常,poll方法会返回 null

注3:如果队列没有空,element peek 方法会返回队列头部元素,但是 不会删除 ;如果队列为空,element方法会抛出一个 NoSuchElementException异常,peek方法会返回 null

1.2 java.util.Deque< E > 6

类型方法名功能voidaddFirst(E element)给定的对象添加到双端队列的头部voidaddLast(E element)给定的对象添加到双端队列的尾部booleanofferFirst(E element)给定的对象添加到双端队列的头部,如果队列满了,返回falsebooleanofferLast(E element)给定的对象添加到双端队列的尾部,如果队列满了,返回falseEremoveFirst()删除并返回队列头部的元素EremoveLast()删除并返回队列尾部的元素EpollFirst()删除并返回队列头部的元素,如果队列为空,返回nullEpollLast()删除并返回队列尾部的元素,如果队列为空,返回nullEgetFirst()返回队列头部元素,但是不会删除该元素EgetLast()返回队列尾部元素,但是不会删除该元素EpeekFirst()返回队列头部元素,但是不会删除该元素,如果队列为空,返回nullEpeekLast()返回队列尾部元素,但是不会删除该元素,如果队列为空,返回null void addFirst(E element) void addLast(E element) boolean offerFirst(E element) boolean offerLast(E element) 将给定的对象添加到双端队列的头部或尾部 。如果队列满了,前面两个方法将抛出一个 IllegalStateException 异常,后面两个方法返回false。 E removeFirst() E removeLast() E pollFirst() E pollLast() 如果队列没有空,删除并返回队列头部的元素 。如果队列为空,前面两个方法将抛出一个 NoSuchElemtentException 异常,而后面两个方法返回null。 E getFirst() E getLast() E peekFirst() E peekLast() 如果队列没有空,返回队列头部的元素,但不删除 。如果队列为空,前面两个方法将抛出一个 NoSuchElemtentException 异常,而后面两个方法返回null。

1.3 java.util.ArrayDeque< E > 5

ArrayDeque() ArrayDeque(int initialCapacity) 用初始容量(Initial Capacity) 16 或给定的初始容量构造一个无限双端队列.

1.4 代码演示(用队列求交集)

当然求交集还可以运用hash散列的方式更快的求得; package 数据结构; import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner cin = new Scanner(System.in); Queue<Integer> q1 = new LinkedList<Integer>(); Queue<Integer> q2 = new LinkedList<Integer>(); int n = cin.nextInt(); int tmp = n; while(tmp-->0) { int s = cin.nextInt(),t = cin.nextInt(); for(int i=s;i<t;i++) { q1.offer(i); } } tmp = n; while(tmp-->0) { int s = cin.nextInt(),t = cin.nextInt(); for(int i=s;i<t;i++) { q2.offer(i); } } int cnt = 0; while(!q1.isEmpty() && !q2.isEmpty()) { if(q1.peek() > q2.peek()) q2.poll(); else if(q1.peek()<q2.peek()) q1.poll(); else { cnt++; q1.poll(); q2.poll(); } } System.out.println(cnt); } }

2. 优先级队列

2.1 优先队列的特点

优先级队列(priority queue)中的元素可以按照任意的顺序输入,却总是按照排序的顺序进行检索。也就是说,无论何时调用 poll 方法,总会获得当前优先级队列中最小的元素。然而,优先级队列并没有对所有的元素进行排序。如果使用迭代的方式处理这些元素,并不需要对它们进行排序。优先级队列使用了一个优雅且高效的数据结构,称为堆 (heap) 。堆是一个可以可以自我调整的二叉树,对树执行 offer 和 poll 操作,可以让最小的元素移动到根,而不必花费时间对元素进行排序。与 TreeSet 一样,一个优先级队列既可以保存实现了 Comparable 接口的类对象,也可以保存在构造器中提供的 Comparator 对象。使用优先级队列的典型示例是任务调度。每一个任务有一个优先级,任务以随机顺序添 加到队列中。每当启动一个新的任务时,都将优先级最高的任务从队列中删除(由于习惯上 将 1设为“ 最高” 优先级,所以会将最小的元素删除)。与 TreeSet 中的迭代不同,这里的迭代并不是按照元素的排列顺序访问的。而删除却总是删掉剩余元素中优先级数最小的那个元素。

2.2 优先队列的方法

方法名功能PriorityQueue()PriorityQueue(int initialCapacity)构造一个用于存放 Comparable 对象的优先级队列。ProrityQueue(int initialCapacity, Comparator ? super E> c)构造一个优先级队列,并用指定的比较器对元素进行排序。

2.3 示例代码

package 数据结构; import java.util.*; class Person { private String name; private int population; public Person() {}; public Person(String name, int population) { this.name = name; this.population = population; } public String getName() { return this.name; } public int getPopulation() { return this.population; } public String toString() { return getName()+" - " + getPopulation(); } } public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner cin = new Scanner(System.in); Comparator<Person> cmp = new Comparator<Person>() { public int compare(Person arg0, Person arg1) { // TODO Auto-generated method stub int num_a = arg0.getPopulation(); int num_b = arg1.getPopulation(); if(num_a < num_b) return 1; else if(num_a > num_b) return -1; else return 0; } }; Queue<Person> priorityQueue = new PriorityQueue<Person>(11,cmp); Person p1 = new Person("p1",1); Person p2 = new Person("p2",3); Person p3 = new Person("p3",2); Person p4 = new Person("p4",0); priorityQueue.offer(p1); priorityQueue.offer(p2); priorityQueue.offer(p3); priorityQueue.offer(p4); System.out.println(priorityQueue.poll().toString()); System.out.println(priorityQueue.poll().toString()); System.out.println(priorityQueue.poll().toString()); System.out.println(priorityQueue.poll().toString()); } }

运行结果:

结果分析:这里按照 Comparator 方法写的排序,如果改变 Comparator 方法 结果会改变;

未完持续……

参考文献 & 博客

Java核心技术 卷Ⅰ基础知识(原书第10版)/(美)凯S.霍斯特曼(Cay S. Horstmann)机械工业出版社Java程序设计教程算法导论 (原书第3版)/ (美)Thomas H.Cormen 机械工业出版社数据结构 java语言描述 (原书第3版)/ (美) Michael Main 机械工业出版社https://www.cnblogs.com/vachester/p/5840217.html 堆和优先队列https://www.cnblogs.com/nayitian/p/3266090.html#collectionframe (Java:集合,Collection接口框架图)http://www.importnew.com/6932.html (Java优先队列(PriorityQueue)示例)https://blog.csdn.net/hiphopmattshi/article/details/7334487?utm_source=blogxgwz0 (java中PriorityQueue优先级队列 使用样例)https://blog.csdn.net/cquzhengdayday/article/details/72514900 (浅谈堆以及java优先队列的详细使用)
转载请注明原文地址: https://www.6miu.com/read-4932765.html

最新回复(0)