优先队列
前言:java中有很多的队列类,其中有一些叫做优先队列,优先队列的优点之一就是能够实现自动排序,排序的方式是可以指定的。PriorityQueue是一个最常用的优先队列类,如果你想按照某种特定的方法进行排序,可以在创建对象的时候,转入一个比较器对象(comparator)。
关于优先队列,因为平时用的比较少,所以还不是很清楚,看了一下源代码,发现自己似乎懂,但又不是很懂。懂了是因为它不就是多了排序的功能而已,不懂是因为它是怎么具体实现的。在这种情况下,我跟倾向于不懂,因为它不就是多了排序功能的队列吗!我自己也能写一个,于是乎我自己也开始写了一个优先队列类,环顾身边和我一起些优先队列的童鞋,他们都喜欢用数组来实现,但我偏不用数组,我选择了用链表来实现。
示例代码如下:
/** * 这是一个节点连类 * 它既可以指向上一个节点,也可以指向下一个节点 */ public class LinkNode{ private int obj;//节点里保存的元素 private LinkNode next;//这是指向链表的下一个节点 private LinkNode back;//指向链表的上一个节点 public LinkNode(int obj) { this.obj=obj; } //设置指向下一个节点的方法 public void setNext(LinkNode next){ this.next=next; } //设置指向上一个节点的方法 public void setBack(LinkNode back) { this.back=back; } //修改节点内容的方法 public void setObj(int obj) { this.obj=obj; } //获得下一个节点的方法 public LinkNode getNext() { return next; } //获得上一个节点的方法 public LinkNode getBack(){ return back; } //获得节点内容的方法 public int getObj() { return obj; } }
节点类的代码很简单,下面是优先队列的代码,下面的代码中为什么要创建头结点和尾节点,能不能省略,具体说来我也不知道,我只知道用它们才能实现我想要的功能,当然这个队列还可以优化。
/** * 这是一个自定义的优先队列类 * 没往里面加一个数据,就可以自动排序 *该优先队列的排序方式是按从大到小的顺序进行排列 */ public class YouxianQueue { private LinkNode root;//头结点 private LinkNode back;//尾节点 private int size=0;//一个保存队列元素个数的属性 public YouxianQueue(){ root=new LinkNode(0);//初始化头结点 back=new LinkNode(0);//初始化尾节点 root.setNext(back);//让头结点和尾节点相互指向 back.setBack(root);// } //王队列里面添加元素的方法 public void add(int i){ LinkNode link=root;//一个中间变量 for(int k=0;k<size+1;k++){ link=link.getNext();//获得下一个节点 if(i>link.getObj()||link.getNext()==null){//如果要插入的元素大于这个节点里的元素,就插入 LinkNode temp=new LinkNode(i);//创建一个新节点 LinkNode back=link.getBack();//获得上一个节点 back.setNext(temp);//上一个节点指向新节点 temp.setBack(back);//新节点指向上一个节点 temp.setNext(link);//新节点指向下一个节点 link.setBack(temp);//上一个节点指向新节点 break;//跳出循环 } } size++; } /** * 类似于根据指定的下标获取对应的元素 * @param w 指定的节点位置 * @return 节点里面的元素 */ public int get(int w){ if(w<0||w>size){//如果查找的下标不合法 throw new NullPointerException(); }else{ LinkNode link=root.getNext();//获得头节点下一个节点 for(int k=0;k<w;k++){ link=link.getNext();//指向对应位置的节点 } return link.getObj(); //返回节点的内容 } } /** * 类似于根据下标移除指定的元素 * @param w 节点的位置 * @return 返回被移除的元素 */ public int remove(int w){ if(w<0||w>size){//如果查找的下标不合法 throw new NullPointerException(); }else{ LinkNode link=root.getNext();//获得头节点下一个节点 for(int k=0;k<w;k++){ link=link.getNext();//指向对应位置的节点 } LinkNode next=link.getNext();//获得当前节点的上一个节点和下一个节点 LinkNode back=link.getBack(); next.setBack(back);//让这两个节点相互指向 back.setNext(next); return link.getObj(); //返回节点的内容 } } /** * 按从小到大的顺序获得对应位置节点的元素 * @param w 节点的位置 * return 节点里面的元素 */ public int get_Min(int w){ if(w<0||w>size){//如果查找的下标不合法 throw new NullPointerException(); }else{ LinkNode link=back.getBack();//获得尾节点的上一个节点 for(int k=0;k<w;k++){ link=link.getBack();//指向对应位置的节点 } return link.getObj(); //返回节点的内容 } } //获得队列的长度,即元素的个数 public int size(){ return size; } }
测试类
public class Test { /** * @param args */ public static void main(String[] args) { Test test=new Test();//创建一个对象 test.testQueue(); } //测试自定义优先队列的方法 public void testQueue(){ java.util.Random ran =new java.util.Random(); YouxianQueue queue=new YouxianQueue(); //给队列随机赋100个值 for(int i=0;i<10;i++){ int temp=ran.nextInt(2000);//获得一个随机数 queue.add(temp);//把它加到队列里面 } //按从大到小输出队列里面的元素 for(int j=0;j<queue.size();j++){ int temp=queue.get(j); System.out.println(temp); } //按从小到大输出队列里面的元素 for(int j=0;j<queue.size();j++){ int temp=queue.get_Min(j); System.out.println(temp); } } }
这个队列很大的缺陷就是不支持泛型,当然把它改成支持泛型也比较简单,经过进一步的思考之后,我发现用数组来实现的队列和用链表实现的队列相比。用数组来实现的链表比较适合存储大量的数据的情况,而是用链表实现的队列跟有利实现频繁修改数据的情况。像上面使用链表来实现的时候,查找和比较里面元素的时候特别麻烦,都得从头到尾的去遍历链表,不想用数组,可以用二分法来进行查找,但是他插入数据就会变得很简单,链表需要像数组那样要开辟连续的空间,这样很灵活。
相关推荐
编写优先队列数据(priority_queue)类型,优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除.在最小优先队列(min priority queue)中,查找操作...
优先队列-java可以选择属性和升序降序
用C语言实现一个优先队列;压缩文件中包括三个文件:1.HeapQueue.h优先队列源代码,2.main.cpp测试主函数;3.HeapQueue.h使用说明
可嵌入到matlab中的优先队列,包括pq_create,插入,删去,取顶端,
提出了基于优先队列的时变网络最短路径算法,能克服传统最短路径算法难以对时变网络求解最短路径的缺陷。提出的时间窗选择策略能够在算法求解过程中为节点选择合适的时间窗以降低路径长度,从而求得精确解。进一步地...
堆排序实现优先队列,利用优先队列做了一个小程序,有兴趣看看
数据结构优先队列,是一个简易版优先队列,输入数据及权值可以对其进行插入,删除等操作。
数据结构,课程设计优先队列实验报告 用最大堆实现的优先队列
C语言 堆 优先队列
优先队列求无序整数序列中第k小的元素.cpp
本文提出一种基于K 叉树的优先队列的算法, 通过建立K 叉树堆的数据结构, 从n 个元素中 得到m 个元素的优先队列, 其算法的最坏时间复杂度为O (2m log2n + 2n ). 本算法是基于二叉树堆 的优先队列算法的推广, 并具有较...
分支限界法中的优先队列式分支限界法解装载问题
c++实现的批处理作业调度问题·优先队列式分支限界法·回溯法包括了FlowShop和make类模板,有测试数据data
数据结构 基于链表实现的优先队列 Cpp文件
采用优先队列式分枝限界法求解0/1背包问题,算法设计第五章,描述的很清晰,里面有完整代码,由于害怕你弄混,所以完整运行的代码参考我的博客文章即可
该算法基于Java语言,对算法设计中的优先队列进行了实现,本人能力有限,如有bug请多指教
本程序主要由堆来实现优先队列的数据结构,主要有优先队列的删除,插入。算法复杂度为logn
优先队列课程设计
用头文件封装的优先队列!可以进行插入、查找、删除等操作!