Java数组模拟优先级队列数据结构的实例
优先级队列
如果我们给每个元素都分配一个数字来标记其优先级,不妨设较小的数字具有较高的优先级,这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样,我们就引入了优先级队列这种数据结构。优先级队列(priorityqueue)是0个或多个元素的集合,每个元素都有一个优先权,对优先级队列执行的操作有(1)查找(2)插入一个新元素(3)删除一般情况下,查找操作用来搜索优先权最大的元素,删除操作用来删除该元素。对于优先权相同的元素,可按先进先出次序处理或按任意优先权进行。
Java数组模拟队列
队列是一种特殊的线性表,它只允许在表的前端进行删除操作,而在表的后端进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。这也就是我们平常经常用说到的先进先出原则(FIFO)。Java中的List就可以作为队列来使用,在队列尾部添加元素则使用list.add方法,从队列头部删除元素则使用list.remove方法。
Java数组模拟优先级队列结构实例:
packagedatastruct; importjava.util.Arrays; importjava.util.Comparator; /** *用数组模拟优先级队列优先级高的排前、先出线性表结构 *类似使用了比较器的TreeSet、TreeMap */ publicclassSimulatePriorityQueue{ publicstaticvoidmain(String[]args){ SimulatePriorityQueuequeue=newSimulatePriorityQueue(4); //SimulateQueuequeue=newSimulateQueue(); //System.out.println("取出元素:"+queue.remove()); queue.insert(1); queue.insert(3); queue.insert(2); queue.insert(5); queue.insert(4); System.out.println("size:"+queue.size()); System.out.println("peek:"+queue.peek()); System.out.println("取出元素:"+queue.remove()); System.out.println("取出元素:"+queue.remove()); System.out.println("取出元素:"+queue.remove()); System.out.println("取出元素:"+queue.remove()); //System.out.println("取出元素:"+queue.remove()); System.out.println("size:"+queue.size()); System.out.println(); } privateintmSize=3;//大小 privateint[]mArray;//数组 privateintmNextItem;//下一个位置,也可当作当前的元素数 publicSimulatePriorityQueue(){ mArray=newint[mSize]; mNextItem=0; } publicSimulatePriorityQueue(intsize){ this.mSize=size; mArray=newint[mSize]; mNextItem=0; } /** *插入元素 *@paramitem */ publicvoidinsert(intitem){ if(!isFull()){ mArray[mNextItem++]=item; for(inti=0;i<mNextItem;i++){//冒泡排序 for(intj=0;j<mNextItem-1;j++){ if(mArray[j]>mArray[j+1]){ mArray[j]=mArray[j+1]+0*(mArray[j+1]=mArray[j]); System.out.println(Arrays.toString(mArray)); } } } System.out.println(Arrays.toString(mArray)); }else{ System.out.println("----不能插入元素了,队列已满----"); } } /** *移出元素先进先出 *@return */ publicintremove(){ if(!isEmpty()){ returnmArray[--mNextItem]; }else{ thrownewIllegalArgumentException("没有元素可以取出了"); } } /** *查看前面的元素 *@return */ publicintpeek(){ returnmArray[mNextItem-1]; } /** *是否为空 *@return */ publicbooleanisEmpty(){ returnmNextItem==0; } /** *是否满 *@return */ publicbooleanisFull(){ returnmNextItem==mSize; } /** *size *@return */ publicintsize(){ returnmNextItem; } }
输出结果:
[1,0,0,0] [1,3,0,0] [1,2,3,0] [1,2,3,0] [1,2,3,5] ----不能插入元素了,队列已满---- size:4 peek:5 取出元素:5 取出元素:3 取出元素:2 取出元素:1 size:0