`
128kj
  • 浏览: 600331 次
  • 来自: ...
社区版块
存档分类
最新评论

用数组实现的优先队列(JAVA)

阅读更多
   优先级队列是不同于先进先出队列的另一种队列。每次去队列的是具有最高优先权的元素。
import java.util.Comparator;
public class PriorityQ<T>  
   {
   
   private final int SIZE = 20;
   private T[] queArray;
   private int size;
   private final Comparator<? super T> comparator;


   public PriorityQ(Comparator<? super T> comparator)         
      {
      queArray = (T[])new Object[SIZE];
      this.comparator=comparator;
      size = 0;
      }

  //添加一项,优先级最高的放在数组尾部(队列头部)
   public void add(T item)  
      {
       if(isFull()) doubleArray();
     
      int j;
     
      for(j=0; j<size; j++)  //找到插入的位置
         if( comparator.compare(item,queArray[j])>=0)
            break;
    
      for(int k=size-1; k>=j; k--)  //移动
         queArray[k+1] = queArray[k];

      queArray[j] = item;  
      size++;
      }

   public void offer(T item){
       add(item);
   }

   //在队列头删除优先级最高的元素并返回
   public T poll()         
      { return queArray[--size]; }



   //从此队列中移除指定元素的单个实例
   public boolean remove(T t) {
      int i= find(t);
      if(i==-1) return false;
      removeN(i);
      return true;
   }
  

  //在优先队列中删除索引为n的项
   public void removeN(int n)       
      {
      for(int j=n; j<size-1; j++)  // move items down
         queArray[j] = queArray[j+1];
      size--;
      }

    //获取但不移除此队列的头
   public T peek()         
      { return queArray[size-1]; }



   public int size()           
      { return size; }

   public boolean isEmpty()  
      { return (size==0); }

   public void clear(){
         size=0;
   } 

   
   public T peekN(int n)     
      { return queArray[n]; }

   public int find(T t)  
      {                          
      for(int j=0; j<size; j++)
         if(comparator.compare(queArray[j],t)==0)
            return j;
      return -1;
      }
  
   private boolean isFull(){
      return size==queArray.length;  

   }  

    private void doubleArray(){   
       
        T [] oldQueue = queArray;   
        int oldSize = queArray.length;   
        queArray =(T[])new Object[2*oldSize];   
        for(int index = 0;index<oldSize;index++){   
            queArray[index] = oldQueue[index];   
        }   
        
    }   

   public void display(){
      if(size==0) {System.out.println("没有了");return;}
      for(int i=0;i<size;i++)
           System.out.print(queArray[i]+",");
      System.out.println();
  }


   public static void main(String args[]){
       PriorityQ Q=new PriorityQ(new Comparator(){   
           public int compare(Object o1,Object o2) {            
              Integer I1=(Integer)o1;   
              Integer I2=(Integer)o2;                    
               return I1.compareTo(I2);
           } 
         });
         for(int i=110;i>0;i--)
          Q.offer(new Integer(java.util.concurrent.ThreadLocalRandom.current().nextInt(40)));
         Q.display();
         System.out.println("===============================");
          for(int i=10;i>0;i--)
            Q.poll();
           Q.display();
          System.out.println("===============================");
         Q.remove(35);
         Q.display();
    }


  }

下载源码:
分享到:
评论

相关推荐

    用堆实现简单的优先队列(JAVA)

    总结,用堆实现的优先队列在Java中是一种高效的数据结构,能够快速地获取和删除最高优先级的元素。通过分析PriorityQueue类和PQTest类的代码,我们可以深入了解堆的内部机制以及如何在实际应用中使用优先队列。

    最小生成树(二维数组实现)

    最小生成树是图论中的一个重要概念,...同时,理解和运用数据结构如并查集、优先队列,也是ACM竞赛中的必备技能。在解决这类问题时,不断练习和熟悉这些工具将有助于你在未来面对更复杂的问题时能迅速找到解决方案。

    简单的优先队列

    `Vector.java`可能是对Java内置`ArrayList`的实现,提供动态数组的功能,这在构建优先队列时也可能会用到。而`Bag.java`可能是一个实现了多态集合的数据结构,允许重复元素,这在某些优先级场景下可能有用。 综上所...

    基于java优先队列(PriorityQueue)的多路排序算法(含代码)

    在这个例子中,`multiMergeSort`方法首先递归地将数组分割成两半,然后使用优先队列`pq`进行归并。当遍历完所有子序列后,`temp`数组中存储了完整的排序结果,最后再复制回原数组`arr`。 在`main`方法中,我们创建...

    Java基于堆结构实现优先队列功能示例

    该示例程序主要介绍了Java基于堆结构实现优先队列功能的简单定义与使用方法,并提供了实例形式的分析。 知识点一: 堆结构是什么? 堆结构是一种特殊的树形结构,它满足以下两个性质:(1)堆结构是一棵完全二叉树...

    基于 Java 实现的队列和堆栈

    - **基本操作**:在Java中,可以使用`java.util.Queue`接口来实现队列。主要方法有`add()`(在队尾添加元素)、`remove()`(移除并返回队头元素)、`peek()`(查看但不移除队头元素)等。 - **实现方式**:常见的...

    Java语言编写的数据结构-队列实现

    顺序队列是用数组实现的队列,其特点是存储空间是连续的。在Java中,我们可以使用ArrayList或ArrayDeque类来创建一个顺序队列。SqQueueCycle可能是一个循环队列,这意味着当队列满时,新的元素会覆盖旧的元素,形成...

    高效的实现队列

    它可能包含了上述某一种或多种队列的实现,例如用C++、Java或其他编程语言实现的简单队列、阻塞队列、并发队列等。具体的实现细节需要查看源代码才能得知。 在实际应用中,队列常被用于任务调度、消息传递、网络...

    Java Methods-Heaps and Priority Queues.ppt

    java.util.PriorityQueue类使用了堆来实现优先队列的功能。 四、堆的实现 堆的实现方式有很多种,常见的有二叉堆(Binary Heap)和斐波那契堆(Fibonacci Heap)。二叉堆是一种简单的堆实现方式,它使用了数组来...

    java编程实现优先队列的二叉堆代码分享

    3. Java 实现二叉堆的优先队列:使用 Java 语言实现二叉堆的优先队列,可以使用数组来存储元素,并使用 swim 和 sink 方法来维护堆的有序性。 4. swim 方法的实现:swim 方法用于将元素上浮到正确的位置,以维护堆...

    Java数组模拟优先级队列数据结构的实例

    总结来说,这个Java代码实例展示了如何使用数组和自定义比较逻辑来实现优先级队列。虽然这种方法在性能上可能不如Java内置的`PriorityQueue`类高效,但对于学习理解优先级队列的工作原理和数据结构的实现是一个很好...

    java 二维数组 随机生成迷宫

    - **广度优先搜索(BFS)**:BFS使用队列来处理节点的访问顺序,通常可以生成更均匀的迷宫,因为每个节点的邻居被访问的机会是均等的。 - **Prim算法或Kruskal算法**:这些图论算法通常用于生成最小生成树,但也...

    图的邻接矩阵实现及广度优先搜索(JAVA)

    本文将深入探讨如何使用Java实现图的邻接矩阵以及如何在该数据结构上执行广度优先搜索(BFS)。 **邻接矩阵** 邻接矩阵是一种二维数组,它用来表示图中顶点之间的连接。如果图是无向的,邻接矩阵是对称的;如果图...

    JAVA迷宫,JAVA语言,数组

    "1.ppt"文件可能是关于这个主题的演示文稿,它可能包含了更详细的步骤、示例代码或图形解释,帮助学习者更好地理解如何用Java实现数组迷宫。如果你能够访问这个文件,那么将对你的学习大有裨益。 总之,Java语言和...

    图数据结构以及深度优先和广度优先算法java实现

    BFS通常使用队列来辅助实现,确保先访问距离起点近的节点。 在提供的压缩包文件中,我们有以下三个文件: 1. **DefaultGraph.java**:这可能是图的默认实现,包含了图的基本操作,如添加顶点、添加边、删除顶点或边...

    使用队列实现排队系统

    - **服务优先级**:可以使用优先级队列来实现不同优先级的用户优先服务。例如,VIP客户可以优先出队。 - **多服务窗口**:如果有多个服务窗口,可以使用多个队列,每个窗口对应一个队列,根据窗口的可用性分配任务...

    阻塞队列阻塞队列阻塞队列

    ArrayBlockingQueue是一个基于固定数组实现的阻塞队列。它的容量在创建时就需要指定,并且不可变。队列内部采用双指针机制,一个指向头部,一个指向尾部,进行元素的入队和出队操作。ArrayBlockingQueue支持公平和非...

    拓扑排序java实现

    3. **性能优化**:对于大规模数据集,可以考虑使用更高效的数据结构和算法,比如优先队列。 综上所述,该代码片段提供了一个基本的拓扑排序实现框架,通过理解其核心算法流程,可以进一步对其进行优化和扩展,以...

    手撸一个优先队列(csdn)————程序.pdf

    在Java中,`java.util.PriorityQueue`是内置的优先队列实现,但这里我们将探讨如何手动实现一个简单的优先队列。 首先,我们需要理解优先队列的核心功能。这个手动实现的优先队列将具备以下特性: 1. **泛型支持**...

Global site tag (gtag.js) - Google Analytics