Java實現的DSA - 優先佇列

概述

優先佇列比普通佇列更專業。與普通佇列一樣，優先佇列具有相同的方法，但有一個主要區別。在優先佇列中，專案按鍵值排序，鍵值最小的專案位於佇列前端，鍵值最大的專案位於佇列後端，反之亦然。因此，我們根據專案的鍵值賦予其優先順序。值越低，優先順序越高。以下是優先佇列的主要方法。

基本操作

• 插入/入隊 − 將專案新增到佇列的尾部。

• 刪除/出隊 − 從佇列的頭部刪除專案。

優先隊列表示

在本文中，我們將使用陣列實現佇列。佇列還支援一些其他操作，如下所示。

• 檢視 − 獲取佇列頭部元素。

• 是否已滿 − 檢查佇列是否已滿。

• 是否為空 − 檢查佇列是否為空。

插入/入隊操作

每當將元素插入佇列時，優先佇列會根據其順序插入該元素。這裡我們假設值較大的資料優先順序較低。

public void insert(int data){
   int i =0;

   if(!isFull()){
      // if queue is empty, insert the data 
      if(itemCount == 0){
         intArray[itemCount++] = data;        
      }else{
         // start from the right end of the queue 
         for(i = itemCount - 1; i >= 0; i-- ){
            // if data is larger, shift existing item to right end 
            if(data > intArray[i]){
               intArray[i+1] = intArray[i];
            }else{
               break;
            }            
         }
         // insert the data 
         intArray[i+1] = data;
         itemCount++;
      }
   }
}

刪除/出隊操作

每當要從佇列中刪除元素時，佇列會使用專案計數獲取該元素。刪除元素後，專案計數減一。

public int remove(){
    return intArray[--itemCount];
}

優先佇列實現

PriorityQueue.java

package com.tutorialspoint.datastructure;

public class PriorityQueue {
   private final int MAX;
   private int[] intArray;
   private int itemCount;

   public PriorityQueue(int size){
      MAX = size;
      intArray = new int[MAX];     
      itemCount = 0;
   }

   public void insert(int data){
      int i =0;

      if(!isFull()){
         // if queue is empty, insert the data 
         if(itemCount == 0){
            intArray[itemCount++] = data;        
         }else{
            // start from the right end of the queue 
            for(i = itemCount - 1; i >= 0; i-- ){
               // if data is larger, shift existing item to right end 
               if(data > intArray[i]){
                  intArray[i+1] = intArray[i];
               }else{
                  break;
               }            
            }   
            // insert the data 
            intArray[i+1] = data;
            itemCount++;
         }
      }
   }

   public int remove(){
      return intArray[--itemCount];
   }

   public int peek(){
      return intArray[itemCount - 1];
   }

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

   public boolean isFull(){
      return itemCount == MAX;
   }

   public int size(){
      return itemCount;
   }
}

演示程式

PriorityQueueDemo.java

package com.tutorialspoint.datastructure;

public class PriorityQueueDemo {
   public static void main(String[] args){
      PriorityQueue queue = new PriorityQueue(6);
       
      //insert 5 items
      queue.insert(3);
      queue.insert(5);
      queue.insert(9);
      queue.insert(1);
      queue.insert(12);

      // ------------------
      // index : 0  1 2 3 4 
      // ------------------
      // queue : 12 9 5 3 1 

      queue.insert(15);

      // ---------------------
      // index : 0  1 2 3 4  5 
      // ---------------------
      // queue : 15 12 9 5 3 1 

      if(queue.isFull()){
         System.out.println("Queue is full!");   
      }


      //remove one item
      int num = queue.remove();
      System.out.println("Element removed: "+num);
      // ---------------------
      // index : 0  1  2 3 4 
      // ---------------------
      // queue : 15 12 9 5 3  

      //insert more items
      queue.insert(16);

      // ----------------------
      // index :  0  1 2 3 4  5
      // ----------------------
      // queue : 16 15 12 9 5 3

      //As queue is full, elements will not be inserted.
      queue.insert(17);
      queue.insert(18);
	 
      // ----------------------
      // index : 0   1  2 3 4 5
      // ----------------------
      // queue : 16 15 12 9 5 3
      System.out.println("Element at front: "+queue.peek());
      System.out.println("----------------------");
      System.out.println("index : 5 4 3 2  1  0");
      System.out.println("----------------------");
      System.out.print("Queue:  ");
      while(!queue.isEmpty()){
         int n = queue.remove();           
         System.out.print(n +" ");
      }
   }
}

如果我們編譯並執行上述程式，則會產生以下結果：

Queue is full!
Element removed: 1
Element at front: 3
----------------------
index : 5 4 3 2  1  0
----------------------
Queue:  3 5 9 12 15 16